高等數(shù)學(xué)-離散數(shù)學(xué)及其應(yīng)用-課件-第九章圖的基本概念

1、第三部分 圖論,1,本部分主要內(nèi)容 圖的基本概念 樹(shù) 歐拉圖與哈密頓圖 二部圖與匹配 平面圖 著色,第九章 圖的基本概念,主要內(nèi)容圖通路與回路圖的連通性圖的矩陣表示預(yù)備知識(shí)多重集合——元素可以重復(fù)出現(xiàn)的集合無(wú)序集——A?B={(x,y) | x?A?y?B},2,14.1 圖,定義9.1 無(wú)向圖G = , 其中(1) V為非空有窮集, 稱為頂點(diǎn)集，其元素稱為頂點(diǎn)(2) E為V?V 的多重有窮集

2、, 稱為邊集, 其元素稱為無(wú)向邊, 簡(jiǎn)稱邊例 無(wú)向圖G = , 其中 V = {v1, v2, v3, v4, v5}, E = {(v1,v1), (v1,v2), (v2,v3), (v2,v3), (v2,v5), (v1,v5), (v4,v5)},有向圖,定義9.2 有向圖D=,其中(1) V 為非空有窮集, 稱為頂點(diǎn)集，其元素稱為頂點(diǎn)(2) E為V?V 的多重有窮集, 稱為邊集, 其元素稱

3、為有向邊, 簡(jiǎn)稱邊例 有向圖D=, 其中V={a,b,c,d}E={,,,, ,,} 注意：圖的集合表示與圖形表示之間的對(duì)應(yīng),4,相關(guān)概念,1. 無(wú)向圖和有向圖通稱圖. 記頂點(diǎn)集V(G), 邊集E(G). 2. 圖的階, n階圖.3. n 階零圖Nn, 平凡圖N1.4. 空?qǐng)D?.5. 標(biāo)定圖與非標(biāo)定圖.6. 有向圖的基圖.7. 無(wú)向圖中頂點(diǎn)與邊的關(guān)聯(lián)及關(guān)聯(lián)次數(shù),

4、頂點(diǎn)與頂點(diǎn)、邊與 邊的相鄰關(guān)系.8. 有向圖中頂點(diǎn)與邊的關(guān)聯(lián), 頂點(diǎn)與頂點(diǎn)、邊與邊的相鄰關(guān) 系.9. 環(huán), 孤立點(diǎn).,5,多重圖與簡(jiǎn)單圖,定義9.3 無(wú)向圖中關(guān)聯(lián)同一對(duì)頂點(diǎn)的2條和2條以上的邊稱為平行邊. 有向圖中2條和2條以上始點(diǎn)、終點(diǎn)相同的邊稱為平行邊. 平行邊的條數(shù)稱為重?cái)?shù).含平行邊的圖稱為多重圖, 不含平行邊和環(huán)的圖稱為簡(jiǎn)單圖.定義9.4 設(shè)G=為無(wú)向圖, ?v?V, 稱v作為邊的端點(diǎn)的

5、次數(shù)之和為v的度數(shù), 簡(jiǎn)稱度, 記作d(v). 設(shè)D=為有向圖, ?v?V, 稱v作為邊的始點(diǎn)的次數(shù)之和為v的出度, 記作d+(v); 稱v作為邊的終點(diǎn)的次數(shù)之和為v的入度, 記作d?(v); 稱d+(v)+d?(v)為v的度數(shù), 記作d(v).,6,頂點(diǎn)的度數(shù),設(shè)G=為無(wú)向圖, G的最大度?(G)=max{d(v) | v?V} G的最小度 ?(G)=min{d(v) | v?V} 設(shè)D=為無(wú)

6、向圖, D的最大度?(D)=max{d(v) | v?V} D的最小度 ?(D)=min{d(v) | v?V} D的最大出度?+(D)=max{d+(v) | v?V} D的最小出度 ? +(D)=min{d+(v) | v?V} D的最大入度??(D)=max{d?(v) | v?V} D的最小入度 ? ?(D)=min{d?(v) | v?V} 懸掛頂點(diǎn): 度數(shù)為1

