離散數(shù)學(xué)及其應(yīng)用課件第7章圖論

1、離散數(shù)學(xué)及其應(yīng)用離散數(shù)學(xué)及其應(yīng)用第7章 圖7.1 圖的基本概念7.2 通路與回路、連通的概念7.3 圖的表示7.4 圖的運算2第7章 圖7.1 圖的基本概念2ABCD圖論起源公元十八世紀(jì)有這樣一個問題：在東普魯士有個哥尼斯堡城（ konigsberg，后屬于蘇聯(lián)立陶宛蘇維埃社會主義共和國，現(xiàn)名為加里寧格勒；現(xiàn)屬于立陶宛共和國）。哥尼斯堡城位于pregel河畔，河中有兩個島，城市中的各個部分由七座橋相連。ABCD圖論起源公元十八世紀(jì)有這樣一個問題：在東普魯士有個哥 最早引入圖論處理的問題就是哥尼斯堡七橋問題。 1736年，瑞士數(shù)學(xué)家 L.Eluer （歐拉）在他發(fā)表的“哥尼斯堡七座橋”的著名文章

2、中闡述了解決這個問題的觀點，從而被譽為圖論之父。 當(dāng)時，城中的居民熱衷于這樣一個問題，從四塊陸地的任一塊出發(fā)，怎樣才能做到經(jīng)過每座橋一次且僅一次，然后回到出發(fā)點。問題看來并不復(fù)雜，但當(dāng)?shù)氐木用窈陀稳俗隽瞬簧俚膰L試，卻都沒有取得成功。 最早引入圖論處理的問題就是哥尼斯堡七橋問題。 Euler將四塊陸地表示成四個結(jié)點，凡陸地間有橋相連的，便在兩點間連一條邊。ABCD Euler將四塊陸地表示成四個結(jié)點，凡陸地間有橋相 此時，哥尼斯堡七橋問題歸結(jié)為： 從A, B, C, D 任一點出發(fā)，通過每條邊一次且僅一次而返回出發(fā)點的回通路是否存在？DCAB 此時，哥尼斯堡七橋問題歸結(jié)為：DCAB 歐拉斷言這樣

3、的回通路是不存在的。 理由是： 從圖中的任一點出發(fā)，為了要回到原來的出發(fā)點，要求與每個點相關(guān)聯(lián)的邊數(shù)均為偶數(shù)。 這樣才能保證從一條邊進(jìn)入某點后，再從另一條邊出去，從一個點的不同的兩條邊一進(jìn)一出才能回到出發(fā)點。 而圖中的A, B, C, D全是與奇數(shù)條邊相連，由此可知所要求的回通路是不可能存在的。 歐拉斷言這樣的回通路是不存在的。 理由是：7.1 圖的基本概念7.1.1 無向圖和有向圖7.1.2 度的概念7.1.3 圖的分類7.1.4 子圖與補圖7.1.5 圖的同構(gòu)87.1 圖的基本概念7.1.1 無向圖和有向圖87.1.1 無向圖和有向圖定義7.1.1 一個無向圖可以表示為G =（V，E），其

4、中V是非空有限結(jié)點集，稱V中的元素為結(jié)點或頂點；E是邊集，其中的元素是由V中的元素組成的無序?qū)?，稱E中的元素為邊。若（v，w）是無序?qū)?，則（v，w）=（w，v）。 例如, G=如圖所示, 其中V=v1, v2, ,v5 E=(v1,v1), (v1,v2), (v2,v3), (v2,v3), (v2,v5), (v1,v5), (v4,v5) 9e1e2e3e4e5e6e7v5v1v2v3v47.1.1 無向圖和有向圖定義7.1.1 一個無向圖可以表示有向圖定義7.1.2 一個有向圖可以表示為D=（V，E），其中V是非空有限結(jié)點集，稱V中的元素為結(jié)點或頂點；E是有向邊集，E中的元素是由V中的

5、元素組成的有序?qū)ΓQE中的元素為有向邊。 有向圖D=（V，E）。結(jié)點集V= v1，v2，v3，v4，有向邊集E=，。在有向圖中，10有向圖定義7.1.2 一個有向圖可以表示為D=（V，E），其圖的術(shù)語定義7.1.3 如果關(guān)聯(lián)一對結(jié)點的邊多于一條，則稱這些邊為平行邊。如果有邊關(guān)聯(lián)于一對結(jié)點，則稱這對結(jié)點是鄰接的。一條邊的兩個端點如果關(guān)聯(lián)于同一個結(jié)點，則稱為環(huán)，和任何邊都不關(guān)聯(lián)的點稱為孤立點。邊e2和e3是平行邊，邊e1關(guān)聯(lián)結(jié)點v1和v3，則稱v1和v3是鄰接的，邊e5=（v3，v3）是環(huán)，v4是孤立點。圖的術(shù)語定義7.1.3 如果關(guān)聯(lián)一對結(jié)點的邊多于一條，則稱圖的術(shù)語如果關(guān)聯(lián)一對結(jié)點的方向相同的

