圖論基本概念PPT課件

1、1緒論 圖論的作用：l 圖與計算機：計算機中數(shù)據(jù)結(jié)構(gòu)，離不開數(shù)組、串、各種鏈接表、樹和圖，因此圖是計算機中數(shù)據(jù)表示、存儲和運算的基礎(chǔ) l 圖與網(wǎng)絡(luò)： 最大流問題：假設(shè)從城市P到城市Q的一個公路網(wǎng)， 公路網(wǎng)中每段公路上每天可以通過的汽車的數(shù)量有上限，那么經(jīng)過該公路網(wǎng)，每天最多可以有多少輛汽車從城市P開到城市Q？ 最優(yōu)支撐樹問題：某一地區(qū)有若干個主要城市，擬修建高速公路把這些城市連接起來，使得從其中任何一個城市都可以經(jīng)高速公路直接或間接到達另一個城市。假設(shè)已經(jīng)知道了任意兩個城市之間修建高速公路的成本，那么應(yīng)如何決定在哪些城市間修建高速公路，使得總成本最小？第1頁/共52頁2第十四章 圖的基本概念

2、主要內(nèi)容l 圖l 通路與回路l 圖的連通性l 圖的矩陣表示l 圖的運算 預(yù)備知識l 多重集合元素可以重復出現(xiàn)的集合l 無序集AB=(x,y) | xAyB第2頁/共52頁314.1 圖定義14.1 無向圖G = , 其中(1) V 為頂點集，元素稱為頂點 Vertex(2) E為VV 的多重集，其元素稱為無向邊，簡稱邊 Edge實例 設(shè) V = v1, v2, ,v5, E = (v1,v1), (v1,v2), (v2,v3), (v2,v3), (v2,v5), (v1,v5), (v4,v5) 則 G = 為一無向圖第3頁/共52頁4有向圖定義14.2 有向圖D=, 只需注意E是VV 的