7、的頂點(diǎn), 懸掛邊: 與懸掛頂點(diǎn)關(guān)聯(lián)的邊.偶度(奇度)頂點(diǎn): 度數(shù)為偶數(shù)(奇數(shù))的頂點(diǎn),7,實(shí)例,d(v1)=4, d(v2)=4, d(v3)=2, d(v4)=1, d(v5)=3.?=4, ?=1.v4是懸掛點(diǎn), e7是懸掛邊.,8,d+(a)=4, d?(a)=1, d(a)=5, d+(b)=0, d?(b)=3, d(b)=3, d+(c)=2, d?(c)=1, d(c)=3, d+(d)=1,

8、d?(d)=2, d(d)=3, ?+=4, ? +=0, ??=3, ??=1, ?=5, ?=3.,9,定理9.1 在任何無(wú)向圖中, 所有頂點(diǎn)的度數(shù)之和等于邊數(shù)的2倍.,證 G中每條邊 (包括環(huán)) 均有兩個(gè)端點(diǎn)，所以在計(jì)算G中各頂點(diǎn)度數(shù)之和時(shí)，每條邊均提供2度，m 條邊共提供 2m 度.,握手定理,定理9.2 在任何有向圖中，所有頂點(diǎn)的度數(shù)之和等于邊數(shù)的2倍; 所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和, 都等于邊數(shù).,推論

9、任何圖 (無(wú)向或有向) 中，奇度頂點(diǎn)的個(gè)數(shù)是偶數(shù).證 由握手定理, 所有頂點(diǎn)的度數(shù)之和是偶數(shù), 而偶度頂點(diǎn)的度數(shù)之和是偶數(shù), 故奇度頂點(diǎn)的度數(shù)之和也是偶數(shù). 所以奇度頂點(diǎn)的個(gè)數(shù)必是偶數(shù)．,10,例1 無(wú)向圖G有16條邊，3個(gè)4度頂點(diǎn)，4個(gè)3度頂點(diǎn)，其余均為2度頂點(diǎn)度，問(wèn)G的階數(shù)n為幾？,解 本題的關(guān)鍵是應(yīng)用握手定理. 設(shè)除3度與4度頂點(diǎn)外，還有x個(gè)頂點(diǎn), 由握手定理, 16?2=32

10、 = 3?4+4?3+2x解得 x = 4, 階數(shù) n = 4+4+3=11.,握手定理應(yīng)用,定理9.3 設(shè)G為任意n階無(wú)向簡(jiǎn)單圖，則?(G)?n?1．,圖的同構(gòu),定義9.5 設(shè)G1=, G2=為兩個(gè)無(wú)向圖(兩個(gè)有向圖)，若存在雙射函數(shù)f:V1?V2, 使得?vi,vj?V1, (vi,vj)?E1 當(dāng)且僅當(dāng) (f(vi),f(vj))?E2 （?E1 當(dāng)且僅當(dāng) ?E2

11、)并且, (vi,vj)（）與 (f(vi),f(vj))（）的重?cái)?shù)相同，則稱G1與G2是同構(gòu)的，記作G1?G2.,圖同構(gòu)的實(shí)例,12,(1) (2) (3) (4),(1)與(2), (3)與(4), (5)與(6)均不同構(gòu).,(5) (6),說(shuō)明: 1. 圖的同構(gòu)關(guān)系具有自

12、反性、對(duì)稱性和傳遞性. 2. 判斷兩個(gè)圖同構(gòu)是個(gè)難題,圖同構(gòu)的實(shí)例,所有4階3條邊非同構(gòu)的簡(jiǎn)單無(wú)向圖,13,所有3階2條邊非同構(gòu)的簡(jiǎn)單有向圖,補(bǔ)圖與自補(bǔ)圖,定義9.6 設(shè)G=為n階無(wú)向簡(jiǎn)單圖，令 ={(u,v) | u?V?v?V?u?v?(u,v)?E},稱 =為G的補(bǔ)圖． 若G ? 則稱G是自補(bǔ)圖．,,,,例,(b)與(c)互為補(bǔ)圖，(a)是自補(bǔ)圖

13、．,完全圖與競(jìng)賽圖,定義9.7 (1) n (n?1) 階無(wú)向完全圖——每個(gè)頂點(diǎn)與其余頂點(diǎn)均相鄰的無(wú)向簡(jiǎn)單圖，記作 Kn.簡(jiǎn)單性質(zhì)：m=n(n-1)/2, ?=?=n-1(2) n (n?1)階有向完全圖——每對(duì)頂點(diǎn)之間均有兩條方向相反的有向邊的有向簡(jiǎn)單圖.簡(jiǎn)單性質(zhì)： m=n(n-1), ?=?=2(n-1) ?+=?+=??=??=n-1(3) n (n?1) 階競(jìng)賽圖——基圖