6、有向邊多于一條，則稱這些有向邊為多重有向邊或平行邊。如關(guān)聯(lián)于結(jié)點v1和v2的兩條有向邊是平行邊，而關(guān)聯(lián)于結(jié)點v3和v4的兩條有向邊方向相反，不是平行邊。（v1，v1）稱為環(huán)。對于有向邊（v2，v3），稱v2為起點，v3為終點，v2和v3是鄰接的。圖的術(shù)語如果關(guān)聯(lián)一對結(jié)點的方向相同的有向邊多于一條，則稱這些圖的術(shù)語n 階圖: n個頂點的圖零圖: E=的圖平凡圖: 1 階零圖在圖的定義中規(guī)定結(jié)點集合V為非空集，但在運算中可能產(chǎn)生結(jié)點集為空集的運算結(jié)果，因此規(guī)定結(jié)點集為空集的圖為空圖，記為圖的術(shù)語n 階圖: n個頂點的圖7.1.2 度的概念定義7.1.6 設(shè)G=為無向圖, vV, v所關(guān)聯(lián)的邊數(shù)稱為

7、 v的度數(shù)，簡稱度，記作d(v)。懸掛頂點: 度數(shù)為1的頂點懸掛邊: 與懸掛頂點關(guān)聯(lián)的邊G的最大度(G)=maxd(v)| vVG的最小度(G)=mind(v)| vV例如 d(v5)=3, d(v2)=4, d(v1)=4, (G)=4, (G)=1, v4是懸掛頂點, e7是懸掛邊, e1是環(huán)14e1e2e3e4e5e6e7v5v1v2v3v47.1.2 度的概念定義7.1.6 設(shè)G=為無向頂點的度數(shù)(續(xù))定義7.1.7 設(shè)D=為有向圖, vV, 以v為起點所關(guān)聯(lián)的邊數(shù)稱為v的出度，記作d+(v)；以v為終點所關(guān)聯(lián)的邊數(shù)稱為v的入度，記作d(v)。v的總度數(shù)(度) d(v)是v的出度和入度

8、之和： d(v)= d+(v)+ d-(v)+(D), +(D), (D), (D), (D), (D)懸掛頂點, 懸掛邊例如 d+(a)=4, d-(a)=1, d(a)=5, d+(b)=0, d-(b)=3, d(b)=3,+=4, +=0, =3, =1, =5, =315e1e2e3e4e5e6e7dabc頂點的度數(shù)(續(xù))定義7.1.7 設(shè)D=為有向圖,握手定理定理7.1.1 設(shè)圖G=(V, E)為無向圖或有向圖，G有n個結(jié)點v1,v2,vn，e條邊(無向或有向), 則圖G中所有結(jié)點的度數(shù)之和為邊數(shù)的兩倍，即證 圖中每條邊(包括環(huán))均有兩個端點, 所以在計算各頂點度數(shù)之和時, 每條邊

9、均提供2度, m條邊共提供2m度.推論 任何圖(無向圖和有向圖)中，度數(shù)為奇數(shù)的結(jié)點的個數(shù)為偶數(shù)。16握手定理定理7.1.1 設(shè)圖G=(V, E)為無向圖或有向圖定理7.1.2定理7.1.2 在有向圖中，所有結(jié)點的入度之和與所有結(jié)點的出度之和相等，都等于圖中的有向邊數(shù)。證 在有向圖中，每條有向邊均有一個起點和一個終點。于是在計算圖中各結(jié)點的出度之和與各結(jié)點的入度之和時，每條有向邊各提供一個出度和一個入度。當(dāng)然e條有向邊共提供e個出度和e個入度。因此所有結(jié)點的入度之和與所有結(jié)點的出度之和相等，都等于圖中的有向邊數(shù)e。定理7.1.2定理7.1.2 在有向圖中，所有結(jié)點的入度之圖的度數(shù)列設(shè)無向圖G的

