離散數(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 無(wú)序積無(wú)序積A B=x,y | x A y B314.1 圖圖定義定義14.1 無(wú)向圖無(wú)向圖G = , 其中其中(1) V 為頂點(diǎn)集，元素稱為為頂點(diǎn)集，元素稱為頂點(diǎn)頂點(diǎn)(2) E為為V V 的多重集，其元素稱為無(wú)向邊，簡(jiǎn)

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

3、(G), V(D), E(D) n階圖階圖2. 有限圖有限圖3. n 階零圖與平凡圖階零圖與平凡圖4. 空?qǐng)D空?qǐng)D5. 用用 ek 表示無(wú)向邊或有向邊表示無(wú)向邊或有向邊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為無(wú)向圖為無(wú)向圖) 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多重圖與簡(jiǎn)單圖多重圖與簡(jiǎn)單圖定義定義14.3 (1) 無(wú)向圖中的平行邊及重?cái)?shù)無(wú)向圖中的平行邊及重?cái)?shù) (2) 有向圖中的平行邊及重?cái)?shù)（注意方向性）有向圖中的平行邊及重?cái)?shù)（注意方向性） (3) 多重圖多重圖 (4) 簡(jiǎn)單圖簡(jiǎn)單圖在定義在定義14.3中定義的簡(jiǎn)單圖是極其重要的概念中定義的簡(jiǎn)單圖是極其重要的概念 8頂點(diǎn)的度數(shù)頂點(diǎn)的度數(shù)定義定義14.4 (1) 設(shè)