14、為Kn的有向簡(jiǎn)單圖.簡(jiǎn)單性質(zhì)： m=n(n-1)/2, ?=?=n-1,15,,,,正則圖,K5 3階有向完全圖 4階競(jìng)賽圖,定義9.8 k-正則圖——?=?=k 的無(wú)向簡(jiǎn)單圖簡(jiǎn)單性質(zhì)：m=kn/2, 當(dāng)k是奇數(shù)時(shí), n必為偶數(shù).例 Kn是 (n?1)-正則圖 彼得松圖是3-正則圖,,子圖,定義9.9 設(shè)兩個(gè)圖G=, G? =（同為無(wú)向圖或同為有向圖）,

15、若V??V且E??E，則稱G?是G的子圖，G為G? 母圖，記作G? ?G. 又若V??V或E??E，則稱G? 為G的真子圖. 若G? ?G且V?=V，則稱G? 為G的生成子圖． 設(shè)V1?V且V1??, 稱以V1為頂點(diǎn)集, 以G中兩個(gè)端點(diǎn)都在V1中的邊組成邊集的圖為G中V1的導(dǎo)出子圖, 記作G[V1]. 設(shè)E1?E且E1??, 稱以E1為邊集, 以E1中邊關(guān)聯(lián)的頂點(diǎn)為頂點(diǎn)集的圖為G中E1的導(dǎo)出子圖, 記作G[E1]．例

16、 G G[{a,b,c}] G[{e1,e3}],18,定義9.10 設(shè)G=為無(wú)向圖． (1) 設(shè)e?E，用G?e表示從G中去掉邊e，稱為刪除邊e．又設(shè)E??E，用 G?E? 表示從G中刪除E? 中的所有邊，稱為刪除E?． (2) 設(shè)v?V，用G?v表示從G中去掉v及所關(guān)聯(lián)的所有邊，稱為刪除頂點(diǎn)v．又設(shè)V? ?V，用G

17、?V? 表示從G中刪除V? 中所有的頂點(diǎn)，稱為刪除V?． (3) 設(shè)e=(u,v)?E，用G＼e表示從G中刪除e后，將e的兩個(gè)端點(diǎn)u,v用一個(gè)新的頂點(diǎn)w（可以用u或v充當(dāng)w）代替，并使w關(guān)聯(lián)除e以外u,v關(guān)聯(lián)的所有邊，稱為收縮邊e ． (4) 設(shè)u,v?V（u,v可能相鄰，也可能不相鄰），用G?(u,v)（或G+(u,v)）表示在u,v之間加一條邊(u,v)，稱為加新邊． 在收縮邊和加新邊過(guò)程中可能產(chǎn)生

18、環(huán)和平行邊．,刪除, 收縮與加新邊,實(shí)例,19,,9.2 通路與回路,定義9.11 設(shè)圖G= (無(wú)向或有向的), G中頂點(diǎn)與邊的交替序列 ? = v0e1v1e2…elvl，如果vi?1, vi 是 ei 的端點(diǎn)(始點(diǎn)和終點(diǎn)), 1?i?l, 則稱? 為v0到vl的通路. v0,vl分別稱作? 的始點(diǎn)和終點(diǎn). ? 中的邊數(shù)l稱作它的長(zhǎng)度. 又若 v0=vl, 則稱? 為回路. 若所有的邊各異, 則稱? 為簡(jiǎn)單通路. 又若v

19、0=vl, 則稱? 為簡(jiǎn)單回路. 若? 中所有頂點(diǎn)各異(除v0和vl可能相同外)且所有邊也各異, 則稱? 為初級(jí)通路或路徑. 若又有v0=vl, 則稱? 為初級(jí)回路或圈. 長(zhǎng)度為奇數(shù)的圈稱為奇圈, 長(zhǎng)度為偶數(shù)的圈稱為偶圈. 若? 中有邊重復(fù)出現(xiàn), 則? 稱為復(fù)雜通路. 若又有v0=vl, 則稱? 為復(fù)雜回路.,20,通路與回路,定理9.4 在n 階圖G中，若從頂點(diǎn)u 到v（u?v）存在通路，則從u 到 v 存在長(zhǎng)度