10、頂點集V=v1，v2，vnG的度數(shù)列: d(v1), d(v2), , d(vn)如右圖度數(shù)列:4,4,2,1,3設(shè)有向圖D的頂點集V=v1，v2，vnD的度數(shù)列d(v1), d(v2), , d(vn)D的出度列: d+(v1), d+(v2), , d+(vn)D的入度列: d(v1), d(v2), , d(vn)如右圖度數(shù)列:5,3,3,3 出度列:4,0,2,1 入度列:1,3,1,218e1e2e3e4e5e6e7v5v1v2v3v4e1e2e3e4e5e6e7dabc圖的度數(shù)列設(shè)無向圖G的頂點集V=v1，v2，vn1例題 例 自然數(shù)序列(3，3，2，2，1)，(4，2，2，1，1

11、)能作為圖的結(jié)點的度數(shù)序列嗎？為什么？ 解 在(3，3，2，2，1)中各個數(shù)之和為奇數(shù)，由握手定理可知，(3，3，2，2，1)不能作為圖的結(jié)點的度數(shù)序列。 (4，2，2，1，1)能作為圖的結(jié)點的度數(shù)序列，下圖中的兩個圖都是以（4,2,2,1,1）為結(jié)點度數(shù)序列。例題 例 自然數(shù)序列(3，3，2，2，1)，(4，2實例20例2 已知圖G有10條邊, 4個3度頂點, 其余頂點的度數(shù)均小于等于2, 問G至少有多少個頂點? 解 設(shè)G有n個頂點. 由握手定理, 43+2(n-4)210解得 n8例3 已知5階有向圖的度數(shù)列和出度列分別為3,3,2,3,3和1,2,1,2,1, 求它的入度列解 2,1,1

12、,1,2實例20例2 已知圖G有10條邊, 4個3度頂點, 其余頂點實例例4 證明不存在具有奇數(shù)個面且每個面都具有奇數(shù)條棱的多面體.21證 用反證法. 假設(shè)存在這樣的多面體, 作無向圖G=,其中 V=v | v為多面體的面, E=(u,v) | u,vV u與v有公共的棱 uv.根據(jù)假設(shè), |V|為奇數(shù)且vV, d(v)為奇數(shù). 這與握手定理的推論矛盾.實例例4 證明不存在具有奇數(shù)個面且每個面都具有奇數(shù)條棱的217.1.3 圖的分類定義7.1.8 設(shè)圖G=（V，E）為無向圖或有向圖，如果G中不含平行邊，也不含環(huán)，則稱為簡單圖。定義7.1.9 設(shè)圖G=（V，E）為無向圖或有向圖，如果G中含有平行

13、邊，則稱為多重圖。簡單圖多重圖多重圖簡單圖7.1.3 圖的分類定義7.1.8 設(shè)圖G=（V，E）為無圖的應(yīng)用1、航班路線圖 有向多重圖2、微博關(guān)注圖 有向簡單圖3、合作關(guān)系圖 無向簡單圖或多重圖圖的應(yīng)用完全圖(1)定義7.1.10 設(shè)G =（V，E）是n階無向簡單圖，若G中任何結(jié)點都與其余的n-1個結(jié)點相鄰，則稱G為n階無向完全圖，記作Kn。 圖7.1.7 完全圖 頂點數(shù)n, 邊數(shù)m=n(n-1)/2, (G)=(G)=n-1K3K5完全圖(1)定義7.1.10 設(shè)G =（V，E）是n階無完全圖(2)設(shè)G =（V，E）為n階有向簡單圖，若對于V中任意的兩個結(jié)點u和v，既有有向邊(u，v)，又有

14、有向邊(v，u)，則稱G是n階有向完全圖。 頂點數(shù)n, 邊數(shù)m=n(n-1), +(D)=+(D)= -(D)= -(D)=n-1, (D)=(D)=2(n-1) 無特別說明時，完全圖均指無向完全圖。完全圖(2)設(shè)G =（V，E）為n階有向簡單圖，若對于V中任定理7.1.3定理7.1.3 設(shè)G為任意n階無向簡單圖，則(G) n-1。證明：略定理7.1.3定理7.1.3 設(shè)G為任意n階無向簡單圖，則例題例5 判斷下列各非負(fù)整數(shù)列是否是簡單圖的結(jié)點度數(shù)序列？（1）（5,5,4,4,2,1）（2）（5,4,3,2,2）（3）（3,3,2,2,1,1）（4） 解 （1）根據(jù)握手定理的推論可知，不是圖的

15、結(jié)點度數(shù)序列，因為有3個奇數(shù)。 （2）中有5個數(shù)，最大數(shù)是5，根據(jù)定理7.1.3，它不是簡單圖的結(jié)點序列。 （3）是簡單圖的結(jié)點序列。下圖的兩個無向簡單圖都是（3,3,2,2,1,1）為結(jié)點度數(shù)序列。 （4）中的最大值d1n, 根據(jù)定理7.1.3，不是簡單圖的結(jié)點序列。例題例5 判斷下列各非負(fù)整數(shù)列是否是簡單圖的結(jié)點度數(shù)序列？正則圖定義7.1.11 設(shè)G為n階無向簡單圖，若vV（G），均有d(v)=k,則稱G為k-正則圖。 K52正則圖4正則圖 3正則圖彼得松圖正則圖定義7.1.11 設(shè)G為n階無向簡單圖，若vV（G正則圖 根據(jù)握手定理，n階k-正則圖的邊數(shù) 。當(dāng)k為奇數(shù)時，n為偶數(shù)。當(dāng)k=0

16、時，0-正則圖就是n階零圖。n階無向完全圖是(n-1)-正則圖。正則圖 根據(jù)握手定理，n階k-正則圖的邊數(shù) 環(huán)圖和輪圖定義7.1.12 如果圖G =（V，E）的結(jié)點集V=v1，v2，vn（n3），邊集E=（v1，v2），（v2，v3），（ vn-1，vn），（vn，v1），則稱G為環(huán)圖，記為Cn。下圖是C3,C4 ,C5 ,C6。定義7.1.13 當(dāng)給環(huán)圖Cn-1（n4）添加一個結(jié)點，并把這個結(jié)點和Cn-1里的每個結(jié)點逐個連接后得到的圖成為輪圖，記作Wn。下圖是輪圖W4，W5，W6，W7。環(huán)圖和輪圖定義7.1.12 如果圖G =（V，E）的結(jié)點集31定義7.1.14 如果圖G =（V，E）有2

17、n個結(jié)點，每個結(jié)點表示一個長度為n的位串，任何兩個相鄰的結(jié)點表示的位串只有一位不同，則稱G稱為n方體圖，記作Qn。方體圖0 110110001010101100000111011001Q1 Q2 Q331定義7.1.14 如果圖G =（V，E）有2n個結(jié)點，方體圖對任意nN ，Qn 是將兩個Qn-1 圖的對應(yīng)結(jié)點連接起來的簡單圖 . Q0 有 1 個結(jié)點.Q0Q1Q2Q3Q4結(jié)點數(shù): 2n. 邊數(shù)： n2n-1方體圖對任意nN ，Qn 是將兩個Qn-1 圖的對應(yīng)結(jié)點連二分圖定義7.1.15 如果圖G =（V，E）的結(jié)點集V能劃分為兩個子集：V1和V2，使每條邊有一個端點在V1中,另一個端點在V

18、2中，則稱該圖為二分圖（或二部圖）。定義7.1.16 二分圖G =（V，E）的結(jié)點集V能劃分為兩個子集：V1和V2，若V1中的每個結(jié)點和V2中的每個結(jié)點均有邊相連，則稱G為完全二分圖。若|V1|=m，|V2|=n, 則可記為Km,n。下圖所示的是K2,3和K3,3。 二分圖定義7.1.15 如果圖G =（V，E）的結(jié)點集V能帶權(quán)圖定義7.1.17 每個結(jié)點或每條邊都帶有數(shù)值的圖稱為帶權(quán)圖。 可以用有序三元組或有序四元組表示帶權(quán)圖。如G=(V,E,f)，G=(V,E,g) 或G=(V,E,f,g)，其中V是結(jié)點集，E是邊集， f是結(jié)點所帶的權(quán)的集合，g是邊所帶的權(quán)的集合。下圖左邊為邊帶權(quán)圖，右邊

19、為結(jié)點帶權(quán)圖。 34 6 2 1帶權(quán)圖定義7.1.17 每個結(jié)點或每條邊都帶有數(shù)值的圖7.1.4 子圖與補圖定義7.1.18 設(shè)圖G=（V，E）設(shè)eE，從G圖中刪去邊e得到的圖表示為G-e,稱為刪除邊運算；設(shè)E1E，從G圖中刪去E1的所有邊得到的圖表示為G- E1,稱為刪除邊集運算。設(shè)vV，從G圖中刪去結(jié)點v及v關(guān)聯(lián)的所有邊得到的圖表示為Gv,稱為刪除結(jié)點運算；設(shè)V1V，從G圖中刪去V1中所有結(jié)點及它們關(guān)聯(lián)的所有邊得到的圖表示為GV1,稱為刪除結(jié)點集運算。設(shè)e=(u,v)E，從G圖中刪去邊e,將e的兩個端點u、v用一個新的結(jié)點w代替，將u,v關(guān)聯(lián)的所有邊都關(guān)聯(lián)結(jié)點w，稱為邊e的收縮，記為Ge。

20、設(shè)u,vV，在u,v之間加一條邊（u,v），稱為加新邊，表示為G(u,v)(或G+(u,v)。7.1.4 子圖與補圖定義7.1.18 設(shè)圖G=（V，例題在下圖中，(1)為圖G，(2)為G-e1, (3)為G-e1,e2， (4)為G-v3, (5)為G-v1,v3, (6)為Ge1。例題在下圖中，(1)為圖G，(2)為G-e1, (3)為G-子圖定義7.1.19 設(shè)G=（V，E）和G1=(V1，E1)是兩個圖。若V1V，且E1E，則稱G1是G的子圖，G是G1的母圖，記作G1 G。若G1 G且G1 G(即V1 V, 或E1 E)，則稱G1是G的真子圖。若G1G且V1 =V，則稱G1是G的生成子圖

21、。對圖G =（V，E），設(shè)V1V且V1 ，以V1為結(jié)點集，以兩端點均在V1中的全體邊為邊集的G的子圖，稱G1為G的由結(jié)點集V1導(dǎo)出的子圖，記為G（V1）。對圖G=（V，E），設(shè)E1E且E1 ，以E1為邊集，以E1中邊關(guān)聯(lián)的結(jié)點的全體為結(jié)點集的G的子圖，稱G1為G的由邊集E1導(dǎo)出的子圖，記為G（E1）。子圖定義7.1.19 設(shè)G=（V，E）和G1=(V1，E38例題(1),(2),(3)是(1)的子圖, (2),(3)是真子圖, (1)是母圖.(1),(3)是(1)的生成子圖.(2)是d,e,f 的導(dǎo)出子圖, 也是e5, e6, e7導(dǎo)出子圖.(3)是e1, e3, e5, e7的導(dǎo)出子圖aab

22、bccdddeee f f f e1 e1 e2 e3 e3 e4 e5 e5 e5 e6 e6 e7 e7 e7(1)(2)(3)38例題(1),(2),(3)是(1)的子圖, (2),(3補圖定義7.1.20 設(shè)G=(V，E)是n階無向簡單圖或有向簡單圖。以V為結(jié)點，以所有能使G成為完全圖需添加的邊組成的集合為邊集的圖，稱為G相對于完全圖的補圖，簡稱G的補圖，記作G。 補圖定義7.1.20 設(shè)G=(V，E)是n階無向簡單圖或例題證明：在任意6個人的集會上，總會有3個人以前互相認(rèn)識或有3個人以前互相不認(rèn)識（假設(shè)認(rèn)識是相互的）。即證明6個結(jié)點的無向圖G或其補圖G中至少有一個完全子圖K3。證明：

23、考慮完全圖K6,結(jié)點v1與其余5個結(jié)點各有一條邊相連，這5條邊一定有3條邊在G或G中。假設(shè)有3條邊在G圖中，這3條邊為（v1,v2）、（v1,v3）、（v1,v4）。對于結(jié)點v2、v3、v4，若在G中v2、v3、v4間無邊連接，則v2、v3、v4相互不認(rèn)識，如果至少存在一條邊，如v2、v3間存在一條邊，則在v1、v2、v3三個結(jié)點都有邊連接，構(gòu)成一個K3子圖，即有三個人相互認(rèn)識。因此，總會有三個人相互認(rèn)識或不認(rèn)識。例題證明：在任意6個人的集會上，總會有3個人以前互相認(rèn)識或有7.1.5 圖的同構(gòu)定義7.1.21 設(shè)兩個圖G=（V，E）和G=（V ，E），如果從V到V 存在雙射函數(shù)f，使得對于任意

24、的u，vV，(u，v) E, 當(dāng)且僅當(dāng)(f(u)，f(v) E ；如果在u，v間存在平行邊，則關(guān)聯(lián)于結(jié)點u，v的平行邊數(shù)與關(guān)聯(lián)于結(jié)點f(u)，f(v)的平行邊數(shù)相同，則稱G與G是同構(gòu)的，記作G G 。7.1.5 圖的同構(gòu)定義7.1.21 設(shè)兩個圖G=（V，E判斷兩個圖同構(gòu)的必要條件1)必須具有相同的頂點數(shù)；2)必須具有相同的邊數(shù)；3)度數(shù)相同的結(jié)點數(shù)相等。（對應(yīng)頂點的度數(shù)相同.）4)相同長度的回路數(shù)相同。 判斷兩個圖同構(gòu)的必要條件1)必須具有相同的頂點數(shù)； 例題例6 畫出4階3條邊的所有非同構(gòu)的無向簡單圖解 總度數(shù)為6, 分配給4個頂點, 最大度為3, 且奇度頂點數(shù)為偶數(shù), 有下述3個度數(shù)列:

