離散數(shù)學(xué)第十四章

1、1,14.3 圖的連通性,無向圖的連通性(1) 頂點之間的連通關(guān)系：G=為無向圖 ① 若 vi 與 vj 之間有通路，則 vi?vj ② ?是V上的等價關(guān)系 R={| u,v ?V且u?v} (2) G的連通性與連通分支 ① 若?u,v?V，u?v，則稱G連通 ② V/R={V1,V2,…,Vk}，稱G[V1], G[V2], …,G[Vk]為連通分 支，其個數(shù)

2、 p(G)=k (k?1)； k=1，G連通,2,短程線與距離,(3) 短程線與距離 ① u與v之間的短程線：u?v，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)+

3、d(v,w)?d(u,w),3,無向圖的連通度,1. 刪除頂點及刪除邊 G?v ——從G中將v及關(guān)聯(lián)的邊去掉 G?V?——從G中刪除V?中所有的頂點 G?e ——將e從G中去掉 G?E?——刪除E?中所有邊 2. 點割集與邊割集 點割集與割點定義14.16 G=, V??V V?為點割集——p(G?V?)>p(G)且有極小性 v為割點——{v}為點

4、割集定義14.17 G=, E??E E?是邊割集——p(G?E?)>p(G)且有極小性 e是割邊（橋）——{e}為邊割集,4,點割集與割點,例3 {v1,v4}，{v6}是點割集，v6是割點. {v2,v5}是點割集嗎？{e1,e2}，{e1,e3,e5,e6}，{e8}等是邊割集，e8是橋，{e7,e9,e5,e6} 是邊割集嗎？,幾點說明：Kn中無點割集，Nn中既無點割集，也無邊

5、割集，其中Nn為 n 階零圖. 若G 連通，E?為邊割集，則 p(G?E?)=2，V?為點割集，則 p(G?V?)?2,5,點連通度與邊連通度,定義14.18 G為連通非完全圖 點連通度— ?(G) = min{ |V ?|?V ?為點割集 } 規(guī)定 ?(Kn) = n?1? 若G非連通，?(G) = 0? 若 ?(G)?k，則稱G為 k-連通圖 定義14.19 設(shè)G為連通圖 邊連通度——

6、?(G) = min{|E?|?E?為邊割集} 若G非連通，則?(G) = 0 若?(G)?r，則稱G是 r 邊-連通圖圖中， ?=?=1，它是 1-連通圖 和 1邊-連通圖,6,幾點說明,?(Kn)=?(Kn)=n?1G非連通，則 ?=?=0若G中有割點，則?=1，若有橋，則?=1若?(G)=k, 則G是1-連通圖，2-連通圖，…，k-連通圖，但不是(k+s)-連通圖，s?1若?(G)=r, 則G是1-邊連

7、通圖，2-邊連通圖，…，r-邊連通圖，但不是(r+s)-邊連通圖，s?1?, ?, ?之間的關(guān)系.定理7.5 ?(G)??(G)??(G)請畫出一個?<?<?的無向簡單圖,7,有向圖的連通性,定義14.20 D=為有向圖 vi ? vj（vi 可達 vj）——vi 到vj 有通路 vi ? vj（vi 與vj 相互可達）性質(zhì) ? 具有自反性(vi ? vi)、傳遞性

8、? 具有自反性、對稱性、傳遞性 vi 到vj 的短程線與距離類似于無向圖中，只需注意距離表示法的不同(無向圖中d(vi,vj)，有向圖中d) 及 d無對稱性,8,有向圖的連通性及分類,定義14.22 D=為有向圖 D弱連通(連通)——基圖為無向連通圖 D單向連通——?vi,vj?V，vi?vj 或 vj?vi D強連通——?vi,vj?V，vi?vj易知，強連通?單向連通?弱連通判別法定理1

9、4.8 D強連通當(dāng)且僅當(dāng)D中存在經(jīng)過每個頂點至少一次的回路定理14.9 D單向連通當(dāng)且僅當(dāng)D中存在經(jīng)過每個頂點至少一次的通路,實例,10,二部圖,定義14.23 設(shè) G=為一個無向圖，若能將 V分成 V1和V2(V1?V2=V，V1?V2=?)，使得 G 中的每條邊的兩個端點都是一個屬于V1，另一個屬于V2，則稱 G 為二部圖 ( 或稱二分圖、偶圖等 )，稱V1和V2為互補頂點子集，常將二部圖G記為. 又若G是簡單