20、小于或等于n?1 的通路.推論 在 n 階圖G中，若從頂點(diǎn)u 到 v（u?v）存在通路，則從u 到v 存在長(zhǎng)度小于或等于n?1的初級(jí)通路（路徑）.定理9.5 在n 階圖G中，若存在 v 到自身的回路，則一定存在v 到自身長(zhǎng)度小于或等于 n 的回路.推論 在n 階圖G中，若存在 v 到自身的簡(jiǎn)單回路，則一定存在v 到自身的長(zhǎng)度小于或等于n 的初級(jí)回路.,21,同構(gòu)意義下和定義意義下的圈,例2 無(wú)向完全圖Kn（n?3）中

21、有幾種非同構(gòu)的圈？,22,解 長(zhǎng)度相同的圈都是同構(gòu)的. 易知Kn(n?3)中含長(zhǎng)度3,4,…,n的圈，共有n?2種非同構(gòu)的圈．,長(zhǎng)度相同的圈都是同構(gòu)的, 因此在同構(gòu)意義下給定長(zhǎng)度的圈只有一個(gè). 在標(biāo)定圖中, 圈表示成頂點(diǎn)和邊的標(biāo)記序列. 如果只要兩個(gè)圈的標(biāo)記序列不同, 稱這兩個(gè)圈在定義意義下不同.,例3 無(wú)向完全圖K3的頂點(diǎn)依次標(biāo)定為a,b,c．在定義意義下K3中有多少個(gè)不同的長(zhǎng)度為3的圈？,解 在定義意義下, 不同起點(diǎn)(

22、終點(diǎn))的圈是不同的, 頂點(diǎn)間排列順序不同的圈也是不同的, 因而K3中有3!=6個(gè)不同的長(zhǎng)為3的圈：abca，acba，bacb，bcab，cabc，cbac．,帶權(quán)圖與最短路徑,定義9.12 設(shè)圖G= (無(wú)向圖或有向圖), 對(duì)G的每一條邊e,給定一個(gè)數(shù)W(e),稱作邊e的權(quán). 把這樣的圖稱為帶權(quán)圖, 記作G=. 當(dāng)e=(u,v)()時(shí), 把W(e)記作W(u,v). 設(shè)P是G中的一條通路, P中所有邊的權(quán)之和稱為P的長(zhǎng)度,

23、記作W(P). 類似地, 可定義回路C的長(zhǎng)度W(C). 設(shè)帶權(quán)圖G= (無(wú)向圖或有向圖), 其中每一條邊e的權(quán)W(e)為非負(fù)實(shí)數(shù). ?u,v?V, 當(dāng)u和v連通(u可達(dá)v)時(shí), 稱從u到v長(zhǎng)度最短的路徑為從u到v的最短路徑, 稱其長(zhǎng)度為從u到v的距離, 記作d(u,v). 約定: d(u,u)=0; 當(dāng)u和v不連通(u不可達(dá)v)時(shí), d(u,v)=+?.,23,最短路問(wèn)題,最短路問(wèn)題: 給定帶權(quán)圖G=及頂點(diǎn)u和v, 其中每

24、一條邊e的權(quán)W(e)為非負(fù)實(shí)數(shù), 求從u到v的最短路徑.Dijkstra標(biāo)號(hào)法 (求從s到其余各點(diǎn)的最短路徑和距離)1. 令l(s)?(s,0), l(v)?(s,+?) (v?V-{s}), i?1, l(s)是永久標(biāo)號(hào), 其余標(biāo)號(hào)均為臨時(shí)標(biāo)號(hào), u?s2. for 與u關(guān)聯(lián)的臨時(shí)標(biāo)號(hào)的頂點(diǎn)v 3. if l2(u)+W(u,v)< l2(v) then 令l(v)?(u,l2(u)+W(u,v)

25、)4. 計(jì)算l2(t)=min{ l2(v) | v?V且有臨時(shí)標(biāo)號(hào)}, l(t)改為永久標(biāo)號(hào)5. if i<n then 令u?t, i?i+1, 轉(zhuǎn)2對(duì)每一個(gè)u, d(s,u)= l2(u),根據(jù)l1(v)回溯找到s到u的最短路徑.,24,實(shí)例,例9.5 一個(gè)總部和6個(gè)工地, 求從總部到各工地的最短路徑解,25,實(shí)例,26,實(shí)例,27,實(shí)例,28,實(shí)例,v1v3v2, d(v1,v2

26、)=13 v1v3, d(v1,v3)=10v1v3v5v4, d(v1,v4)=18 v1v3v5, d(v1,v5)=14v1v3v5v6, d(v1,v6)=16 v1v3v5v6v7, d(v1,v7)=22,29,9.3 圖的連通性,定義9.13