25、 (1) 1,1,1,3;(2)1,1,2,2;(3)0,2,2,2.431,1,1,31,1,2,20,2,2,2 例題例6 畫出4階3條邊的所有非同構(gòu)的無向簡單圖431,1例題例7 畫出3個以1,1,1,2,2,3為度數(shù)列的非同構(gòu)的無向簡單圖44例題例7 畫出3個以1,1,1,2,2,3為度數(shù)列的非同構(gòu)的自互補圖定義7.1.22 如果一個圖同構(gòu)于它的補圖,則稱此圖為自互補圖。例8 試證明：一個圖為自互補圖，其對應(yīng)的完全圖的邊數(shù)必為偶數(shù)。 證明 設(shè)G為自互補圖，G有e條邊，并設(shè)G對應(yīng)的完全圖的邊數(shù)為m，則G的補圖的邊數(shù)為me。對于自互補圖G，有G G，所以e = me，m=2e 是偶數(shù)。 自

26、互補圖定義7.1.22 如果一個圖同構(gòu)于它的補圖,則稱7.2 通路與回路、連通的概念7.2.1 通路與回路7.2.2 連通的概念467.2 通路與回路、連通的概念7.2.1 通路與回路4647定義7.2.1 給定圖G=（V，E）中，以v0為起點，vn為終點的由結(jié)點和邊交替出現(xiàn)的序列v0e1v1e2v2vn-1envn稱為從結(jié)點v0到vn的長度為n的通路。G是無向圖時，其中的邊ei的端點是vi-1和vi（i=1，2，n）；G是有向圖時，其中的有向邊ei的起點是vi-1，終點是vi（i=1，2，n）。 7.2.1 通路與回路47定義7.2.1 給定圖G=（V，E）中，以v0為起點，v通路與回路若一