10、二部圖，V1中每個頂點均與V2中所有的頂點相鄰，則稱G為完全二部圖，記為 Kr,s，其中r=|V1|，s=|V2|. 注意，n 階零圖為二部圖.,11,,一個無向圖G = 是二部圖當(dāng)且僅當(dāng)G中無奇數(shù)長度的回路。,二部圖判定定理,若|V1| = n，|V2| = m，則記完全二部圖G為Kn, m,圈的長度都是偶數(shù),12,例1：判斷下列圖是否為二部圖。,同構(gòu)于,同構(gòu)于,13,14.4 圖的矩陣表示,無向圖的關(guān)聯(lián)矩陣（對圖無限制）

11、定義14.24 無向圖G=，|V|=n，|E|=m，令 mij為 vi 與 ej的關(guān)聯(lián)次數(shù)，稱(mij)n?m為G 的關(guān)聯(lián)矩陣，記為M(G). mij 的可能取值為0,1,2.性質(zhì),無向圖的關(guān)聯(lián)矩陣,例如,15,有向圖的關(guān)聯(lián)矩陣（無環(huán)有向圖）,定義14.25 有向圖D=，令則稱 (mij)n?m為D的關(guān)聯(lián)矩陣，記為M(D).,(4) 平行邊對應(yīng)的列相同,性質(zhì),有向圖的關(guān)聯(lián)矩陣,實例,,17,有向圖的鄰接矩陣（無限制）,定義14

12、.26 設(shè)有向圖D=, V={v1, v2, …, vn}, E={e1, e2, …, em}, 令為頂點 vi 鄰接到頂點 vj 邊的條數(shù)，稱為D的鄰接矩陣，記作A(D)，或簡記為A. 性質(zhì),18,推論 設(shè)Bl=A+A2+…+Al（l?1），則 Bl中元素,為D中長度為 l 的通路總數(shù)，,定理14.11 設(shè) A為有向圖 D 的鄰接矩陣，V={v1, v2, …, vn}為頂點集，則 A 的 l 次冪 A

13、l（l?1）中元素,為D中vi 到vj長度為 l 的通路數(shù)，其中,為vi到自身長度為 l 的回路數(shù)，而,為D中長度小于或等于 l 的回路數(shù),為D中長度小于或等于 l 的通路數(shù).,鄰接矩陣的應(yīng)用,為D 中長度為 l 的回路總數(shù).,19,例5 有向圖D如圖所示，求 A, A2, A3, A4，并回答諸問題：(1) D 中長度為1, 2, 3, 4的通路各有多少條？其中回路分別為多少條？(2) D 中長度小于或等于4的通路為多少條？其中

14、有多少條回路？,實例,20,,(1) D中長度為1的通路為8條，其中有1條是回路. D中長度為2的通路為11條，其中有3條是回路. D中長度為3和4的通路分別為14和17條，回路分別 為1與3條.(2) D中長度小于等于4的通路為50條，其中有8條是回路.,實例求解,21,定義14.27 設(shè)D=為有向圖. V={v1, v2, …, vn}, 令,有向圖的可達矩陣（無限制）,稱 (pij)n?n

15、為D的可達矩陣，記作P(D)，簡記為P. 由于?vi?V，vi?vi，所以P(D)主對角線上的元素全為1. 由定義不難看出, D 強連通當(dāng)且僅當(dāng) P(D)為全1矩陣. 下圖所示有向圖 D 的可達矩陣為,2、邊不相交的,G1=,G2=,,同為無向圖或同為有向圖,G1與G2是不相交的,,E1∩E2 = φ,V1∩V2 =φ,G1與G2是邊不相交,E1∩E2 = φ,4、圖的交,G1=,G2=,,是可運算的,V1∩V2為結(jié)點集,E1∩

16、E2為邊集合,,G1和G2的交,G1∩G2,5、圖的并,G1=,G2=,,是可運算的,V1 ∪ V2為結(jié)點集,E1 ∪ E2為邊集合,,G1和G2的并,G1 ∪ G2,6、圖的差,G1=,G2=,,是可運算的,G1與G2的差:,在G1中去掉G2的邊所得到的圖,G1 - G2,7、圖的環(huán)和,G1=,G2=,,是可運算的,V1 ∪ V2為結(jié)點集,E1 ⊕ E2為邊集合,,G1和G2的環(huán)和,G1 ⊕ G2,圖運算的舉例,與如下圖所示，求：G