27、 設(shè)無(wú)向圖G=，若u,v?V之間存在通路，則稱u,v是連通的，記作u～v. 規(guī)定: ?v?V v～v． 若無(wú)向圖G是平凡圖或G中任何兩個(gè)頂點(diǎn)都是連通的，則稱G為連通圖，否則稱G為非連通圖．～是V上的等價(jià)關(guān)系, 具有自反性、對(duì)稱性和傳遞性．定義9.14 設(shè)無(wú)向圖G=，Vi是V關(guān)于頂點(diǎn)之間連通關(guān)系～的一個(gè)等價(jià)類，稱導(dǎo)出子圖G[Vi]為G的一個(gè)連通分支. G的連通分支數(shù)記為p(G)．,30,點(diǎn)割集與邊割集,定義

28、9.15 設(shè)無(wú)向圖G=. 若V??V使得p(G?V? )>p(G), 且對(duì)于任意的V?? ?V?, 均有p(G?V??)=p(G), 則稱V?是G的點(diǎn)割集.若V? ={v}, 則稱v為割點(diǎn)．定義9.16 設(shè)無(wú)向圖G=, 若E??E使得p(G?E? )>p(G), 且對(duì)于任意的E???E?, 均有p(G?E??)=p(G), 則稱E?是G的邊割集，簡(jiǎn)稱為割集. 若E? ={e}, 則稱e為割邊或橋．,31,例

29、3 {v1,v4}，{v6}是點(diǎn)割集，v6是割點(diǎn). {v2,v5}不是.{e1,e2}，{e1,e3,e5,e6}，{e8}等是邊割集，e8是橋. 而{e7,e9,e5,e6} 不是.,點(diǎn)連通度與邊連通度,定義9.17 G為連通非完全圖, 稱 ?(G) = min{ |V ?|?V ?為點(diǎn)割集 } 為G的點(diǎn)連通度, 簡(jiǎn)稱連通度. 若?(G)?k，則稱G為 k-連通圖 . 規(guī)

30、定 ?(Kn) = n?1, 非連通圖的連通度為0.?定義9.18 設(shè)G為連通圖, 稱 ?(G) = min{|E?|?E?為邊割集}為G的邊連通度. 若?(G)?r，則稱G是 r 邊-連通圖. 規(guī)定非連通圖的邊連通度為0.,32,例 ?=2, 2-連通圖, 也是1-連通. ?=2, 2邊-連通圖, 也是1邊-連通.,幾點(diǎn)說(shuō)明,?(Kn)=?(Kn)=n?1G

31、非連通，則 ?=?=0若G中有割點(diǎn)，則?=1，若有橋，則?=1若?(G)=k, 則G是1-連通圖，2-連通圖，…，k-連通圖，但不是(k+s)-連通圖，s?1若?(G)=r, 則G是1邊-連通圖，2邊-連通圖，…，r邊-連通圖，但不是(r+s)-邊連通圖，s?1定理9.6 ?(G)??(G)??(G),33,有向圖的連通性及分類,定義9.19 設(shè)D=為一個(gè)有向圖, ?vi,vj?V, 若從vi到vj存在通路, 則稱vi

32、可達(dá)vj, 記作vi?vj . 規(guī)定vi ?vi. 若vi?vj且vj?vi，則稱vi與vj是相互可達(dá)的, 記作vi?vj. 規(guī)定vi?vi．性質(zhì): ? 具有自反性(vi ? vi)、傳遞性 ? 具有自反性、對(duì)稱性、傳遞性 定義9.20 若有向圖D=<V,E)的基圖是連通圖, 則稱D是弱連通圖, 簡(jiǎn)稱為連通圖. 若?vi,vj?V, vi?vj與vj?vi至少有一個(gè)成立，則稱 D是單向連