27、條通路的起點和終點是同一點，稱它是一條回路。若通路中的所有邊互不相同，則稱它為簡單通路或跡。若回路中的所有邊互不相同，則稱它為簡單回路或閉跡。若通路中的所有結(jié)點互不相同，所有邊互不相同，則稱它為基本通路或初級通路、路徑。若回路中的所有結(jié)點互不相同，所有邊互不相同，則稱它為基本回路或初級回路、圈。一條通路或回路包含的邊的數(shù)目稱為通路或回路的長度。如果一條回路的長度為奇(偶)數(shù)，則稱為奇(偶)回路。通路與回路若一條通路的起點和終點是同一點，稱它是一條回路。例題v1e1v2e9v6e9v2e8v6e7v5是從結(jié)點v1到v5的長度為5的通路，v2e4v4e5v5e6 v2e1v1e10v6是簡單通路，

28、v2e4v4e5v5e6 v2e1v1e10v6e9v2是簡單回路，v3e3v4e5v5e6v2e1v1e10v6是基本通路，v2e1v1e10v6e7v5e6 v2 是基本回路或圈。例題v1e1v2e9v6e9v2e8v6e7v5是從結(jié)點v1例題v1e2v2e5v4e4v3是從結(jié)點v1到v3的長度為3的通路，v1e2v2e5v4e6v2是簡單通路，v1e2v2e5v4e4v3 是基本通路。在有向圖中要注意邊的方向，通路上一條邊的終點是這條通路下一條邊的起點例題v1e2v2e5v4e4v3是從結(jié)點v1到v3的長度為351說明(1) 表示方法 按定義用頂點和邊的交替序列, =v0e1v1e2el