3、多重子集圖2表示的是一個有向圖，試寫出它的V 和 E 注意：圖的數(shù)學定義與圖形表示，在同構(gòu)（待敘）的意義下是一一對應(yīng)的第4頁/共52頁5相關(guān)概念1. 圖 可用G泛指圖（無向的或有向的） V(G), E(G), |V(G)|, |E(G)| n階圖：n 個頂點的圖2. 有限圖3. n 階零圖（0條邊）與平凡圖（1個頂點）4. 空圖（運算中出現(xiàn)）5. 用 ek 表示無向邊或有向邊第5頁/共52頁6相關(guān)概念6. 頂點與邊的關(guān)聯(lián)關(guān)系 關(guān)聯(lián)、關(guān)聯(lián)次數(shù) 環(huán) 孤立點7. 頂點之間的相鄰與鄰接關(guān)系第6頁/共52頁7)()()(),()(|)(vvNvNvvuGEvuGVuuvNv 的的閉閉鄰鄰域域的的鄰鄰域域

4、)(|)(關(guān)關(guān)聯(lián)聯(lián)與與veGEeevI )()()()()()(,)(|)()(,)(|)(vvNvNvvvvNvvuDEvuDVuuvvvuDEuvDVuuvvDDDDDDD 的的閉閉鄰鄰域域的的鄰鄰域域的的先先驅(qū)驅(qū)元元集集的的后后繼繼元元集集8. 鄰域與關(guān)聯(lián)集 v V(G) (G為無向圖) v 的關(guān)聯(lián)集 v V(D) (D為有向圖)9. 標定圖與非標定圖(頂點和邊指定編號的）10. 基圖（有向圖的有向邊改為無向邊）相關(guān)概念第7頁/共52頁8多重圖與簡單圖 定義14.3 (1) 無向圖中的平行邊及重數(shù) 關(guān)聯(lián)一對頂點的邊多于一條，條數(shù)稱為重數(shù) (2) 有向圖中的平行邊及重數(shù)（注意方向性） (3

5、) 多重圖 (4) 簡單圖（無平行邊和環(huán)） 簡單圖是極其重要的概念 第8頁/共52頁9頂點的度數(shù)定義14.4 (1) 設(shè)G=為無向圖, vV, d(v)v的度數(shù), 簡稱度 (2) 設(shè)D=為有向圖, vV, d+(v)v的出度 d(v)v的入度 d(v)v的度或度數(shù) (3) (G)（最大度）, (G)（最小度） 無向圖中 (4) +(D), +(D), (D), (D), (D), (D) (5) 度數(shù)為1的點稱為懸掛點，關(guān)聯(lián)的邊為懸掛邊； 奇頂點度與偶度頂點第9頁/共52頁10mvdnii2)(1 mvdvdmvdniiniinii 111)()(,2)(且且定理定理14.1 設(shè)設(shè)G=為任意無

6、向圖，為任意無向圖，V=v1,v2,vn, |E|=m, 則則證 G中每條邊 (包括環(huán)) 均有兩個端點，所以在計算G中各頂點度數(shù)之和時，每條邊均提供2度，m 條邊共提供 2m 度.此二定理是歐拉此二定理是歐拉17361736年給出，是圖論的基本定理年給出，是圖論的基本定理握手定理定理14.2 設(shè)D=為任意有向圖，V=v1,v2,vn, |E|=m, 則第10頁/共52頁11握手定理推論 推論 任何圖 (無向或有向) 中，奇度頂點的個數(shù)是偶數(shù). 證 設(shè)G=為任意圖，令 V1=v | vV d(v)為奇數(shù) V2=v | vV d(v)為偶數(shù) 則V1V2=V, V1V2=，由握手定理可知 由于2m,

7、 均為偶數(shù)，所以 為偶數(shù)，但因為V1中 頂點度數(shù)為奇數(shù)，所以|V1|必為偶數(shù). 21)()()(2VvVvVvvdvdvdm 2)(Vvvd 1)(Vvvd第11頁/共52頁12圖的度數(shù)列1 . V=v1, v2, , vn為無向圖G的頂點集，稱d(v1), d(v2), , d(vn)為G的度數(shù)列 2. V=v1, v2, , vn為有向圖D的頂點集， D的度數(shù)列：d(v1), d(v2), , d(vn) D的出度列：d+(v1), d+(v2), , d+(vn) D的入度列：d(v1), d(v2), , d(vn) 3. 非負整數(shù)列d=(d1, d2, , dn)是可圖化的，是可簡單

8、圖化的.易知：(2, 4, 6, 8, 10)，(1, 3, 3, 3, 4) 是可圖化的，后者又是可簡單圖化的，而(2, 2, 3, 4, 5)，(3, 3, 3, 4) 都不是可簡單圖化的，特別是后者也不是可圖化的第12頁/共52頁13圖的同構(gòu) 定義14.5 設(shè)G1=, G2=為兩個無向圖(兩個有向 圖)，若存在雙射函數(shù)f:V1V2, 對于vi,vjV1, (vi,vj)E1 當且僅當 (f(vi),f(vj)E2 （E1 當且僅當 E2 ) 并且, (vi,vj)（）與 (f(vi),f(vj)（）的重數(shù)相 同，則稱G1與G2是同構(gòu)的，記作G1G2. l 圖之間的同構(gòu)關(guān)系具有自反性、對稱

9、性和傳遞性.l 能找到多條同構(gòu)的必要條件，但它們?nèi)皇浅浞謼l件： 邊數(shù)相同，頂點數(shù)相同; 度數(shù)列相同; 對應(yīng)頂點的關(guān)聯(lián)集及鄰域的元素個數(shù)相同，等等 若破壞必要條件，則兩圖不同構(gòu)l 判斷兩個圖同構(gòu)是個難題第13頁/共52頁14圖同構(gòu)的實例 圖中(1)與(2)的度數(shù)列相同，它們同構(gòu)嗎？為什么？ (1) (2) (3) (4) 圖中，(1)與(2)不同構(gòu)（度數(shù)列不同），(3)與(4)也不同構(gòu). (1) (2) 第14頁/共52頁15n 階完全圖與競賽圖 定義14.6 (1) n (n1) 階無向完全圖每個頂點與其余頂點均相鄰的無向簡單圖，記作 Kn. 簡單性質(zhì)：邊數(shù) (2) n (n1)階有向完全圖

10、每對頂點之間均有兩條方向相反的有向邊的有向簡單圖. 簡單性質(zhì)： (3) n (n1) 階競賽圖基圖為Kn的有向簡單圖. 簡單性質(zhì)：邊數(shù)1,2)1( nnnm 1),1(2),1( nnnnm 1,2)1( nnnm 第15頁/共52頁16n 階 k 正則圖 (1)為K5，(2)為3階有向完全圖，(3)為4階競賽圖. (1) (2) (3)定義14.7 n 階k正則圖 = =k 的無向簡單圖簡單性質(zhì)：邊數(shù)（由握手定理得）Kn是 n 1正則圖，彼得松圖（見書上圖14.3(1) 所示，記住它）2nkm 第16頁/共52頁17子圖 定義14.8 G=, G= (1) GG G為G的子圖，G為G的母圖

11、(2) 若GG且V=V，則稱G為G的生成子圖 (3) 若VV或EE，稱G為G的真子圖 (4) V（VV且V）的導出子圖，記作GV (5) E（EE且E）的導出子圖，記作GE第17頁/共52頁18例2 畫出K4的所有非同構(gòu)的生成子圖實例第18頁/共52頁19補圖定義14.9 設(shè)G=為n階無向簡單圖，以V為頂點集，以所有使G成為完全圖Kn的添加邊組成的集合為邊集的圖，稱為G的補圖，記作 .若G , 則稱G是自補圖. 相對于K4, 求上面圖中所有圖的補圖，并指出哪些是自補圖. 問：互為自補圖的兩個圖的邊數(shù)有何關(guān)系？GG第19頁/共52頁2014.2 通路與回路定義14.11 給定圖G=（無向或有向的

12、），G中頂點與邊的交替序列 = v0e1v1e2elvl，vi1, vi 是 ei 的端點.(1) 通路與回路： 為通路；若 v0=vl， 為回路，l 為回路長 度.(2) 簡單通路與回路：所有邊各異， 為簡單通路，又若v0=vl， 為簡單回路(3) 初級通路(路徑)與初級回路(圈)： 中所有頂點各異，則稱 為初級通路(路徑)，又若除v0=vl，所有的頂點各不相同且所有的邊各異，則稱 為初級回路(圈)(4) 復雜通路與回路：有邊重復出現(xiàn)第20頁/共52頁21幾點說明 表示法 定義表示法 只用邊表示法 只用頂點表示法（在簡單圖中） 混合表示法 環(huán)（長為1的圈）的長度為1，兩條平行邊構(gòu)成的圈長度為

13、 2，無向簡單圖中，圈長3，有向簡單圖中圈的長度2. 不同的圈（以長度3的為例） 定義意義下 無向圖：圖中長度為l（l3）的圈，定義意義下為2l個 有向圖：圖中長度為l（l3）的圈，定義意義下為l個 同構(gòu)意義下：長度相同的圈均為1個 試討論l=3和l=4的情況第21頁/共52頁22通路與回路的長度 定理14.5 在n 階圖G中，若從頂點vi 到vj（vivj）存在通路， 則從vi 到 vj 存在長度小于或等于n1 的通路. 推論 在 n 階圖G中，若從頂點vi 到 vj（vivj）存在通路，則 從vi 到vj 存在長度小于或等于n1的初級通路（路徑）. 定理14.6 在一個n 階圖G中，若存在

14、 vi 到自身的回路，則一 定存在vi 到自身長度小于或等于 n 的回路. 推論 在一個n 階圖G中，若存在 vi 到自身的簡單回路，則一 定存在長度小于或等于n 的初級回路.第22頁/共52頁2314.3 圖的連通性無向圖的連通性(1) 頂點之間的連通關(guān)系：G=為無向圖 若 vi 與 vj 之間有通路，則 vivj 是V上的等價關(guān)系 R=| u,v V且uv (2) G的連通性與連通分支 若u,vV，uv，則稱G連通 V/R=V1,V2,Vk，稱GV1, GV2, ,GVk為連通分 支，其個數(shù) p(G)=k (k1)； k=1，G連通第23頁/共52頁24短程線與距離 (3) 短程線與距離

15、u與v之間的短程線：uv，u與v之間長度最短的通路 u與v之間的距離：d(u,v)短程線的長度 d(u,v)的性質(zhì)： d(u,v)0, u v時d(u,v)= d(u,v)=d(v,u) d(u,v)+d(v,w)d(u,w)第24頁/共52頁25無向圖的連通度1. 刪除頂點及刪除邊 Gv 從G中將v及關(guān)聯(lián)的邊去掉 GV從G中刪除V中所有的頂點 Ge 將e從G中去掉 GE刪除E中所有邊 2. 點割集與邊割集 點割集與割點定義14.16 G=, VV V為點割集p(GV)p(G)且有極小性 v為割點v為點割集定義14.17 G=, EE E是邊割集p(GE)p(G)且有極小性 e是割邊（橋）e為

16、邊割集第25頁/共52頁26點割集與割點 例3 v1,v4，v6是點 割集，v6是割點. v2,v5 是點割集嗎？ e1,e2，e1,e3,e5,e6， e8等是邊割集，e8是 橋，e7,e9,e5,e6 是邊割 集嗎？幾點說明：l Kn中無點割集，Nn中既無點割集，也無邊割集，其中Nn為 n 階零圖. l 若G 連通，E 為邊割集，則 p(G E )=2，V 為點割集，則 p(G V ) 2 第26頁/共52頁27點連通度與邊連通度 定義14.18 G為連通非完全圖 點連通度 (G) = min |V |V 為點割集 規(guī)定 (Kn) = n1 若G非連通，(G) = 0 若 (G)k，則稱G

17、為 k-連通圖 定義14.19 設(shè)G為連通圖 邊連通度(G) = min|E|E為邊割集 若G非連通，則(G) = 0 若(G)r，則稱G是 r 邊-連通圖 圖中， =1，它是 1-連通圖 和 1邊-連通圖第27頁/共52頁28幾點說明l (Kn)=(Kn)=n1l G非連通，則 =0l 若G中有割點，則=1，若有橋，則=1l 若(G)=k, 則G是1-連通圖，2-連通圖，k-連通圖，但不是(k+s)-連通圖，s1l 若(G)=r, 則G是1-邊連通圖，2-邊連通圖，r-邊連通圖，但不是(r+s)-邊連通圖，s1l , , 之間的關(guān)系. 定理7.5 (G)(G)(G) 請畫出一個的無向簡單圖第

18、28頁/共52頁29有向圖的連通性 定義14.20 D=為有向圖 vi vj（vi 可達 vj）vi 到vj 有通路 vi vj（vi 與vj 相互可達） 性質(zhì) 具有自反性(vi vi)、傳遞性 具有自反性、對稱性、傳遞性 vi 到vj 的短程線與距離 類似于無向圖中，只需注意距離表示法的不同 (無向圖中d(vi,vj)，有向圖中d) 及 d無對稱性第29頁/共52頁30有向圖的連通性及分類 定義14.22 D=為有向圖 D弱連通(連通)基圖為無向連通圖 D單向連通vi,vjV，vivj 或 vjvi D強連通vi,vjV，vivj 易知，強連通單向連通弱連通 判別法 定理14.8 D強連通當

19、且僅當D中存在經(jīng)過每個頂點至少一次 的回路 定理14.9 D單向連通當且僅當D中存在經(jīng)過每個頂點至少一 次的通路第30頁/共52頁31擴大路徑法無向圖中設(shè)G=為 n 階無向圖，E. 設(shè) l 為G中一條路徑，若此路徑的始點或終點與通路外的頂點相鄰，就將它們擴到通路中來，繼續(xù)這一過程，直到最后得到的通路的兩個端點不與通路外的頂點相鄰為止. 設(shè)最后得到的路徑為l+k（長度為 l 的路徑擴大成了長度為 l+k 的路徑），稱l+k為“極大路徑”，稱使用此種方法證明問題的方法為“擴大路徑法”.有向圖中類似討論，只需注意，在每步擴大中保證有向邊方向的一致性.第31頁/共52頁32實例由某條路徑擴大出的極大路

20、徑不惟一，極大路徑不一定是圖中最長的路徑上圖中，(1)中實線邊所示的長為2的初始路徑，(2),(3),(4)中實線邊所示的都是它擴展成的極大路徑. 還能找到另外的極大路徑嗎？ (1) (2) (4) (3)第32頁/共52頁33擴大路徑法的應(yīng)用 例4 設(shè) G 為 n（n3）階無向簡單圖， 2，證明G 中存在 長度 +1 的圈.證 設(shè) = v0v1vl 是由初始路徑 0 用擴大路徑法的得到的極大路徑，則 l （為什么？）. 因為v0 不與 外頂點相鄰，又 d(v0) ，因而在 上除 v1外，至少還存在 1個頂點與 v0 相鄰. 設(shè) vx 是離 v0 最遠的頂點，于是 v0v1vxv0 為 G 中

21、長度 +1 的圈. 第33頁/共52頁34二部圖定義14.23 設(shè) G=為一個無向圖，若能將 V分成 V1和V2(V1V2=V，V1V2=)，使得 G 中的每條邊的兩個端點都是一個屬于V1，另一個屬于V2，則稱 G 為二部圖 ( 或稱二分圖、偶圖等 )，稱V1和V2為互補頂點子集，常將二部圖G記為. 又若G是簡單二部圖，V1中每個頂點均與V2中所有的頂點相鄰，則稱G為完全二部圖，記為 Kr,s，其中r=|V1|，s=|V2|. 注意，n 階零圖為二部圖. 第34頁/共52頁35二部圖的判別法 定理14.10 無向圖G=是二部圖當且僅當G中無奇圈 由定理14.10可知圖9中各圖都是二部圖，哪些是

22、完全二部 圖？哪些圖是同構(gòu)的？第35頁/共52頁3614.4 圖的矩陣表示 無向圖的關(guān)聯(lián)矩陣（對圖無限制） 定義14.24 無向圖G=，|V|=n，|E|=m，令 mij為 vi 與 ej 的關(guān)聯(lián)次數(shù)，稱(mij)nm為G 的關(guān)聯(lián)矩陣，記為M(G). 性質(zhì)平行邊的列相同平行邊的列相同)4(2)3(),.,2 , 1()()2(),.,2 , 1(2)1(,11mmnivdmmjmjiijimjijniij 第36頁/共52頁37 jiijmjmjiijiijniijmnivdmvdmmjm,1110)3(,.,2 , 1),()1(),()1()2(),.,2 , 1(0)1( 的的終終點點為

23、為，不不關(guān)關(guān)聯(lián)聯(lián)與與，的的始始點點為為jijijiijevevevm10,1有向圖的關(guān)聯(lián)矩陣（無環(huán)有向圖） 定義定義14.25 有向圖D=，令則稱 (mij)n m為D的關(guān)聯(lián)矩陣，記為M(D). (4) 平行邊對應(yīng)的列相同平行邊對應(yīng)的列相同性質(zhì)有向圖的關(guān)聯(lián)矩陣第37頁/共52頁38有向圖的鄰接矩陣（無限制）定義14.26 設(shè)有向圖D=, V=v1, v2, , vn, E=e1, e2, , em, 令為頂點 vi 鄰接到頂點 vj 邊的條數(shù)，稱為D的鄰接矩陣，記作A(D)，或簡記為A. 性質(zhì) 的回路數(shù)的回路數(shù)中長度為中長度為的通路數(shù)的通路數(shù)中長度為中長度為1)4(1)3(,.,2 , 1),

24、()2(,.,2 , 1),()1(1)1(,)1(1)1(1)1(DaDmanjvdanivdaniiijiijjniijinjij 第38頁/共52頁39推論 設(shè)Bl=A+A2+Al（l 1），則 Bl中元素為D中長度為 l 的通路總數(shù)，)(lija)(liia ninjlija11)( niliia1)( ninjlijb11)( niliib1)(定理14.11 設(shè) A為有向圖 D 的鄰接矩陣，V=v1, v2, , vn為頂點集，則 A 的 l 次冪 Al（l 1）中元素為D中vi 到vj長度為 l 的通路數(shù)，其中為vi到自身長度為 l 的回路數(shù)，而為D中長度小于或等于 l 的回路數(shù)

25、為D中長度小于或等于 l 的通路數(shù). 鄰接矩陣的應(yīng)用為D 中長度為 l 的回路總數(shù). 第39頁/共52頁40例5 有向圖D如圖所示，求 A, A2, A3, A4，并回答諸問題：(1) D 中長度為1, 2, 3, 4的通路各有多少條？其中回路分別為多少條？(2) D 中長度小于或等于4的通路為多少條？其中有多少條回路？實例第40頁/共52頁41 1004010410050001010310030104000110020102100300010101100101020001432AAAA(1) D中長度為1的通路為8條，其中有1條是回路. D中長度為2的通路為11條，其中有3條是回路. D中長

26、度為3和4的通路分別為14和17條，回路分別 為1與3條.(2) D中長度小于等于4的通路為50條，其中有8條是回路.實例求解第41頁/共52頁42 否否則則可可達達, 1, 0jiijvvp 1101110111110001P定義14.27 設(shè)D=為有向圖. V=v1, v2, , vn, 令 有向圖的可達矩陣（無限制）稱 (pij)n n 為D的可達矩陣，記作P(D)，簡記為P. 由于 vi V，vivi，所以P(D)主對角線上的元素全為1. 由定義不難看出, D 強連通當且僅當 P(D)為全1矩陣. 下圖所示有向圖 D 的可達矩陣為第42頁/共52頁43第十四章 習題課 主要內(nèi)容l 無向

27、圖、有向圖、關(guān)聯(lián)與相鄰、簡單圖、完全圖、正則圖、子圖、補圖；握手定理與推論；圖的同構(gòu)l 通路與回路及其分類l 無向圖的連通性與連通度l 有向圖的連通性及其分類l 圖的矩陣表示第43頁/共52頁44基本要求l 深刻理解握手定理及推論的內(nèi)容并能靈活地應(yīng)用它們l 深刻理解圖同構(gòu)、簡單圖、完全圖、正則圖、子圖、補圖、二部圖的概念以及它們的性質(zhì)及相互之間的關(guān)系l 記住通路與回路的定義、分類及表示法l 深刻理解與無向圖連通性、連通度有關(guān)的諸多概念l 會判別有向圖連通性的類型l 熟練掌握用鄰接矩陣及其冪求有向圖中通路與回路數(shù)的方法，會求可達矩陣 第44頁/共52頁4519階無向圖G中，每個頂點的度數(shù)不是5就

28、是6. 證明G中至少有5個6度頂點或至少有6個5度頂點. 練習1證 關(guān)鍵是利用握手定理的推論. 方法一：窮舉法設(shè)G中有x個5度頂點，則必有(9 x)個6度頂點，由握手定理推論可知，(x,9 x)只有5種可能：(0,9), (2,7), (4,5), (6,3), (8,1）它們都滿足要求. 方法二：反證法否則，由握手定理推論可知，“G至多有4個5度頂點并且至多有4個6度頂點”，這與G是 9 階圖矛盾. 第45頁/共52頁462數(shù)組2, 2, 2, 2, 3, 3能簡單圖化嗎？若能，畫出盡可能多的非同構(gòu)的圖來. 練習2只要能畫出6 階無向簡單圖，就說明它可簡單圖化. 下圖的4個圖都以此數(shù)列為度數(shù)列，請證明它們彼此不同構(gòu)，都是K6的子圖.第46頁/共52頁47用擴大路徑法證明.情況一： +. 證明D中存在長度 +1的圈. 設(shè) = v0v1vl為極大路