33、通圖. 若?vi,vj?V, 均有vi?vj, 則稱D是強(qiáng)連通圖．,34,有向圖的連通性,35,強(qiáng)連通 單向連通 弱連通,定理9.7 有向圖D=是強(qiáng)連通圖當(dāng)且僅當(dāng)D中存在經(jīng)過(guò)每個(gè)頂點(diǎn)至少一次的回路．證 充分性顯然. 證必要性. 設(shè)V={v1,v2,?,vn}, ?i為vi到vi+1的通路( i=1,2,…,n?1), ?n為vn到v1的通路. 依次連接?1,

34、?2, …, ?n?1, ?n所得到的回路經(jīng)過(guò)D中每個(gè)頂點(diǎn)至少一次．定理9.8 有向圖D是單向連通圖當(dāng)且僅當(dāng)D中存在經(jīng)過(guò)每個(gè)頂點(diǎn)至少一次的通路．,例,擴(kuò)大路徑法,設(shè)G=為無(wú)向圖, ? 為G中一條路徑. 若此路徑的兩個(gè)端點(diǎn)都不與通路外的頂點(diǎn)相鄰, 則稱? 是極大路徑.任取一條邊, 如果它有一個(gè)端點(diǎn)與其他的頂點(diǎn)相鄰, 就將這條邊延伸到這個(gè)頂點(diǎn). 繼續(xù)這一過(guò)程, 直至得到一條極大路徑為止. 稱此種方法為“擴(kuò)大路徑法”. 用擴(kuò)大

35、路徑法總可以得到一條極大路徑. 在有向圖中可類似討論.,例 由一條路徑擴(kuò)大出的極大路徑不惟一，極大路徑不一定是最長(zhǎng)的路徑,擴(kuò)大路徑法的應(yīng)用,例4 設(shè) G 為 n（n?3）階無(wú)向簡(jiǎn)單圖，? ? 2，證明G 中存在長(zhǎng)度 ? ?+1 的圈.,37,證 設(shè) ? = v0v1…vl 是一條極大路徑, 則 l ? ?. 因?yàn)関0 不與 ? 外頂點(diǎn)相鄰, 又 d(v0) ? ?, 因而在 ?上除 v1外, 至少還存在??1個(gè)

36、頂點(diǎn)與 v0 相鄰. 設(shè) vx 是離 v0 最遠(yuǎn)的頂點(diǎn), 于是v0v1…vxv0 為 G 中長(zhǎng)度 ? ?+1 的圈.,9.4 圖的矩陣表示,無(wú)向圖的關(guān)聯(lián)矩陣定義9.21 無(wú)向圖G=，|V|=n，|E|=m，令 mij為 vi 與 ej的關(guān)聯(lián)次數(shù)，稱(mij)n?m為G 的關(guān)聯(lián)矩陣，記為M(G).,38,例,無(wú)向圖關(guān)聯(lián)矩陣的性質(zhì),39,40,定義9.22 設(shè)有向圖D=中無(wú)環(huán)，令則稱 (mij)n?m為D的關(guān)聯(lián)矩陣，

37、記為M(D).,例,有向圖(無(wú)環(huán))的關(guān)聯(lián)矩陣,41,(1) 每列恰好有一個(gè)+1和一個(gè)-1．(2) -1的個(gè)數(shù)等于+1的個(gè)數(shù)，都等于邊數(shù)m.第i行中，+1的個(gè)數(shù)等于d+(vi)，-1的個(gè)數(shù)等于d?(vi)．(4) 平行邊對(duì)應(yīng)的列相同,有向圖關(guān)聯(lián)矩陣的性質(zhì),有向圖的鄰接矩陣,定義9.23 設(shè)有向圖D=, V={v1, v2, …, vn}, 令 為頂點(diǎn) vi 鄰接到頂點(diǎn) vj 邊的條數(shù)，稱( )為D的鄰接矩

38、陣，記作A(D)，或簡(jiǎn)記為A.,42,例,有向圖鄰接矩陣的性質(zhì),43,定理9.9 設(shè) A為有向圖 D 的鄰接矩陣, 頂點(diǎn)集V={v1,v2,…, vn}，則 A 的 l 次冪 Al（l?1）中元素,鄰接矩陣的應(yīng)用,45,例5 有向圖D如圖所示，求 A, A2, A3, A4，并回答諸問(wèn)題：(1) D 中長(zhǎng)度為1, 2, 3, 4的通路各有多少條？其中回路分別為多少條？(2) D 中長(zhǎng)度小于或等于4的通路為多少條？其中有多少條回