29、vl 用邊序列, =e1e2el 簡單圖中, 用頂點序列, =v0v1vl(2) 在無向圖中, 長度為1的圈由環(huán)構(gòu)成.長度為2的圈由兩條平行邊構(gòu)成. 在無向簡單圖中, 所有圈的長度3. 在有向圖中, 長度為1的圈由環(huán)構(gòu)成. 在有向簡單圖中, 所有圈的長度2.51說明(1) 表示方法52說明(續(xù))(3) 初級通路(回路)是簡單通路(回路), 但反之不真初級通路非初級的簡單通路初級回路非初級的簡單回路52說明(續(xù))(3) 初級通路(回路)是簡單通路(回路), 定理定理7.2.1 在n階圖G中，若從結(jié)點u到v（uv）存在通路，則從u到v存在長度小于或等于n-1的通路。證明： 見課本。推論 在n階圖G

30、中，若從結(jié)點u到v（uv）存在通路，則從u到v存在長度小于或等于n1的基本通路。證明： 若通路中沒有相同的頂點(即基本通路), 長度必 n1.若有相同的頂點, 刪去這兩個頂點之間的這一段, 仍是u到v的通路. 重復(fù)進(jìn)行, 直到?jīng)]有相同的頂點為止.定理定理7.2.1 在n階圖G中，若從結(jié)點u到v（uv）定理定理7.2.2 在n階圖G中，若從結(jié)點u到自身存在回路，則回路的長度小于或等于n。推論 在n階圖G中，若從結(jié)點u到自身存在回路，則一定存在從結(jié)點u到自身的長度小于或等于n的基本回路。定理定理7.2.2 在n階圖G中，若從結(jié)點u到自身存在回路55短程線與距離設(shè)u,v為圖G中任意兩個結(jié)點，u與v之

31、間的短程線:u與v之間長度最短的通路(設(shè)u與v連通)u與v之間的距離d(u,v):u與v之間短程線的長度若u與v不連通, 規(guī)定d(u,v)=.性質(zhì)：(1) d(u,v)0, 且d(u,v)=0 u=v(2) d(u,v)=d(v,u)(3) d(u,v)+d(v,w)d(u,w) 例如 a與e之間的短程線:ace,afe. d(a,e)=2, d(a,h)=abcde f ghi55短程線與距離設(shè)u,v為圖G中任意兩個結(jié)點，例如 a與e通路的應(yīng)用六度分割理論電影演員合作圖中的貝肯數(shù)（bacon number）論文合作關(guān)系圖中的埃德斯數(shù)(Erds number)通路的應(yīng)用六度分割理論7.2.2

32、連通的概念定義7.2.3 若無向圖G中任意兩結(jié)點間都有一條通路(長度1)，則稱G是連通圖；否則，稱G是非連通圖。連通關(guān)系 R=| u,v V且u與v連通. R是等價關(guān)系連通分支: V關(guān)于R的等價類的導(dǎo)出子圖設(shè)V/R=V1,V2,Vk, G的連通分支為GV1,GV2,GVk連通分支數(shù)W(G)=kG是連通圖 W(G)=1 7.2.2 連通的概念定義7.2.3 若無向圖G中任意兩結(jié)定理定理7.2.3 設(shè)簡單圖G=（V，E）有n個結(jié)點，e條邊，w個連通分支，則n-we。證明 (用歸納法來證明)（1）當(dāng)e=0時，也就是對于n個結(jié)點的零圖，w=n，則n-we成立。 （2）假定邊數(shù)為e-1的簡單圖結(jié)論成立。

33、對于邊數(shù)為e的簡單圖G，從G中刪去一條邊，得到邊數(shù)為e-1的簡單圖G。分兩種情況分析：(a) 刪去一條邊的圖G的連通分支數(shù)沒有增加，即G有n個結(jié)點，w個分支，e-1條邊，由歸納假設(shè)有n-w e-1，所以n-we成立。(b) 刪去一條邊的圖G的連通分支數(shù)增加，即G有n個結(jié)點，w+1個分支，e-1條邊，由歸納假設(shè)有n-(w+1) e-1,所以n-we成立。定理定理7.2.3 設(shè)簡單圖G=（V，E）有n個結(jié)點，e條點割集和邊割集定義7.2.4 設(shè)無向圖G=(V,E), VV, 若W(GV)W(G)且VV, W(GV)=W(G), 則稱V為G的點割集. 若v為點割集, 則稱v為割點.設(shè)EE, 若W(G

34、E)W(G)且EE, W(GE)=W(G), 則稱E為G的邊割集. 若e為邊割集, 則稱e為割邊或橋.abcde fge1e2e3e4e5e6e7e8e9e, f點割集:e,f ,割點:c,d 橋:e8,e9邊割集:e8,e9,e1,e2,e1, e3, e6,e1, e3, e4, e7點割集和邊割集定義7.2.4 設(shè)無向圖G=(V,E), 60說明Kn無點割集n階零圖既無點割集，也無邊割集.若G連通，E為邊割集，則W(GE)=2若G連通，V為點割集，則W(GV)260說明Kn無點割集例題例7.2.2 試證明2n個城市，如果每個城市至少可以和另外n個城市可以相互直航，那么這2n個城市中任何兩

