離散數(shù)學(xué)第14章課件_高等教育出版社_屈婉玲_耿素云_張立昂主編

1、1第五部分第五部分 圖論圖論本部分主要內(nèi)容本部分主要內(nèi)容l 圖的基本概念圖的基本概念l 歐拉圖、哈密頓圖歐拉圖、哈密頓圖l 樹樹l 2 第十四章第十四章 圖的基本概念圖的基本概念主要內(nèi)容主要內(nèi)容l 圖圖l 通路與回路通路與回路l 圖的連通性圖的連通性l 圖的矩陣表示圖的矩陣表示l 圖的運(yùn)算圖的運(yùn)算預(yù)備知識(shí)預(yù)備知識(shí)l 多重集合多重集合元素可以重復(fù)出現(xiàn)的集合元素可以重復(fù)出現(xiàn)的集合l 無序積無序積A B=x,y | x A y B314.1 圖圖定義定義14.1 無向圖無向圖G = , 其中其中(1) V 為頂點(diǎn)集，元素稱為為頂點(diǎn)集，元素稱為頂點(diǎn)頂點(diǎn)(2) E為為V V 的多重集，其元素稱為無向邊，

2、簡稱的多重集，其元素稱為無向邊，簡稱邊邊實(shí)例實(shí)例 設(shè)設(shè) V = v1, v2, ,v5, E = (v1,v1), (v1,v2), (v2,v3), (v2,v3), (v2,v5), (v1,v5), (v4,v5) 則則 G = 為一無向圖為一無向圖4有向圖有向圖定義定義14.2 有向圖有向圖D=, 只需注意只需注意E是是V V 的多重子集的多重子集圖圖2表示的是一個(gè)有向圖，試寫出它的表示的是一個(gè)有向圖，試寫出它的V 和和 E 注意：圖的數(shù)學(xué)定義與圖形表示。注意：圖的數(shù)學(xué)定義與圖形表示。5相關(guān)概念相關(guān)概念1. 圖圖 可用可用G泛指圖（無向的或有向的）泛指圖（無向的或有向的） V(G),

3、E(G), V(D), E(D) n階圖階圖2. 有限圖有限圖3. n 階零圖與平凡圖階零圖與平凡圖4. 空?qǐng)D空?qǐng)D5. 用用 ek 表示無向邊或有向邊表示無向邊或有向邊6. 頂點(diǎn)與邊的關(guān)聯(lián)關(guān)系頂點(diǎn)與邊的關(guān)聯(lián)關(guān)系 關(guān)聯(lián)、關(guān)聯(lián)次數(shù)關(guān)聯(lián)、關(guān)聯(lián)次數(shù) 環(huán)環(huán) 孤立點(diǎn)孤立點(diǎn)7. 頂點(diǎn)之間的相鄰關(guān)系頂點(diǎn)之間的相鄰關(guān)系6)()()(),()(|)(vvNvNvvuGEvuGVuuvNv 的的閉閉鄰鄰域域的的鄰鄰域域)(|)(關(guān)關(guān)聯(lián)聯(lián)與與veGEeevI )()()()()()(,)(|)()(,)(|)(vvNvNvvvvNvvuDEvuDVuuvvvuDEuvDVuuvvDDDDDDD 的閉鄰域的閉鄰域的鄰域

4、的鄰域的先驅(qū)元集的先驅(qū)元集的后繼元集的后繼元集8. 鄰域與關(guān)聯(lián)集鄰域與關(guān)聯(lián)集 v V(G) (G為無向圖為無向圖) v 的關(guān)聯(lián)集的關(guān)聯(lián)集 v V(D) (D為有向圖為有向圖)9. 標(biāo)定圖與非標(biāo)定圖標(biāo)定圖與非標(biāo)定圖10. 基圖基圖相關(guān)概念相關(guān)概念7多重圖與簡單圖多重圖與簡單圖定義定義14.3 (1) 無向圖中的平行邊及重?cái)?shù)無向圖中的平行邊及重?cái)?shù) (2) 有向圖中的平行邊及重?cái)?shù)（注意方向性）有向圖中的平行邊及重?cái)?shù)（注意方向性） (3) 多重圖多重圖 (4) 簡單圖簡單圖在定義在定義14.3中定義的簡單圖是極其重要的概念中定義的簡單圖是極其重要的概念 8頂點(diǎn)的度數(shù)頂點(diǎn)的度數(shù)定義定義14.4 (1)