39、路？,實(shí)例,46,,(1) D中長(zhǎng)度為1的通路為8條，其中有1條是回路. D中長(zhǎng)度為2的通路為11條，其中有3條是回路. D中長(zhǎng)度為3的通路為14條，其中有1條是回路. D中長(zhǎng)度為4的通路為17條，其中有3條是回路. (2) D中長(zhǎng)度小于等于4的通路為50條，其中有8條是回路.,實(shí)例求解,47,定義9.24 設(shè)D=為有向圖. V={v1, v2, …, vn}, 令,有向圖的可達(dá)矩陣,稱 (pij

40、)n?n 為D的可達(dá)矩陣，記作P(D)，簡(jiǎn)記為P. P(D)的主對(duì)角線上的元素全為1. D 強(qiáng)連通當(dāng)且僅當(dāng) P(D)為全1矩陣.,例,第九章 習(xí)題課,主要內(nèi)容無(wú)向圖和有向圖及其有關(guān)的概念; 握手定理及其推論；圖的同構(gòu)通路與回路無(wú)向圖的連通性與連通度有向圖的連通性及其分類圖的矩陣表示,48,基本要求,深刻理解圖及其有關(guān)的概念深刻理解和靈活地應(yīng)用握手定理及推論記住通路與回路的定義、分類及表示法深刻理解與無(wú)向圖連通性、連

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

42、, (8,1）它們都滿足要求.,方法二：反證法否則，至多有4個(gè)5度頂點(diǎn)并且至多有4個(gè)6度頂點(diǎn)，這與G是 9 階圖矛盾.,51,2．存在以2, 2, 2, 2, 3, 3為頂點(diǎn)度數(shù)的簡(jiǎn)單圖嗎？若存在，畫(huà)出盡可能多的這種非同構(gòu)的圖來(lái).,練習(xí)2,解,52,證 用擴(kuò)大路徑法證明.設(shè)? ? ? ? +, 證明D中存在長(zhǎng)度 ? ? ?+1的圈. 設(shè) ? = v0v1…vl為極大路徑, 則l ? ? ?. 在 ? 上存在d?(v0)? ?

43、?個(gè)頂點(diǎn) 鄰接到v0, 設(shè)vk是其中離v0最遠(yuǎn)的頂點(diǎn), k?? ?. 于是, v0v1…vkv0為D中長(zhǎng)度 ? ? ?+1的圈 . 當(dāng)? + ? ? ?時(shí), 類似可證.,3．設(shè)D=為有向簡(jiǎn)單圖, 已知 ?(D) ? 2, ? +(D)>0, ? ?(D)>0, 證明D中存在長(zhǎng)度 ? max{? +,? ?}+1的圈.,練習(xí)3,練習(xí)4,(1) D中有幾種不同構(gòu)的圈？(2) D中有幾種不同構(gòu)的非圈簡(jiǎn)單回路？(3) D是哪

44、類連通圖?(4) D中v1到v4長(zhǎng)度為1,2,3,4的通路各多少條？(5) D中v1到v1長(zhǎng)度為1,2,3,4的回路各多少條？(6) D中長(zhǎng)度為4的通路（不含回路）有多少條？(7) D中長(zhǎng)度為4的回路有多少條？(8) D中長(zhǎng)度?4的通路有多少條？其中有幾條是回路？(9) 寫出D的可達(dá)矩陣.,53,4．有向圖D如圖所示，回答下列諸問(wèn)：,解答,解 (1) 有3種非同構(gòu)的圈，長(zhǎng)度分別為1,2,3.,54,(2) 有3種非同構(gòu)的

45、非圈簡(jiǎn)單回路，它們的長(zhǎng)度分別為 4,5,6.,(3) D是強(qiáng)連通的.,為解(4)—(8), 先求D的鄰接矩陣的前4次冪.,55,(4) v1到v4長(zhǎng)度為1,2,3,4的通路數(shù)分別為0,0,2,2. (定義意義下).,解答,(5) v1到v1長(zhǎng)度為1,2,3,4的回路數(shù)分別為1,1,3,5.,(6) 長(zhǎng)度為4的通路(不含回路)為33條.,(7) 長(zhǎng)度為4的回路為11條.,(8) 長(zhǎng)度?4的通路88條，其中22條為回路.,(9) 4?4的