35、個之間可互相通航 (有些可能要通過另外的城市中轉(zhuǎn))（即證明:2n個結(jié)點，每個結(jié)點的度數(shù) n的簡單圖是連通的。）證明 設(shè)有2n個結(jié)點的圖G不連通，則G中至少包含兩個連通分支,而且必有一個分支的結(jié)點數(shù) n，即使這個分支是完全圖，其每個結(jié)點的度數(shù)d(v) n-1，和d(v) n矛盾。所以圖G只有一個連通分支，G是連通的。例題例7.2.2 試證明2n個城市，如果每個城市至少可以有向圖的連通性及其分類定義7.2.5 設(shè)G=（V，E）是一個有向圖，對G中任意兩個結(jié)點u和v，若從u到v存在通路，則稱由u到v是可達(dá)的，否則稱由u到v是不可達(dá)的。若從u到v存在通路，且從v到u存在通路，則稱u和v是相互可達(dá)的。規(guī)

36、定一個結(jié)點到自己總是可達(dá)的。有向圖的結(jié)點之間的可達(dá)關(guān)系具有自反性和傳遞性，不具有對稱性。62有向圖的連通性及其分類定義7.2.5 設(shè)G=（V，E）是一個有向連通圖定義7.2.6 設(shè)G=（V，E）是有向圖。如果圖G的任意兩個結(jié)點間至少從一個結(jié)點到另一個結(jié)點是可達(dá)的，則稱G是單向連通的。如果圖G的任意兩個結(jié)點間是互相可達(dá)的，則稱G是強連通的。如果圖G在略去有向邊的方向后得到的無向圖是連通的，則稱G是弱連通的。 具有三種連通性中的任何一種的有向圖都稱為有向連通圖。有向連通圖定義7.2.6 設(shè)G=（V，E）是有向圖。64實例 強連通單連通弱連通64實例 強連通單連通弱連通頂點集上的互相可達(dá)關(guān)系 對于u

37、，vV，u與v有關(guān)系，當(dāng)且僅當(dāng)從u可達(dá)v，并且從v可達(dá)u。頂點集上的互相可達(dá)關(guān)系是等價關(guān)系。 利用互相可達(dá)關(guān)系可將頂點集V劃分為V1，V2，,Vw,每個Vi的任兩個頂點都是互相可達(dá)的.所以每個Vi導(dǎo)出的子圖Gi是強連通的,稱為G的一個強分圖.頂點集上的互相可達(dá)關(guān)系頂點集上的互相可達(dá)關(guān)系 對于u，vV，u與v有關(guān)系，有向圖的強連通分支.GG(V1)G(V2)G(V3)V1=v1,v7 V2=v2,v3, v5,v6 V3=v4 注意:有向圖中不一定每條邊都一定屬于一個強連通分支.而無向圖中每條邊必屬于一個連通分支. 有向圖中每個頂點必屬于一個強連通分支.定理7.2.4 ：有向圖G是強連通的當(dāng)且僅

38、當(dāng)G中存在經(jīng)過每個結(jié)點的回路。有向圖的強連通分支.GG(V1)G(V2)G(V3)V1=有向圖的應(yīng)用資源分配圖是有向圖：G=（V，E）,其中V是頂點的集合，E是邊的集合。頂點集合分為兩部分：（1）P=P1,P2,Pn,它由進(jìn)程集合的所有活動進(jìn)程組成。（2） R=r1,r2,rm,它由進(jìn)程集合所涉及的全部資源類型組成。邊集合分為以下兩種：（1）申請邊(Pi，rj),表示進(jìn)程Pi申請一個單位的rj資源，但當(dāng)前Pi在等待該資源。（2）賦給邊(rj，Pi),表示有一個單位的rj資源已分配給進(jìn)程Pi。有向圖的應(yīng)用資源分配圖是有向圖：G=（V，E）,其中V是頂點資源分配圖（1）G1 (2)G2圖G1中有一

39、個回路，所以是死鎖狀態(tài)。圖G2也有一個回路：P1r1P3r2P1，然而沒有出現(xiàn)死鎖。因為進(jìn)程P2和P4能釋放占有的資源r1和r2,然后就可以將r1和r2分給P1和P3,這樣環(huán)路就打開了。資源分配圖中存在回路是死鎖存在的必要條件，但不是充分條件。P1P3r2r1r1P1P2P3P4r2資源分配圖（1）G1 697.3 圖的表示7.3.1 鄰接表7.3.2 鄰接矩陣7.3.3 可達(dá)矩陣7.3.4 關(guān)聯(lián)矩陣697.3 圖的表示7.3.1 鄰接表70定義7.3.1 列出圖的每一個結(jié)點和它的所有鄰接結(jié)點的表稱為鄰接表。例 1 用鄰接表表示無向簡單圖。例 2 用鄰接表表示有向簡單圖。7.3.1 鄰接表無向

