圖論基本概念學習教案

1、圖論圖論(t ln)基本概念基本概念第一頁，共52頁。有多少輛汽車從城市P開到城市Q？最優(yōu)支撐樹問題：某一地區(qū)有若干個主要城市，擬修建高速公路把這些城市連接起來，使得從其中任何(rnh)一個城市都可以經(jīng)高速公路直接或間接到達另一個城市。假設已經(jīng)知道了任意兩個城市之間修建高速公路的成本，那么應如何決定在哪些城市間修建高速公路，使得總成本最?。康?頁/共52頁第二頁，共52頁。無序集AB=(x,y) | xAyB第2頁/共52頁第三頁，共52頁。V = v1, v2, ,v5, E = (v1,v1), (v1,v2), (v2,v3), (v2,v3), (v2,v5), (v1,v5), (v

2、4,v5) 則 G = 為一無向圖第3頁/共52頁第四頁，共52頁。注意：圖的數(shù)學定義(dngy)與圖形表示，在同構（待敘）的意義下是一一對應的第4頁/共52頁第五頁，共52頁。第5頁/共52頁第六頁，共52頁。第6頁/共52頁第七頁，共52頁。8. 鄰域鄰域(ln y)與關聯(lián)集與關聯(lián)集 vV(G) (G為無向圖為無向圖) v 的關聯(lián)的關聯(lián)(gunlin)集集 v V(D) (D為有向圖為有向圖)9. 標定圖與非標定圖標定圖與非標定圖(頂點和邊指定頂點和邊指定(zhdng)編號的）編號的）10. 基圖（有向圖的有向邊改為無向邊）基圖（有向圖的有向邊改為無向邊）相關概念相關概念第7頁/共52頁第

3、八頁，共52頁。簡單圖是極其重要的概念第8頁/共52頁第九頁，共52頁。 (3) (G)（最大度）, (G)（最小度） 無向圖中 (4) +(D), +(D), (D), (D), (D), (D) (5) 度數(shù)(d shu)為1的點稱為懸掛點，關聯(lián)的邊為懸掛邊；奇頂點度與偶度頂點第9頁/共52頁第十頁，共52頁。定理定理(dngl)14.1 (dngl)14.1 設設G=G=為任意無向圖，為任意無向圖，V=v1,v2,vn, |E|=m, V=v1,v2,vn, |E|=m, 則則證 G中每條邊 (包括環(huán)) 均有兩個端點(dun din)，所以在計算G中各頂點度數(shù)之和時，每條邊均提供2度，m

4、 條邊共提供 2m 度.此二定理(dngl)是歐拉1736年給出，是圖論的基本定理(dngl)握手定理握手定理定理定理14.2 設設D=為任意有向圖，為任意有向圖，V=v1,v2,vn, |E|=m, 則則第10頁/共52頁第十一頁，共52頁。由于2m, 均為偶數(shù)，所以為偶數(shù)，但因為V1中頂點度數(shù)為奇數(shù)(j sh)，所以|V1|必為偶數(shù). 第11頁/共52頁第十二頁，共52頁。d+(v2), , d+(vn) D的入度列：d(v1), d(v2), , d(vn) 3. 非負整數(shù)列d=(d1, d2, , dn)是可圖化的，是可簡單圖化的.易知：(2, 4, 6, 8, 10)，(1, 3,

5、3, 3, 4) 是可圖化的，后者又是可簡單圖化的，而(2, 2, 3, 4, 5)，(3, 3, 3, 4) 都不是(b shi)可簡單圖化的，特別是后者也不是(b shi)可圖化的第12頁/共52頁第十三頁，共52頁。(f(vi),f(vj)（）的重數(shù)相同，則稱G1與G2是同構的，記作G1G2. l圖之間的同構關系具有自反性、對稱性和傳遞性圖之間的同構關系具有自反性、對稱性和傳遞性.l能找到多條同構的必要條件，但它們全不是充分條件：能找到多條同構的必要條件，但它們全不是充分條件：l 邊數(shù)相同，頂點數(shù)相同邊數(shù)相同，頂點數(shù)相同; 度數(shù)列相同度數(shù)列相同; l 對應頂點的關聯(lián)集及鄰域的元素對應頂點

6、的關聯(lián)集及鄰域的元素(yun s)個數(shù)相同，等等個數(shù)相同，等等l 若破壞必要條件，則兩圖不同構若破壞必要條件，則兩圖不同構l判斷兩個圖同構是個難題判斷兩個圖同構是個難題第13頁/共52頁第十四頁，共52頁。 (1) (2) (3) (4) 圖中，圖中，(1)與與(2)不同不同(b tn)構（度數(shù)列不同構（度數(shù)列不同(b tn)），），(3)與與(4)也不同也不同(b tn)構構. (1) (2) 第14頁/共52頁第十五頁，共52頁。(3) n (n1) 階競賽(jngsi)圖基圖為Kn的有向簡單圖.簡單性質：邊數(shù) 1,2)1( nnnm 第15頁/共52頁第十六頁，共52頁。 (1) (2)

7、 (3)定義定義(dngy)14.7 n 階階k正則圖正則圖=k 的無向簡單圖的無向簡單圖簡單性質：邊數(shù)（由握手定理得）簡單性質：邊數(shù)（由握手定理得）Kn是是 n1正則圖，正則圖，彼得松圖（見書上圖彼得松圖（見書上圖14.3(1) 所示，記住它）所示，記住它）第16頁/共52頁第十七頁，共52頁。(5) E（EE且E）的導出子圖，記作GE第17頁/共52頁第十八頁，共52頁。例例2 畫出畫出K4的所有的所有(suyu)非同構的生成子圖非同構的生成子圖實例實例(shl)第18頁/共52頁第十九頁，共52頁。. 問：互為自補圖的兩個圖的邊數(shù)有何關系？第19頁/共52頁第二十頁，共52頁。(2) 簡

8、單(jindn)通路與回路：所有邊各異，為簡單(jindn)通路，又若v0=vl，為簡單(jindn)回路(3) 初級通路(路徑)與初級回路(圈)：中所有頂點各異，則稱為初級通路(路徑)，又若除v0=vl，所有的頂點各不相同且所有的邊各異，則稱為初級回路(圈)(4) 復雜通路與回路：有邊重復出現(xiàn)第20頁/共52頁第二十一頁，共52頁。的為例） 定義意義下無向圖：圖中長度為l（l3）的圈，定義意義下為2l個有向圖：圖中長度為l（l3）的圈，定義意義下為l個 同構意義下：長度相同的圈均為1個試討論l=3和l=4的情況第21頁/共52頁第二十二頁，共52頁。存在 vi 到自身的回路，則一定存在vi

9、到自身長度(chngd)小于或等于 n 的回路.推論 在一個n 階圖G中，若存在 vi 到自身的簡單回路，則一定存在長度(chngd)小于或等于n 的初級回路.第22頁/共52頁第二十三頁，共52頁。，稱G連通 V/R=V1,V2,Vk，稱GV1, GV2, ,GVk為連通分支，其個數(shù) p(G)=k (k1)； k=1，G連通第23頁/共52頁第二十四頁，共52頁。 d(u,v)=d(v,u) d(u,v)+d(v,w)d(u,w)第24頁/共52頁第二十五頁，共52頁。定義14.16 G=, VV V為點割集p(GV)p(G)且有極小性 v為割點v為點割集定義14.17 G=, EE E是邊

10、割集p(GE)p(G)且有極小性 e是割邊（橋）e為邊割集第25頁/共52頁第二十六頁，共52頁。割集，e8是橋，e7,e9,e5,e6 是邊割集嗎？幾點說明：幾點說明：Kn中無點割集，中無點割集，Nn中既無點割集，也無邊中既無點割集，也無邊(wbin)割集，其中割集，其中Nn為為 n 階零圖階零圖. 若若G 連通，連通，E為邊割集，則為邊割集，則 p(GE)=2，V為點割集，則為點割集，則 p(GV)2 第26頁/共52頁第二十七頁，共52頁。min|E|E為邊割集若G非連通，則(G) = 0若(G)r，則稱G是 r 邊-連通圖圖中，=1，它是 1-連通圖 和 1邊-連通圖第27頁/共52頁

11、第二十八頁，共52頁。不是(r+s)-邊連通圖，s1l, , 之間的關系.l定理(dngl)7.5 (G)(G)(G)l請畫出一個的無向簡單圖第28頁/共52頁第二十九頁，共52頁。類似(li s)于無向圖中，只需注意距離表示法的不同(無向圖中d(vi,vj)，有向圖中d) 及 d無對稱性第29頁/共52頁第三十頁，共52頁。定理14.8 D強連通當且僅當D中存在經(jīng)過每個頂點至少一次的回路定理14.9 D單向(dn xin)連通當且僅當D中存在經(jīng)過每個頂點至少一次的通路第30頁/共52頁第三十一頁，共52頁。為 l 的路徑擴大成了長度為 l+k 的路徑），稱l+k為“極大路徑”，稱使用此種方法

12、證明問題的方法為“擴大路徑法”.有向圖中類似討論，只需注意，在每步擴大中保證有向邊方向的一致性.第31頁/共52頁第三十二頁，共52頁。(2),(3),(4)中實線邊所示的都是它擴展成的極大路徑. 還能找到另外的極大路徑嗎？ (1) (2) (4) (3)第32頁/共52頁第三十三頁，共52頁。證證 設設 = v0v1vl 是由初始路徑是由初始路徑 0 用擴大路徑法的得到的極用擴大路徑法的得到的極大路徑，則大路徑，則 l （為什么？）（為什么？）. 因為因為(yn wi)v0 不與不與 外頂點相鄰，又外頂點相鄰，又 d(v0) ，因而在，因而在 上除上除 v1外，至少還存在外，至少還存在 1個

13、頂點與個頂點與 v0 相鄰相鄰. 設設 vx 是離是離 v0 最遠的頂最遠的頂點，于是點，于是 v0v1vxv0 為為 G 中長度中長度 +1 的圈的圈. 第33頁/共52頁第三十四頁，共52頁。補頂點子集，常將二部圖G記為. 又若G是簡單二部圖，V1中每個頂點均與V2中所有的頂點相鄰，則稱G為完全二部圖，記為 Kr,s，其中r=|V1|，s=|V2|. 注意，n 階零圖為二部圖. 第34頁/共52頁第三十五頁，共52頁。第35頁/共52頁第三十六頁，共52頁。第36頁/共52頁第三十七頁，共52頁。有向圖的關聯(lián)矩陣（無環(huán)有向圖） 定義(dngy)14.25 有向圖D=，令則稱 (mij)nm

14、為D的關聯(lián)矩陣，記為M(D). (4) 平行平行(pngxng)邊對應的列相同邊對應的列相同性質性質(xngzh)有向圖的關聯(lián)矩陣第37頁/共52頁第三十八頁，共52頁。第38頁/共52頁第三十九頁，共52頁。推論推論(tuln) 設設Bl=A+A2+Al（l1），則），則 Bl中元素中元素為D中長度為 l 的通路(tngl)總數(shù)，定理定理14.11 設設 A為有向圖為有向圖 D 的鄰接矩陣，的鄰接矩陣，V=v1, v2, , vn為頂點為頂點(dngdin)集，則集，則 A 的的 l 次冪次冪 Al（l1）中元素）中元素為D中vi 到vj長度為 l 的通路數(shù)，其中為vi到自身長度為 l 的回

15、路數(shù)，而為為D中長度小于或等于中長度小于或等于 l 的回路數(shù)的回路數(shù)為為D中長度小于或等于中長度小于或等于 l 的通路數(shù)的通路數(shù). 鄰接矩陣的應用鄰接矩陣的應用為為D 中長度為中長度為 l 的回路總數(shù)的回路總數(shù). 第39頁/共52頁第四十頁，共52頁。例例5 有向圖有向圖D如圖所示，求如圖所示，求 A, A2, A3, A4，并回答諸問題：，并回答諸問題：(1) D 中長度為中長度為1, 2, 3, 4的通路各有多少條？其中回路分別的通路各有多少條？其中回路分別(fnbi)為多少條？為多少條？(2) D 中長度小于或等于中長度小于或等于4的通路為多少條？其中有多少條回路？的通路為多少條？其中有

16、多少條回路？實例實例(shl)第40頁/共52頁第四十一頁，共52頁。(1) D中長度為中長度為1的通路的通路(tngl)為為8條，其中有條，其中有1條是回路條是回路. D中長度為中長度為2的通路的通路(tngl)為為11條，其中有條，其中有3條是回路條是回路. D中長度為中長度為3和和4的通路的通路(tngl)分別為分別為14和和17條，回路分別條，回路分別 為為1與與3條條.(2) D中長度小于等于中長度小于等于4的通路的通路(tngl)為為50條，其中有條，其中有8條是回路條是回路.實例實例(shl)求解求解第41頁/共52頁第四十二頁，共52頁。定義定義(dngy)14.27 設設D=

17、為有向圖為有向圖. V=v1, v2, , vn, 令令 有向圖的可達矩陣有向圖的可達矩陣(j zhn)（無限（無限制）制）稱稱 (pij)nn 為為D的可達矩陣，記作的可達矩陣，記作P(D)，簡記為，簡記為P. 由于由于(yuy)viV，vivi，所以，所以P(D)主對角線上的元素全為主對角線上的元素全為1. 由定義不難看出由定義不難看出, D 強連通當且僅當強連通當且僅當 P(D)為全為全1矩陣矩陣. 下圖所示有向圖下圖所示有向圖 D 的可達矩陣為的可達矩陣為第42頁/共52頁第四十三頁，共52頁。第43頁/共52頁第四十四頁，共52頁。l會判別有向圖連通性的類型l熟練掌握用鄰接矩陣及其冪

18、求有向圖中通路與回路數(shù)的方法，會求可達矩陣第44頁/共52頁第四十五頁，共52頁。19階無向圖階無向圖G中，每個頂點中，每個頂點(dngdin)的度數(shù)不是的度數(shù)不是5就是就是6. 證明證明G中至少有中至少有5個個6度頂點度頂點(dngdin)或至少有或至少有6個個5度頂點度頂點(dngdin). 練習練習(linx)1證證 關鍵是利用握手定理的推論關鍵是利用握手定理的推論. 方法一：窮舉法方法一：窮舉法設設G中有中有x個個5度頂點，則必有度頂點，則必有(9x)個個6度頂點，由握手定理推論可知，度頂點，由握手定理推論可知，(x,9x)只有只有5種可能種可能(knng)：(0,9), (2,7),

19、 (4,5), (6,3), (8,1）它們都滿足要求）它們都滿足要求. 方法二：反證法方法二：反證法否則，由握手定理推論可知，否則，由握手定理推論可知，“G至多有至多有4個個5度頂點并且至多有度頂點并且至多有4個個6度頂點度頂點”，這與，這與G是是 9 階圖矛盾階圖矛盾. 第45頁/共52頁第四十六頁，共52頁。2數(shù)組數(shù)組2, 2, 2, 2, 3, 3能簡單能簡單(jindn)圖化嗎？若能，畫出盡可能多的非同構的圖來圖化嗎？若能，畫出盡可能多的非同構的圖來. 練習練習(linx)2只要能畫出只要能畫出6 階無向簡單階無向簡單(jindn)圖，就說明它可簡單圖，就說明它可簡單(jindn)圖化圖化. 下圖的下圖的4個圖都以此數(shù)列為度數(shù)列，請證明它們彼此不同構，都是個圖都以此數(shù)列為度數(shù)列，請證明它們彼此不同構，都是K6的子圖的子圖.第46頁/共52頁第四十七頁，共52頁。用擴大路徑法證明用擴大路徑法證明.情況一：情況一： +. 證明證明D中存在長度中存在長度(chngd) +1的圈的圈. 設設 = v0v1vl為極大路徑，則為極大路徑，則l (為什么為什么?)