5、設(shè)設(shè)G=為無向圖為無向圖, v V, d(v)v的度數(shù)的度數(shù), 簡稱度簡稱度 (2) 設(shè)設(shè)D=為有向圖為有向圖, v V, d+(v)v的入度的入度 d (v)v的出度的出度 d(v)v的度或度數(shù)的度或度數(shù) (3) (G), (G) (4) +(D), +(D), (D), (D), (D), (D) (5) 奇頂點(diǎn)度與偶度頂點(diǎn)奇頂點(diǎn)度與偶度頂點(diǎn)9mvdnii2)(1 mvdvdmvdniiniinii 111)()(,2)(且且定理定理14.1 設(shè)設(shè)G=為任意無向圖，為任意無向圖，V=v1,v2,vn, |E|=m, 則則證證 G中每條邊中每條邊 (包括環(huán)包括環(huán)) 均有兩個(gè)端點(diǎn)，所以在計(jì)算均

6、有兩個(gè)端點(diǎn)，所以在計(jì)算G中各頂點(diǎn)中各頂點(diǎn)度數(shù)之和時(shí)，每條邊均提供度數(shù)之和時(shí)，每條邊均提供2度，度，m 條邊共提供條邊共提供 2m 度度.本定理的證明類似于定理本定理的證明類似于定理14.1握手定理握手定理定理定理14.2 設(shè)設(shè)D=為任意有向圖，為任意有向圖，V=v1,v2,vn, |E|=m, 則則10握手定理推論握手定理推論推論推論 任何圖任何圖 (無向或有向無向或有向) 中，奇度頂點(diǎn)的個(gè)數(shù)是偶數(shù)中，奇度頂點(diǎn)的個(gè)數(shù)是偶數(shù).證證 設(shè)設(shè)G=為任意圖，令為任意圖，令 V1=v | v V d(v)為奇數(shù)為奇數(shù) V2=v | v V d(v)為偶數(shù)為偶數(shù) 則則V1 V2=V, V1 V2=，由握手定

7、理可知，由握手定理可知由于由于2m, 均為偶數(shù)，所以均為偶數(shù)，所以 為偶數(shù)，但因?yàn)闉榕紨?shù)，但因?yàn)閂1中中頂點(diǎn)度數(shù)為奇數(shù)，所以頂點(diǎn)度數(shù)為奇數(shù)，所以|V1|必為偶數(shù)必為偶數(shù). 21)()()(2VvVvVvvdvdvdm 2)(Vvvd 1)(Vvvd11例例1 無向圖無向圖G有有16條邊，條邊，3個(gè)個(gè)4度頂點(diǎn)，度頂點(diǎn)，4個(gè)個(gè)3度頂點(diǎn)，其余度頂點(diǎn)，其余頂點(diǎn)度數(shù)均小于頂點(diǎn)度數(shù)均小于3，問，問G的階數(shù)的階數(shù)n為幾？為幾？解解 本題的關(guān)鍵是應(yīng)用握手定理本題的關(guān)鍵是應(yīng)用握手定理. 設(shè)除設(shè)除3度與度與4度頂點(diǎn)外，還有度頂點(diǎn)外，還有x個(gè)頂點(diǎn)個(gè)頂點(diǎn)v1, v2, , vx， 則則 d(vi) 2，i =1, 2

8、, , x，于是得不等式于是得不等式 32 24+2x得得 x 4, 階數(shù)階數(shù) n 4+4+3=11. 握手定理應(yīng)用握手定理應(yīng)用12圖的度數(shù)列圖的度數(shù)列1 . V=v1, v2, , vn為無向圖為無向圖G的頂點(diǎn)集，稱的頂點(diǎn)集，稱d(v1), d(v2), , d(vn)為為G的的度度數(shù)列數(shù)列 2. V=v1, v2, , vn為有向圖為有向圖D的頂點(diǎn)集，的頂點(diǎn)集， D的的度數(shù)列度數(shù)列：d(v1), d(v2), , d(vn) D的的入度列入度列：d+(v1), d+(v2), , d+(vn) D的的出度列出度列：d (v1), d (v2), , d (vn) 3. 非負(fù)整數(shù)列非負(fù)整數(shù)列

9、d=(d1, d2, , dn)在什么條件下是在什么條件下是可圖化的可圖化的，是，是可簡單圖化可簡單圖化的？的？定理定理14.4 p277易知：易知：(2, 4, 6, 8, 10)，(1, 3, 3, 3, 4) 是可圖化的，后者又是可是可圖化的，后者又是可簡單圖化的，而簡單圖化的，而(2, 2, 3, 4, 5)，(3, 3, 3, 4) 都不是可簡單圖化都不是可簡單圖化的，特別是后者也不是可圖化的的，特別是后者也不是可圖化的13n 階完全圖與競(jìng)賽圖階完全圖與競(jìng)賽圖定義定義14.6 (1) n (n 1) 階無向完全圖階無向完全圖每個(gè)頂點(diǎn)與其余頂點(diǎn)均相鄰的每個(gè)頂點(diǎn)與其余頂點(diǎn)均相鄰的無向簡單

10、圖無向簡單圖，記作，記作 Kn.簡單性質(zhì)：邊數(shù)簡單性質(zhì)：邊數(shù)(2) n (n 1)階階有向完全圖有向完全圖每對(duì)頂點(diǎn)之間均有兩條方向相每對(duì)頂點(diǎn)之間均有兩條方向相反的有向邊的反的有向邊的有向簡單圖有向簡單圖.簡單性質(zhì)：簡單性質(zhì)： (3) n (n 1) 階階競(jìng)賽圖競(jìng)賽圖基圖為基圖為Kn的的有向簡單圖有向簡單圖.簡單性質(zhì)：邊數(shù)簡單性質(zhì)：邊數(shù)1,2)1( nnnm 1),1(2),1( nnnnm 1,2)1( nnnm 14n 階階 k 正則圖正則圖(1)為為K5，(2)為為3階有向完全圖，階有向完全圖，(3)為為4階競(jìng)賽圖階競(jìng)賽圖. (1) (2) (3)定義定義14.7 n 階階k正則圖正則圖

11、= =k 的的無向簡單圖無向簡單圖簡單性質(zhì)：邊數(shù)（由握手定理得）簡單性質(zhì)：邊數(shù)（由握手定理得）n階完全圖階完全圖Kn是是 n 1正則圖，正則圖，2nkm 15子圖子圖定義定義14.8 G=, G =(1) GG G 為為G的的子圖子圖，G為為G 的的母圖母圖(2) 若若GG且且V =V，則稱，則稱G 為為G的的生成子圖生成子圖(3) 若若VV或或EE，稱，稱G 為為G的的真子圖真子圖(4) V （VV且且V）的）的導(dǎo)出子圖導(dǎo)出子圖，記作，記作GV (5) E （EE且且E）的）的導(dǎo)出子圖導(dǎo)出子圖，記作，記作GE 16例例2 畫出畫出K4的所有非同構(gòu)的生成子圖的所有非同構(gòu)的生成子圖實(shí)例實(shí)例17補(bǔ)

12、圖補(bǔ)圖定義定義14.9 設(shè)設(shè)G=為為n階無向簡單圖，以階無向簡單圖，以V為頂點(diǎn)集，以為頂點(diǎn)集，以所有使所有使G成為完全圖成為完全圖Kn的的添加邊添加邊組成的集合為邊集的圖，組成的集合為邊集的圖，稱為稱為G的的補(bǔ)圖補(bǔ)圖，記作，記作 .若若G , 則稱則稱G是是自補(bǔ)圖自補(bǔ)圖. 例：見書例：見書P280 圖圖14.6GG1814.2 通路與回路通路與回路定義定義14.11 給定圖給定圖G=（無向或有向的），（無向或有向的），G中中頂點(diǎn)與頂點(diǎn)與邊的交替序列邊的交替序列 = v0e1v1e2elvl，vi 1, vi 是是 ei 的端點(diǎn)的端點(diǎn).(1) 通路與回路：通路與回路： 為為通路通路；若；若 v0

13、=vl， 為為回路回路，l 為為回路長回路長 度度.(2) 簡單通路與回路：所有邊各異，簡單通路與回路：所有邊各異， 為為簡單通路簡單通路，又若，又若v0=vl， 為為簡單回路簡單回路(3) 初級(jí)通路初級(jí)通路(路徑路徑)與初級(jí)回路與初級(jí)回路(圈圈)： 中所有頂點(diǎn)各異，則中所有頂點(diǎn)各異，則稱稱 為為初級(jí)通路初級(jí)通路(路徑路徑)，又若除，又若除v0=vl，所有的頂點(diǎn)各不相，所有的頂點(diǎn)各不相同且所有的邊各異，則稱同且所有的邊各異，則稱 為為初級(jí)回路初級(jí)回路(圈圈)(4) 復(fù)雜通路與回路：有邊重復(fù)出現(xiàn)復(fù)雜通路與回路：有邊重復(fù)出現(xiàn)19幾點(diǎn)說明幾點(diǎn)說明表示法表示法 定義表示法定義表示法 只用邊表示法只用邊

14、表示法 只用頂點(diǎn)表示法（在簡單圖中）只用頂點(diǎn)表示法（在簡單圖中） 混合表示法混合表示法環(huán)環(huán)（長為（長為1的圈）的長度為的圈）的長度為1，兩條平行邊構(gòu)成的圈長度為，兩條平行邊構(gòu)成的圈長度為 2，無向簡單圖中，圈長，無向簡單圖中，圈長 3，有向簡單圖中圈的長度，有向簡單圖中圈的長度 2. 不同的圈（以長度不同的圈（以長度 3的為例）的為例） 20通路與回路的長度通路與回路的長度定理定理14.5 在在n 階圖階圖G中，若從頂點(diǎn)中，若從頂點(diǎn)vi 到到vj（vi vj）存在通路，）存在通路，則從則從vi 到到 vj 存在長度小于或等于存在長度小于或等于n 1 的通路的通路.推論推論 在在 n 階圖階圖G

15、中，若從頂點(diǎn)中，若從頂點(diǎn)vi 到到 vj（vi vj）存在通路，則）存在通路，則從從vi 到到vj 存在長度小于或等于存在長度小于或等于n 1的初級(jí)通路（路徑）的初級(jí)通路（路徑）.定理定理14.6 在一個(gè)在一個(gè)n 階圖階圖G中，若存在中，若存在 vi 到自身的回路，則一到自身的回路，則一定存在定存在vi 到自身長度小于或等于到自身長度小于或等于 n 的回路的回路.推論推論 在一個(gè)在一個(gè)n 階圖階圖G中，若存在中，若存在 vi 到自身的簡單回路，則一到自身的簡單回路，則一定存在長度小于或等于定存在長度小于或等于n 的初級(jí)回路的初級(jí)回路.2114.3 圖的連通性圖的連通性無向圖的連通性無向圖的連通

16、性(1) 頂點(diǎn)之間的連通關(guān)系：頂點(diǎn)之間的連通關(guān)系：G=為無向圖為無向圖 若若 vi 與與 vj 之間有通路，則之間有通路，則 vi vj 是是V上的等價(jià)關(guān)系上的等價(jià)關(guān)系 R=| u,v V且且u v (2) G的連通性與連通分支的連通性與連通分支 若若 u,v V，u v，則稱，則稱G連通連通 V1,V2,Vk，稱，稱GV1, GV2, ,GVk為為連通分連通分 支支，其個(gè)數(shù)，其個(gè)數(shù) p(G)=k (k 1)； k=1，G連通連通22短程線與距離短程線與距離(3) 短程線與距離短程線與距離 u與與v之間的之間的短程線短程線：u v，u與與v之間長度最短的通路之間長度最短的通路 u與與v之間的之

17、間的距離距離：d(u,v)短程線的長度短程線的長度 d(u,v)的性質(zhì)：的性質(zhì)： d(u,v) 0, u v時(shí)時(shí)d(u,v)= d(u,v)=d(v,u) d(u,v)+d(v,w) d(u,w)23無向圖的連通度無向圖的連通度1. 刪除頂點(diǎn)及刪除邊刪除頂點(diǎn)及刪除邊 G v 從從G中將中將v及關(guān)聯(lián)的邊去掉及關(guān)聯(lián)的邊去掉 G V 從從G中刪除中刪除V 中所有的頂點(diǎn)中所有的頂點(diǎn) G e 將將e從從G中去掉中去掉 G E 刪除刪除E 中所有邊中所有邊 2. 點(diǎn)割集與邊割集點(diǎn)割集與邊割集 點(diǎn)割集與割點(diǎn)點(diǎn)割集與割點(diǎn) 書書p283定義定義14.15 G=, VV V 為為點(diǎn)割集點(diǎn)割集p(G V )p(G)

18、且有極小性且有極小性 v為為割點(diǎn)割點(diǎn)v為點(diǎn)割集為點(diǎn)割集定義定義14.16 G=, EE E 是是邊割集邊割集p(G E )p(G)且有極小性且有極小性 e是是割邊割邊（橋）（橋）e為邊割集為邊割集24點(diǎn)割集與割點(diǎn)點(diǎn)割集與割點(diǎn)例例3 v1,v4，v6是點(diǎn)是點(diǎn)割集，割集，v6是割點(diǎn)是割點(diǎn). v2,v5是點(diǎn)割集嗎？是點(diǎn)割集嗎？e1,e2，e1,e3,e5,e6，e8等是邊割集，等是邊割集，e8是是橋，橋，e7,e9,e5,e6 是邊割是邊割集嗎？集嗎？幾點(diǎn)說明：幾點(diǎn)說明：l Kn中無點(diǎn)割集，中無點(diǎn)割集，Nn中既無點(diǎn)割集，也無邊割集，其中中既無點(diǎn)割集，也無邊割集，其中Nn為為 n 階零圖階零圖. l

19、若若G 連通，連通，E 為邊割集，則為邊割集，則 p(G E )=2，V 為點(diǎn)割集，則為點(diǎn)割集，則 p(G V ) 2 25點(diǎn)連通度與邊連通度點(diǎn)連通度與邊連通度定義定義14.18 G為連通非完全圖為連通非完全圖 點(diǎn)連通度點(diǎn)連通度 (G) = min |V | V 為點(diǎn)割集為點(diǎn)割集 規(guī)定規(guī)定 (Kn) = n 1 若若G非連通，非連通， (G) = 0 若若 (G) k，則稱，則稱G為為 k-連通圖連通圖 定義定義14.19 設(shè)設(shè)G為連通圖為連通圖 邊連通度邊連通度 (G) = min|E | E 為邊割集為邊割集 若若G非連通，則非連通，則 (G) = 0 若若 (G) r，則稱，則稱G是是

20、r 邊邊-連通圖連通圖圖中，圖中， = =1，它是，它是 1-連通圖連通圖 和和 1邊邊-連通圖連通圖26有向圖的連通性有向圖的連通性定義定義14.20 D=為有向圖為有向圖 vi vj（vi 可達(dá)可達(dá) vj）vi 到到vj 有通路有通路 vi vj（vi 與與vj 相互可達(dá)）相互可達(dá)）性質(zhì)性質(zhì) 具有自反性具有自反性(vi vi)、傳遞性、傳遞性 具有自反性、對(duì)稱性、傳遞性具有自反性、對(duì)稱性、傳遞性 vi 到到vj 的短程線與距離的短程線與距離類似于無向圖中，只需注意距離表示法的不同類似于無向圖中，只需注意距離表示法的不同(無向圖中無向圖中d(vi,vj)，有向圖中，有向圖中d) 及及 d無對(duì)

21、稱性無對(duì)稱性27有向圖的連通性及分類有向圖的連通性及分類定義定義14.22 D=為有向圖為有向圖 D弱連通弱連通(連通連通)基圖為無向連通圖基圖為無向連通圖 D單向連通單向連通 vi,vj V，vivj 或或 vjvi D強(qiáng)連通強(qiáng)連通 vi,vj V，vivj易知，強(qiáng)連通易知，強(qiáng)連通單向連通單向連通弱連通弱連通判別法判別法定理定理14.8 D強(qiáng)連通當(dāng)且僅當(dāng)強(qiáng)連通當(dāng)且僅當(dāng)D中存在經(jīng)過每個(gè)頂點(diǎn)至少一次中存在經(jīng)過每個(gè)頂點(diǎn)至少一次的回路的回路定理定理14.9 D單向連通當(dāng)且僅當(dāng)單向連通當(dāng)且僅當(dāng)D中存在經(jīng)過每個(gè)頂點(diǎn)至少一中存在經(jīng)過每個(gè)頂點(diǎn)至少一次的通路次的通路28二部圖二部圖定義定義14.23 設(shè)設(shè) G

22、=為一個(gè)無向圖，若能將為一個(gè)無向圖，若能將 V分成分成 V1和和V2(V1 V2=V，V1 V2=)，使得，使得 G 中的每條邊的兩個(gè)端點(diǎn)都是中的每條邊的兩個(gè)端點(diǎn)都是一個(gè)屬于一個(gè)屬于V1，另一個(gè)屬于，另一個(gè)屬于V2，則稱，則稱 G 為為二部圖二部圖 ( 或稱或稱二分二分圖圖、偶圖偶圖等等 )，稱，稱V1和和V2為為互補(bǔ)頂點(diǎn)子集互補(bǔ)頂點(diǎn)子集，常將二部圖，常將二部圖G記為記為. 又若又若G是簡單二部圖，是簡單二部圖，V1中每個(gè)頂點(diǎn)均與中每個(gè)頂點(diǎn)均與V2中所有的頂點(diǎn)相中所有的頂點(diǎn)相鄰，則稱鄰，則稱G為為完全二部圖完全二部圖，記為，記為 Kr,s，其中，其中r=|V1|，s=|V2|. 注意，注意，n

23、 階零圖為二部圖階零圖為二部圖. 2914.4 圖的矩陣表示圖的矩陣表示無向圖的關(guān)聯(lián)矩陣（對(duì)圖無限制）無向圖的關(guān)聯(lián)矩陣（對(duì)圖無限制） P288定義定義14.24 無向圖無向圖G=，|V|=n，|E|=m，令，令 mij為為 vi 與與 ej的關(guān)聯(lián)次數(shù)，稱的關(guān)聯(lián)次數(shù)，稱(mij)n m為為G 的的關(guān)聯(lián)矩陣關(guān)聯(lián)矩陣，記為，記為M(G). 性質(zhì)性質(zhì)平行邊的列相同平行邊的列相同)4(2)3(),.,2 , 1()()2(),.,2 , 1(2)1(,11mmnivdmmjmjiijimjijniij 30jiijmjmjiijiijniijmnivdmvdmmjm,1110)3(,.,2 , 1),(

24、) 1(),() 1()2(),.,2 , 1(0) 1 ( 的的終終點(diǎn)點(diǎn)為為，不不關(guān)關(guān)聯(lián)聯(lián)與與，的的始始點(diǎn)點(diǎn)為為jijijiijevevevm10,1有向圖的關(guān)聯(lián)矩陣（無環(huán)有向圖）P288 定義定義14.25 有向圖有向圖D=，令，令則稱則稱 (mij)n m為為D的的關(guān)聯(lián)矩陣關(guān)聯(lián)矩陣，記為，記為M(D). (4) 平行邊對(duì)應(yīng)的列相同平行邊對(duì)應(yīng)的列相同性質(zhì)性質(zhì)有向圖的關(guān)聯(lián)矩陣31有向圖的鄰接矩陣（無限制）有向圖的鄰接矩陣（無限制）定義定義14.26 設(shè)有向圖設(shè)有向圖D=, V=v1, v2, , vn, E=e1, e2, , em, 令為頂點(diǎn)令為頂點(diǎn) vi 鄰接到頂點(diǎn)鄰接到頂點(diǎn) vj 邊的

25、條數(shù)，稱為邊的條數(shù)，稱為D的的鄰接矩鄰接矩陣陣，記作，記作A(D)，或簡記為，或簡記為A. 性質(zhì)性質(zhì) 的回路數(shù)的回路數(shù)中長度為中長度為的通路數(shù)的通路數(shù)中長度為中長度為1)4(1)3(,.,2 , 1),()2(,.,2 , 1),()1(1)1(,)1(1)1(1)1(DaDmanjvdanivdaniiijiijjniijinjij 32推論推論 設(shè)設(shè)Bl=A+A2+Al（l 1），則），則 Bl中元素中元素為D中長度為 l 的通路總數(shù)，)(lija)(liia ninjlija11)( niliia1)( ninjlijb11)( niliib1)(定理定理14.11 設(shè)設(shè) A為有向圖為有

26、向圖 D 的鄰接矩陣，的鄰接矩陣，V=v1, v2, , vn為為頂點(diǎn)集，則頂點(diǎn)集，則 A 的的 l 次冪次冪 Al（l 1）中元素）中元素為D中vi 到vj長度為 l 的通路數(shù)，其中為vi到自身長度為 l 的回路數(shù)，而為為D中長度小于或等于中長度小于或等于 l 的回路數(shù)的回路數(shù)為為D中長度小于或等于中長度小于或等于 l 的通路數(shù)的通路數(shù). 鄰接矩陣的應(yīng)用鄰接矩陣的應(yīng)用為為D 中長度為中長度為 l 的回路總數(shù)的回路總數(shù). 33例例5 有向圖有向圖D如圖所示，求如圖所示，求 A, A2, A3, A4，并回答諸問題：，并回答諸問題：(1) D 中長度為中長度為1, 2, 3, 4的通路各有多少條

27、？其中回路分別為多的通路各有多少條？其中回路分別為多少條？少條？(2) D 中長度小于或等于中長度小于或等于4的通路為多少條？其中有多少條回路？的通路為多少條？其中有多少條回路？實(shí)例實(shí)例34 1004010410050001010310030104000110020102100300010101100101020001432AAAA(1) D中長度為中長度為1的通路為的通路為8條，其中有條，其中有1條是回路條是回路. D中長度為中長度為2的通路為的通路為11條，其中有條，其中有3條是回路條是回路. D中長度為中長度為3和和4的通路分別為的通路分別為14和和17條，回路分別條，回路分別 為為1與

28、與3條條.(2) D中長度小于等于中長度小于等于4的通路為的通路為50條，其中有條，其中有8條是回路條是回路.實(shí)例求解實(shí)例求解35 否否則則可可達(dá)達(dá), 1, 0jiijvvp 1101110111110001P定義定義14.27 設(shè)設(shè)D=為有向圖為有向圖. V=v1, v2, , vn, 令令 有向圖的可達(dá)矩陣（無限制）有向圖的可達(dá)矩陣（無限制）稱稱 (pij)n n 為為D的可達(dá)矩陣，記作的可達(dá)矩陣，記作P(D)，簡記為，簡記為P. 由于由于 vi V，vivi，所以，所以P(D)主對(duì)角線上的元素全為主對(duì)角線上的元素全為1. 由定義不難看出由定義不難看出, D 強(qiáng)連通當(dāng)且僅當(dāng)強(qiáng)連通當(dāng)且僅當(dāng)

29、P(D)為全為全1矩陣矩陣. 下圖所示有向圖下圖所示有向圖 D 的可達(dá)矩陣為的可達(dá)矩陣為36第十四章第十四章 習(xí)題課習(xí)題課主要內(nèi)容主要內(nèi)容l 無向圖、有向圖、關(guān)聯(lián)與相鄰、簡單圖、完全圖、正則圖、無向圖、有向圖、關(guān)聯(lián)與相鄰、簡單圖、完全圖、正則圖、子圖、補(bǔ)圖；握手定理與推論；圖的同構(gòu)子圖、補(bǔ)圖；握手定理與推論；圖的同構(gòu)l 通路與回路及其分類通路與回路及其分類l 無向圖的連通性與連通度無向圖的連通性與連通度l 有向圖的連通性及其分類有向圖的連通性及其分類l 圖的矩陣表示圖的矩陣表示37基本要求基本要求l 深刻理解握手定理及推論的內(nèi)容并能靈活地應(yīng)用它們深刻理解握手定理及推論的內(nèi)容并能靈活地應(yīng)用它們l

30、 深刻理解圖同構(gòu)、簡單圖、完全圖、正則圖、子圖、補(bǔ)圖、深刻理解圖同構(gòu)、簡單圖、完全圖、正則圖、子圖、補(bǔ)圖、二部圖的概念以及它們的性質(zhì)及相互之間的關(guān)系二部圖的概念以及它們的性質(zhì)及相互之間的關(guān)系l 記住通路與回路的定義、分類及表示法記住通路與回路的定義、分類及表示法l 深刻理解與無向圖連通性、連通度有關(guān)的諸多概念深刻理解與無向圖連通性、連通度有關(guān)的諸多概念l 會(huì)判別有向圖連通性的類型會(huì)判別有向圖連通性的類型l 熟練掌握用鄰接矩陣及其冪求有向圖中通路與回路數(shù)的方熟練掌握用鄰接矩陣及其冪求有向圖中通路與回路數(shù)的方法，會(huì)求可達(dá)矩陣法，會(huì)求可達(dá)矩陣 3819階無向圖階無向圖G中，每個(gè)頂點(diǎn)的度數(shù)不是中，每個(gè)

31、頂點(diǎn)的度數(shù)不是5就是就是6. 證明證明G中至少有中至少有5個(gè)個(gè)6度頂點(diǎn)或至少有度頂點(diǎn)或至少有6個(gè)個(gè)5度頂點(diǎn)度頂點(diǎn). 練習(xí)練習(xí)1證證 關(guān)鍵是利用握手定理的推論關(guān)鍵是利用握手定理的推論. 方法一：窮舉法方法一：窮舉法設(shè)設(shè)G中有中有x個(gè)個(gè)5度頂點(diǎn)，則必有度頂點(diǎn)，則必有(9 x)個(gè)個(gè)6度頂點(diǎn)，由握手定度頂點(diǎn)，由握手定理推論可知，理推論可知，(x,9 x)只有只有5種可能：種可能：(0,9), (2,7), (4,5), (6,3), (8,1）它們都滿足要求）它們都滿足要求. 方法二：反證法方法二：反證法否則，由握手定理推論可知，否則，由握手定理推論可知，“G至多有至多有4個(gè)個(gè)5度頂點(diǎn)并且度頂點(diǎn)并且至多有至多有4個(gè)個(gè)6度頂點(diǎn)度頂點(diǎn)”，這與，這與G是是 9 階圖矛盾階圖矛盾. 392數(shù)組數(shù)組2, 2, 2, 2, 3, 3能簡單圖化嗎？若能，畫出盡可能多圖能簡單圖化嗎？若能，畫出盡可能多圖來來. 練習(xí)練習(xí)2只要能畫出只要能畫出6 階無向簡單圖，就說明它可簡單圖化階無向簡單圖，就說明它可簡單圖化. 下圖的下圖的4個(gè)圖都以此數(shù)列為度數(shù)