40、簡單圖的鄰接表結(jié)點鄰接結(jié)點ab,cba,c,dca,b,d,edb,cec有向圖的鄰接表起點終點abbc,dca,b,d,edeb,c70定義7.3.1 列出圖的每一個結(jié)點和它的所有鄰接結(jié)點的表7.3.2 鄰接矩陣定義7.3.2 設(shè)圖G=（V，E）是有向圖，V=v1，v2，vn，G的鄰接矩陣為 ，其中7.3.2 鄰接矩陣定義7.3.2 設(shè)圖G=（V，E）是72例題A=1 1 0 00 0 1 01 0 0 01 0 2 0v1v2v3v472例題A=1 1 0 0v1v2v3v4有向圖中的通路數(shù)與回路數(shù)定理7.3.1 設(shè)A是有向圖G=（V，E）的鄰接矩陣，V=v1，v2，vn， ，則 表示G中

41、從vi到vj的長度為k的所有有向路的數(shù)目，其中 是從vi到自身的長度為k的所有回路的數(shù)目。證明 用歸納法證明，對k作歸納。當(dāng)k=1時，由鄰接矩陣的定義知結(jié)論成立。設(shè)k=m時，結(jié)論成立。當(dāng)k=m+1時，有 ，從而 。顯然 等于從vi出發(fā)經(jīng)vp到vj的長度為m+1的有向路的數(shù)目。由于p的任意性 等于G中從vi到vj的長度為m+1的所有有向路的數(shù)目。73有向圖中的通路數(shù)與回路數(shù)定理7.3.1 設(shè)A是有向圖G=有向圖中的通路數(shù)與回路數(shù)(續(xù))推論設(shè)矩陣 則Bl中的元素表示圖G中從結(jié)點vi到vj的長度小于等于l的所有通路的總數(shù)。其中bii(l)是從vi到自身的長度小于等于l的所有回路的總數(shù)目。74有向圖中

42、的通路數(shù)與回路數(shù)(續(xù))推論設(shè)矩陣 74實例(續(xù)) 75A=1 1 0 00 0 1 01 0 0 01 0 2 0A2=1 1 1 01 0 0 01 1 0 03 1 0 0A3=2 1 1 01 1 0 01 1 0 03 3 1 0A4=3 2 1 01 1 0 02 1 1 04 3 1 0v1到v2長為3的通路有1條v1到v3長為3的通路有1條v1到自身長為4的回路有3條D中長為3的通路共有15條,其中回路3條v1v2v3v4實例(續(xù)) 75A=1 1 0 0A2=1 1 無向圖的鄰接矩陣定義7.3.3 設(shè)圖G=（V，E）是無向圖，V=v1，v2，vn，G的鄰接矩陣為 ，其中例3 寫

43、出如下圖所示的無向圖G的鄰接矩陣。解 鄰接矩陣為無向圖的鄰接矩陣定義7.3.3 設(shè)圖G=（V，E）是無向圖例題例4 畫出給定的鄰接矩陣所表示的圖。（1） （2） （a） （b）abcabc (c)v1v2v4v3解 （1）鄰接矩陣（1）所表示的圖可以是無向圖（a）或有向圖（b）。 （2）鄰接矩陣（2）所表示的圖見圖（c)。例題例4 畫出給定的鄰接矩陣所表示的圖。abcabcv1例題例5 判定下面的鄰接矩陣A所表示的圖G是否強連通圖？解因為B3中存在為0的元素，所以圖G不是強連通圖。v1v2v3例題例5 判定下面的鄰接矩陣A所表示的圖G是否強連通圖？v1例題例6 判斷下面的兩個圖是否同構(gòu)？解 兩

44、個圖的鄰接矩陣為： 將矩陣A2的第2行元素和第3行元素交換，得到矩陣 ，然后將矩陣 的第2列元素和第3列元素交換，得到矩陣 。 矩陣 和矩陣 相同，所以兩個圖同構(gòu)。例題例6 判斷下面的兩個圖是否同構(gòu)？ 7.3.3 可達(dá)矩陣定義7.3.4 設(shè)圖G=（V，E）是有向圖，V=v1，v2，vn，A是G的鄰接矩陣， G的可達(dá)矩陣為 ， i，j=1,2，n, 其中 7.3.3 可達(dá)矩陣定義7.3.4 設(shè)圖G=（V，E）是例題 寫出右圖的可達(dá)矩陣。解 所以可達(dá)矩陣為例題 寫出右圖的可達(dá)矩陣。由可達(dá)矩陣求強連通分支對可達(dá)矩陣P求轉(zhuǎn)置PT，PT中的(i,j)的元素為 ，定義一個矩陣P PT，使得它的(i,j)的元素為 ，于是矩陣P PT的第i行的“1”對應(yīng)的結(jié)點組成一個含有結(jié)點vi的強連通分支。矩陣P PT的第2行的兩個“1”表明結(jié)點v2和v3是一個強連通分支。由可達(dá)矩陣求強連通分支對可達(dá)矩陣P求轉(zhuǎn)置PT，PT中的(i,83則稱(mij)nm為G的關(guān)聯(lián)矩陣, 記為M(G).定義7.3.5 設(shè)圖G=(V,E)是無環(huán)的有向圖, V=v1, v2, , vn, E=e1, e2, , em. 令7.3.4 關(guān)聯(lián)矩陣83則稱(mij)nm為G的關(guān)聯(lián)矩陣, 記為M(G).定義84例題e