5、設(shè)G=為無(wú)向圖為無(wú)向圖, v V, d(v)v的度數(shù)的度數(shù), 簡(jiǎn)稱度簡(jiǎn)稱度 (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=為任意無(wú)向圖，為任意無(wú)向圖，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握手定理推論握手定理推論推論推論 任何圖任何圖 (無(wú)向或有向無(wú)向或有向) 中，奇度頂點(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 無(wú)向圖無(wú)向圖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，問(wèn)，問(wèn)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為無(wú)向圖為無(wú)向圖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ù)列d

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

10、無(wú)向簡(jiǎn)單圖，記作，記作 Kn.簡(jiǎn)單性質(zhì)：邊數(shù)簡(jiǎn)單性質(zhì)：邊數(shù)(2) n (n 1)階階有向完全圖有向完全圖每對(duì)頂點(diǎn)之間均有兩條方向相每對(duì)頂點(diǎn)之間均有兩條方向相反的有向邊的反的有向邊的有向簡(jiǎn)單圖有向簡(jiǎn)單圖.簡(jiǎn)單性質(zhì)：簡(jiǎn)單性質(zhì)： (3) n (n 1) 階階競(jìng)賽圖競(jìng)賽圖基圖為基圖為Kn的的有向簡(jiǎn)單圖有向簡(jiǎn)單圖.簡(jiǎn)單性質(zhì)：邊數(shù)簡(jiǎn)單性質(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 的的無(wú)向簡(jiǎn)單圖無(wú)向簡(jiǎn)單圖簡(jiǎn)單性質(zhì)：邊數(shù)（由握手定理得）簡(jiǎn)單性質(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階無(wú)向簡(jiǎn)單圖，以階無(wú)向簡(jiǎn)單圖，以V為頂點(diǎn)集，以為頂點(diǎn)集，以所有使所有使G成為完全圖成為完全圖Kn的的添加邊添加邊組成的集合為邊集的圖，組成的集合為邊集的圖，稱為稱為G的的補(bǔ)圖補(bǔ)圖，記作，記作 .若若G , 則稱則稱G是是自補(bǔ)圖自補(bǔ)圖. 例：見(jiàn)書例：見(jiàn)書P280 圖圖14.6GG1814.2 通路與回路通路與回路定義定義14.11 給定圖給定圖G=（無(wú)向或有向的），（無(wú)向或有向的），G中中頂點(diǎn)與頂點(diǎn)與邊的交替序列邊的交替序列 = v0e1v1e2elvl，vi 1, vi 是是 ei 的端點(diǎn)的端點(diǎn).(1) 通路與回路：通路與回路： 為為通路通路；若；若 v0=

13、vl， 為為回路回路，l 為為回路長(zhǎng)回路長(zhǎng) 度度.(2) 簡(jiǎn)單通路與回路：所有邊各異，簡(jiǎn)單通路與回路：所有邊各異， 為為簡(jiǎn)單通路簡(jiǎn)單通路，又若，又若v0=vl， 為為簡(jiǎn)單回路簡(jiǎn)單回路(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)說(shuō)明幾點(diǎn)說(shuō)明表示法表示法 定義表示法定義表示法 只用邊表示法只用邊表

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

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

16、(1) 頂點(diǎn)之間的連通關(guān)系：頂點(diǎn)之間的連通關(guān)系：G=為無(wú)向圖為無(wú)向圖 若若 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之間長(zhǎng)度最短的通路之間長(zhǎng)度最短的通路 u與與v之間的之間

17、的距離距離：d(u,v)短程線的長(zhǎng)度短程線的長(zhǎng)度 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無(wú)向圖的連通度無(wú)向圖的連通度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)說(shuō)明：幾點(diǎn)說(shuō)明：l Kn中無(wú)點(diǎn)割集，中無(wú)點(diǎn)割集，Nn中既無(wú)點(diǎn)割集，也無(wú)邊割集，其中中既無(wú)點(diǎn)割集，也無(wú)邊割集，其中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是是 r

20、 邊邊-連通圖連通圖圖中，圖中， = =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 的短程線與距離的短程線與距離類似于無(wú)向圖中，只需注意距離表示法的不同類似于無(wú)向圖中，只需注意距離表示法的不同(無(wú)向圖中無(wú)向圖中d(vi,vj)，有向圖中，有向圖中d) 及及 d無(wú)對(duì)稱

21、性無(wú)對(duì)稱性27有向圖的連通性及分類有向圖的連通性及分類定義定義14.22 D=為有向圖為有向圖 D弱連通弱連通(連通連通)基圖為無(wú)向連通圖基圖為無(wú)向連通圖 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)過(guò)每個(gè)頂點(diǎn)至少一次中存在經(jīng)過(guò)每個(gè)頂點(diǎn)至少一次的回路的回路定理定理14.9 D單向連通當(dāng)且僅當(dāng)單向連通當(dāng)且僅當(dāng)D中存在經(jīng)過(guò)每個(gè)頂點(diǎn)至少一中存在經(jīng)過(guò)每個(gè)頂點(diǎn)至少一次的通路次的通路28二部圖二部圖定義定義14.23 設(shè)設(shè) G=

22、為一個(gè)無(wú)向圖，若能將為一個(gè)無(wú)向圖，若能將 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是簡(jiǎn)單二部圖，是簡(jiǎn)單二部圖，V1中每個(gè)頂點(diǎn)均與中每個(gè)頂點(diǎn)均與V2中所有的頂點(diǎn)相中所有的頂點(diǎn)相鄰，則稱鄰，則稱G為為完全二部圖完全二部圖，記為，記為 Kr,s，其中，其中r=|V1|，s=|V2|. 注意，注意，n

23、階零圖為二部圖階零圖為二部圖. 2914.4 圖的矩陣表示圖的矩陣表示無(wú)向圖的關(guān)聯(lián)矩陣（對(duì)圖無(wú)限制）無(wú)向圖的關(guān)聯(lián)矩陣（對(duì)圖無(wú)限制） P288定義定義14.24 無(wú)向圖無(wú)向圖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)矩陣（無(wú)環(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有向圖的鄰接矩陣（無(wú)限制）有向圖的鄰接矩陣（無(wú)限制）定義定義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)，或簡(jiǎn)記為，或簡(jiǎn)記為A. 性質(zhì)性質(zhì) 的回路數(shù)的回路數(shù)中長(zhǎng)度為中長(zhǎng)度為的通路數(shù)的通路數(shù)中長(zhǎng)度為中長(zhǎng)度為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中長(zhǎng)度為 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長(zhǎng)度為 l 的通路數(shù)，其中為vi到自身長(zhǎng)度為 l 的回路數(shù)，而為為D中長(zhǎng)度小于或等于中長(zhǎng)度小于或等于 l 的回路數(shù)的回路數(shù)為為D中長(zhǎng)度小于或等于中長(zhǎng)度小于或等于 l 的通路數(shù)的通路數(shù). 鄰接矩陣的應(yīng)用鄰接矩陣的應(yīng)用為為D 中長(zhǎng)度為中長(zhǎng)度為 l 的回路總數(shù)的回路總數(shù). 33例例5 有向圖有向圖D如圖所示，求如圖所示，求 A, A2, A3, A4，并回答諸問(wèn)題：，并回答諸問(wèn)題：(1) D 中長(zhǎng)度為中長(zhǎng)度為1, 2, 3, 4的通路各有多少條？

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

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

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

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