17、1∩G2 G1∪G2 G1-G2 G2-G1 ， G1⊕G2 。,G1∩G2,V1∩V2,,E1∩E2,={a,b,d},= {e1,e2,e5},G1∪G2,V1∪V2,,{e1,e2,e3 , e4,e5,e6 ,e7 , e8,e9,e10},={a,b,c,d,e},E1∪E2 =,G1 -G2,,G2 –G1,,G1⊕G2,E1 ⊕ E2 =,,V1∪V2,={a,b,c,d,e},{e3 , e4,e6 ,e7 ,

18、e8,e9,e10},33,第十四章 習(xí)題課,主要內(nèi)容無向圖、有向圖、關(guān)聯(lián)與相鄰、簡單圖、完全圖、正則圖、子圖、補圖；握手定理與推論；圖的同構(gòu)通路與回路及其分類無向圖的連通性與連通度有向圖的連通性及其分類圖的矩陣表示,34,基本要求,深刻理解握手定理及推論的內(nèi)容并能靈活地應(yīng)用它們深刻理解圖同構(gòu)、簡單圖、完全圖、正則圖、子圖、補圖、二部圖的概念以及它們的性質(zhì)及相互之間的關(guān)系記住通路與回路的定義、分類及表示法深刻理解與無向圖

19、連通性、連通度有關(guān)的諸多概念會判別有向圖連通性的類型熟練掌握用鄰接矩陣及其冪求有向圖中通路與回路數(shù)的方法，會求可達矩陣,35,1．9階無向圖G中，每個頂點的度數(shù)不是5就是6. 證明G中至少有5個6度頂點或至少有6個5度頂點.,練習(xí)1,證 關(guān)鍵是利用握手定理的推論. 方法一：窮舉法設(shè)G中有x個5度頂點，則必有(9?x)個6度頂點，由握手定理推論可知，(x,9?x)只有5種可能：(0,9), (2,7), (4,5), (6,3

20、), (8,1）它們都滿足要求. 方法二：反證法否則，由握手定理推論可知，“G至多有4個5度頂點并且至多有4個6度頂點”，這與G是 9 階圖矛盾.,36,2．?dāng)?shù)組2, 2, 2, 2, 3, 3能簡單圖化嗎？若能，畫出盡可能多的非同構(gòu)的圖來.,練習(xí)2,只要能畫出6 階無向簡單圖，就說明它可簡單圖化. 下圖的4個圖都以此數(shù)列為度數(shù)列，都是K6的子圖.,37,用擴大路徑法證明.情況一：?? ? ?+. 證明D中存在長度 ? ??+1的

21、圈. 設(shè) ? = v0v1…vl為極大路徑，則l ? ??(為什么?).由于d?(v0)? ??，所以在 ? 上存在,,,,,PLAY,鄰接到v0，于是,情況二：?+ ? ??，只需注意d+(vl) ? ? + .,3．設(shè)D=為有向簡單圖，已知 ?(D) ? 2，?+(D)>0，??(D)>0，證明D中存在長度 ? max{?+,??}+1的圈.,為D中長度 ? ??+1的有向圈,練習(xí)3,38,(1) D中有幾種非同構(gòu)的圈

22、？(2) D中有幾種非圈非同構(gòu)的簡單回路？(3) D是哪類連通圖?(4) D中v1到v4長度為1,2,3,4的通路各多少 條？其中幾條是非初級的簡單通路？(5) D中v1到v1長度為1,2,3,4的回路各多少 條？討論它們的類型.(6) D中長度為4的通路（不含回路）有多少條？(7) D中長度為4的回路有多少條？(8) D中長度?4的通路有多少條？其中有幾條是回路？(9) 寫出D的可達矩陣.,4．有向

23、圖D如圖所示，回答下列諸問：,練習(xí)4,39,解答,(1) D中有3種非同構(gòu)的圈，長度分別為1,2,3，請畫出它們的圖形.(2) D中有3種非圈的非同構(gòu)的簡單回路，它們的長度分別為 4,5,6. 請畫出它們的圖形來.(3) D是強連通的（為什么？）為解(4)—(8)，只需先求D的鄰接矩陣的前4次冪.,40,(4) v1到v4長度為1,2,3,4的通路數(shù)分別為0,0,2,2. 其中只有長度為4的兩條是非初級的簡單通路（定義意義下），