離散數(shù)學屈婉玲第九章

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

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

3、 簡簡稱稱邊邊例例 有向圖有向圖D=, 其中其中V=a,b,c,dE=, , 注意：圖的集合表示與圖形表示之間的對應注意：圖的集合表示與圖形表示之間的對應5相關概念相關概念1. 無向圖和有向圖通稱圖無向圖和有向圖通稱圖. 記頂點集記頂點集V(G), 邊集邊集E(G). 2. 圖的階圖的階, n階圖階圖.3. n 階零圖階零圖Nn, 平凡圖平凡圖N1.4. 空圖空圖.5. 標定圖與非標定圖標定圖與非標定圖.6. 有向圖的基圖有向圖的基圖.7. 無向圖中頂點與邊的關聯(lián)及關聯(lián)次數(shù)無向圖中頂點與邊的關聯(lián)及關聯(lián)次數(shù), 頂點與頂點、邊與頂點與頂點、邊與 邊的相鄰關系邊的相鄰關系.8. 有向圖中頂點與邊的關

4、聯(lián)有向圖中頂點與邊的關聯(lián), 頂點與頂點、邊與邊的相鄰關頂點與頂點、邊與邊的相鄰關 系系.9. 環(huán)環(huán), 孤立點孤立點.6多重圖與簡單圖多重圖與簡單圖定義定義9.3 無向圖中關聯(lián)同一對頂點的無向圖中關聯(lián)同一對頂點的2條和條和2條以上的邊稱為條以上的邊稱為平行邊平行邊. 有向圖中有向圖中2條和條和2條以上始點、終點相同的邊稱為條以上始點、終點相同的邊稱為平平行邊行邊. 平行邊的條數(shù)稱為平行邊的條數(shù)稱為重數(shù)重數(shù).含平行邊的圖稱為含平行邊的圖稱為多重圖多重圖, 不含平行邊和環(huán)的圖稱為不含平行邊和環(huán)的圖稱為簡單圖簡單圖.定義定義9.4 設設G=為無向圖為無向圖, v V, 稱稱v作為邊的端點的次作為邊的端

5、點的次數(shù)之和為數(shù)之和為v的的度數(shù)度數(shù), 簡稱簡稱度度, 記作記作d(v). 設設D=為有向圖為有向圖, v V, 稱稱v作為邊的始點的次數(shù)之和作為邊的始點的次數(shù)之和為為v的的出度出度, 記作記作d+(v); 稱稱v作為邊的終點的次數(shù)之和為作為邊的終點的次數(shù)之和為v的的入入度度, 記作記作d (v); 稱稱d+(v)+d (v)為為v的的度數(shù)度數(shù), 記作記作d(v).7頂點的度數(shù)頂點的度數(shù)設設G=為無向圖為無向圖, G的的最大度最大度 (G)=maxd(v) | v V G的的最小度最小度 (G)=mind(v) | v V 設設D=為無向圖為無向圖, D的的最大度最大度 (D)=maxd(v)

6、 | v V D的的最小度最小度 (D)=mind(v) | v V D的的最大出度最大出度 +(D)=maxd+(v) | v V D的的最小出度最小出度 +(D)=mind+(v) | v V D的的最大入度最大入度 (D)=maxd (v) | v V D的的最小入度最小入度 (D)=mind (v) | v V 懸掛頂點懸掛頂點: 度數(shù)為度數(shù)為1的頂點的頂點, 懸掛邊懸掛邊: 與懸掛頂點關聯(lián)的邊與懸掛頂點關聯(lián)的邊.偶度偶度(奇度奇度)頂點頂點: 度數(shù)為偶數(shù)度數(shù)為偶數(shù)(奇數(shù)奇數(shù))的頂點的頂點8實例實例d(v1)=4, d(v2)=4, d(v3)=2, d(v4)=1, d(v5)=3.

7、 =4, =1.v4是懸掛點是懸掛點, e7是懸掛邊是懸掛邊. 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, d (d)=2, d(d)=3, +=4, +=0, =3, =1, =5, =3.9定理定理9.1 在任何無向圖中在任何無向圖中, 所有頂點的度數(shù)之和等于邊數(shù)的所有頂點的度數(shù)之和等于邊數(shù)的2倍倍.證證 G中每條邊中每條邊 (包括環(huán)包括環(huán)) 均有兩個端點，所以在計算均有兩個端點，所以在計算G中各頂中各頂點度數(shù)之和時，每條邊均提供點度數(shù)之和時，每條邊均提供2度，

8、度，m 條邊共提供條邊共提供 2m 度度.握手定理握手定理定理定理9.2 在任何有向圖中，所有頂點的度數(shù)之和等于邊數(shù)的在任何有向圖中，所有頂點的度數(shù)之和等于邊數(shù)的2倍倍; 所有頂點的入度之和等于所有頂點的出度之和所有頂點的入度之和等于所有頂點的出度之和, 都等于邊數(shù)都等于邊數(shù).推論推論 任何圖任何圖 (無向或有向無向或有向) 中，奇度頂點的個數(shù)是偶數(shù)中，奇度頂點的個數(shù)是偶數(shù).證證 由握手定理由握手定理, 所有頂點的度數(shù)之和是偶數(shù)所有頂點的度數(shù)之和是偶數(shù), 而偶度頂點的度而偶度頂點的度數(shù)之和是偶數(shù)數(shù)之和是偶數(shù), 故奇度頂點的度數(shù)之和也是偶數(shù)故奇度頂點的度數(shù)之和也是偶數(shù). 所以奇度頂所以奇度頂點的

9、個數(shù)必是偶數(shù)點的個數(shù)必是偶數(shù)10例例1 無向圖無向圖G有有16條邊，條邊，3個個4度頂點，度頂點，4個個3度頂點，其余度頂點，其余均為均為2度頂點度，問度頂點度，問G的階數(shù)的階數(shù)n為幾？為幾？解解 本題的關鍵是應用握手定理本題的關鍵是應用握手定理. 設除設除3度與度與4度頂點外，還有度頂點外，還有x個頂點個頂點, 由握手定理由握手定理, 16 2=32 = 3 4+4 3+2x解得解得 x = 4, 階數(shù)階數(shù) n = 4+4+3=11. 握手定理應用握手定理應用定理定理9.3 設設G為任意為任意n階無向簡單圖，則階無向簡單圖，則 (G) n 1圖的同構圖的同構定義定義9.5 設設G1=, G2

10、=為兩個無向圖為兩個無向圖(兩個有向兩個有向圖圖)，若存在雙射函數(shù)，若存在雙射函數(shù)f:V1V2, 使得使得 vi,vj V1, (vi,vj) E1 當且僅當當且僅當 (f(vi),f(vj) E2 （ E1 當且僅當當且僅當 E2 )并且并且, (vi,vj)（）與）與 (f(vi),f(vj)（）的重數(shù)相）的重數(shù)相同，則稱同，則稱G1與與G2是是同構同構的，記作的，記作G1 G2. 例例 12圖同構的實例圖同構的實例 (1) (2) (3) (4) (1)與與(2), (3)與與(4), (5)與與(6)均不同構均不同構. (5) (6) 說明說明: 1. 圖的同構關系具有自反性、對稱性和

11、傳遞性圖的同構關系具有自反性、對稱性和傳遞性. 2. 判斷兩個圖同構是個難題判斷兩個圖同構是個難題圖同構的實例圖同構的實例所有所有4階階3條邊非同構的簡單無向圖條邊非同構的簡單無向圖13所有所有3階階2條邊非同構的簡單有向圖條邊非同構的簡單有向圖補圖補圖與自補圖與自補圖定義定義9.6 設設G=為為n階無向簡單圖，令階無向簡單圖，令 =(u,v) | u V v V u v (u,v) E,稱稱 =為為G的的補圖補圖 若若G 則稱則稱G是是自補圖自補圖 EEGG例例 (b)與與(c)互為補圖，互為補圖，(a)是自補圖是自補圖15完全圖與競賽圖完全圖與競賽圖定義定義9.7 (1) n (n 1)

12、階階無向完全圖無向完全圖每個頂點與其余頂點均相鄰的每個頂點與其余頂點均相鄰的無向簡單圖，記作無向簡單圖，記作 Kn.簡單性質：簡單性質：m=n(n-1)/2, = =n-1(2) n (n 1)階階有向完全圖有向完全圖每對頂點之間均有兩條方向相每對頂點之間均有兩條方向相反的有向邊的有向簡單圖反的有向邊的有向簡單圖.簡單性質：簡單性質： m=n(n-1), = =2(n-1) += += = =n-1(3) n (n 1) 階階競賽圖競賽圖基圖為基圖為Kn的有向簡單圖的有向簡單圖.簡單性質：簡單性質： m=n(n-1)/2, = =n-1 正則圖正則圖 K5 3階有向完全圖階有向完全圖 4階競賽

13、圖階競賽圖定義定義9.8 k-正則圖正則圖 = =k 的無向簡單圖的無向簡單圖簡單性質：簡單性質：m=kn/2, 當當k是奇數(shù)時是奇數(shù)時, n必為偶數(shù)必為偶數(shù).例例 Kn是是 (n 1)-正則圖正則圖 彼得松圖彼得松圖是是3-正則圖正則圖子圖子圖定義定義9.9 設兩個圖設兩個圖G=, G =（同為無向圖或（同為無向圖或同為有向圖）同為有向圖）, 若若V V且且EE，則稱，則稱G 是是G的的子圖子圖，G為為G 母圖母圖，記作，記作G G. 又若又若V V或或E E，則稱，則稱G 為為G的的真真子圖子圖. 若若G G且且V =V，則稱，則稱G 為為G的的生成子圖生成子圖 設設V1 V且且V1, 稱

14、以稱以V1為頂點集為頂點集, 以以G中兩個端點都在中兩個端點都在V1中的邊組成邊集的圖為中的邊組成邊集的圖為G中中V1的的導出子圖導出子圖, 記作記作GV1. 設設E1 E且且E1, 稱以稱以E1為邊集為邊集, 以以E1中邊關聯(lián)的頂點為頂點中邊關聯(lián)的頂點為頂點集的圖為集的圖為G中中E1的的導出子圖導出子圖, 記作記作GE1例例 G Ga,b,c Ge1,e318定義定義9.10 設設G=為無向圖為無向圖 (1) 設設e E，用，用G e表示從表示從G中去掉邊中去掉邊e，稱為，稱為刪除邊刪除邊e又又設設E E，用，用 G E 表示從表示從G中刪除中刪除E 中的所有邊，稱為中的所有邊，稱為刪除刪除

15、E (2) 設設v V，用，用G v表示從表示從G中去掉中去掉v及所關聯(lián)的所有邊，稱及所關聯(lián)的所有邊，稱為為刪除頂點刪除頂點v又設又設V V，用，用G V 表示從表示從G中刪除中刪除V 中所有中所有的頂點，稱為的頂點，稱為刪除刪除V (3) 設設e=(u,v) E，用，用Ge表示從表示從G中刪除中刪除e后，將后，將e的兩個的兩個端點端點u,v用一個新的頂點用一個新的頂點w（可以用（可以用u或或v充當充當w）代替，并使）代替，并使w關聯(lián)除關聯(lián)除e以外以外u,v關聯(lián)的所有邊，稱為關聯(lián)的所有邊，稱為收縮邊收縮邊e (4) 設設u,v V（u,v可能相鄰，也可能不相鄰），用可能相鄰，也可能不相鄰），用

16、G (u,v)（或（或G+(u,v)）表示在）表示在u,v之間加一條邊之間加一條邊(u,v)，稱為，稱為加新邊加新邊 在收縮邊和加新邊過程中可能產生環(huán)和平行邊在收縮邊和加新邊過程中可能產生環(huán)和平行邊 刪除刪除, 收縮與加新邊收縮與加新邊19實例實例v1v2v3v4v5e1e2e3e4e5e6e7Gv1v2v3v4v5e1e2e3e4e6e7G-e5v1v2v3v4v5e2e3e5e6e7G-e1,e4v1v2v3v4e3e4e5e6e7G-v5v1v2v3e4e5e7G-v4,v5v1v3v4v5e1e2e3e4e6e7Ge5209.2 通路與回路通路與回路定義定義9.11 設圖設圖G= (無

17、向或有向的無向或有向的), G中頂點與邊的交中頂點與邊的交替序列替序列 = v0e1v1e2elvl，如果，如果vi 1, vi 是是 ei 的端點的端點(始點和終始點和終點點), 1 i l, 則稱則稱 為為v0到到vl的的通路通路. v0,vl分別稱作分別稱作 的的始點始點和和終終點點. 中的邊數(shù)中的邊數(shù)l稱作它的稱作它的長度長度. 又又若若 v0=vl, 則稱則稱 為為回路回路. 若若所有的邊各異所有的邊各異, 則稱則稱 為為簡單通路簡單通路. 又若又若v0=vl, 則稱則稱 為為簡單回簡單回路路. 若若 中所有頂點各異中所有頂點各異(除除v0和和vl可能相同外可能相同外)且所有邊也各且

18、所有邊也各異異, 則稱則稱 為為初級通路初級通路或或路徑路徑. 若又有若又有v0=vl, 則稱則稱 為為初級回初級回路路或或圈圈. 長度為奇數(shù)的圈稱為長度為奇數(shù)的圈稱為奇圈奇圈, 長度為偶數(shù)的圈稱為長度為偶數(shù)的圈稱為偶圈偶圈. 若若 中有邊重復出現(xiàn)中有邊重復出現(xiàn), 則則 稱為稱為復雜通路復雜通路. 若又有若又有v0=vl, 則稱則稱 為為復雜回路復雜回路.21通路與回路通路與回路定理定理9.4 在在n 階圖階圖G中，若從頂點中，若從頂點u 到到v（u v）存在通路，則）存在通路，則從從u 到到 v 存在長度小于或等于存在長度小于或等于n 1 的通路的通路.推論推論 在在 n 階圖階圖G中，若從

19、頂點中，若從頂點u 到到 v（u v）存在通路，則）存在通路，則從從u 到到v 存在長度小于或等于存在長度小于或等于n 1的初級通路（路徑）的初級通路（路徑）.定理定理9.5 在在n 階圖階圖G中，若存在中，若存在 v 到自身的回路，則一定存在到自身的回路，則一定存在v 到自身長度小于或等于到自身長度小于或等于 n 的回路的回路.推論推論 在在n 階圖階圖G中，若存在中，若存在 v 到自身的簡單回路，則一定存到自身的簡單回路，則一定存在在v 到自身的長度小于或等于到自身的長度小于或等于n 的初級回路的初級回路.22同構意義下和定義意義下的圈同構意義下和定義意義下的圈例例2 無向完全圖無向完全圖

20、Kn（n 3）中有幾種非同構的圈？）中有幾種非同構的圈？ 解解 長度相同的圈都是同構的長度相同的圈都是同構的. 易知易知Kn(n 3)中含長度中含長度3,4,n的圈，共有的圈，共有n 2種非同構的圈種非同構的圈長度相同的圈都是同構的長度相同的圈都是同構的, 因此在因此在同構意義下同構意義下給定長度的圈給定長度的圈只有一個只有一個. 在標定圖中在標定圖中, 圈表示成頂點和邊的標記序列圈表示成頂點和邊的標記序列. 如果如果只要兩個圈的標記序列不同只要兩個圈的標記序列不同, 稱這兩個圈在稱這兩個圈在定義意義下定義意義下不同不同.例例3 無向完全圖無向完全圖K3的頂點依次標定為的頂點依次標定為a,b,

21、c在定義意義下在定義意義下K3中有多少個不同的長度為中有多少個不同的長度為3的圈？的圈？解解 在定義意義下在定義意義下, 不同起點不同起點(終點終點)的圈是不同的的圈是不同的, 頂點間排頂點間排列順序不同的圈也是不同的列順序不同的圈也是不同的, 因而因而K3中有中有3!=6個不同的長為個不同的長為3的圈：的圈：abca，acba，bacb，bcab，cabc，cbac23帶權圖與最短路徑帶權圖與最短路徑定義定義9.12 設圖設圖G= (無向圖或有向圖無向圖或有向圖), 對對G的每一條邊的每一條邊e,給定一個數(shù)給定一個數(shù)W(e),稱作邊稱作邊e的的權權. 把這樣的圖稱為把這樣的圖稱為帶權圖帶權圖

22、, 記作記作G=. 當當e=(u,v)()時時, 把把W(e)記作記作W(u,v). 設設P是是G中的一條通路中的一條通路, P中所有邊的權之和稱為中所有邊的權之和稱為P的的長度長度,記作記作W(P). 類似地類似地, 可定義回路可定義回路C的長度的長度W(C). 設帶權圖設帶權圖G= (無向圖或有向圖無向圖或有向圖), 其中每一條邊其中每一條邊e的的權權W(e)為非負實數(shù)為非負實數(shù). u,v V, 當當u和和v連通連通(u可達可達v)時時, 稱從稱從u到到v長度最短的路徑為從長度最短的路徑為從u到到v的的最短路徑最短路徑, 稱其長度為從稱其長度為從u到到v的的距離距離, 記作記作d(u,v)

23、. 約定約定: d(u,u)=0; 當當u和和v不連通不連通(u不可達不可達v)時時, d(u,v)=+ .24最短路問題最短路問題最短路問題最短路問題: 給定帶權圖給定帶權圖G=及頂點及頂點u和和v, 其中每一條其中每一條邊邊e的權的權W(e)為非負實數(shù)為非負實數(shù), 求從求從u到到v的最短路徑的最短路徑.Dijkstra標號法標號法 (求從求從s到其余各點的最短路徑和距離到其余各點的最短路徑和距離)1. 令令l(s)(s,0), l(v)(s,+ ) (v V-s), i1, l(s)是永久標號是永久標號, 其余標號均為臨時標號其余標號均為臨時標號, us2. for 與與u關聯(lián)的臨時標號的

24、頂點關聯(lián)的臨時標號的頂點v 3. if l2(u)+W(u,v) l2(v) then 令令l(v)(u,l2(u)+W(u,v)4. 計算計算l2(t)=min l2(v) | v V且有臨時標號且有臨時標號, l(t)改為永久標號改為永久標號5. if in then 令令ut, ii+1, 轉轉2對每一個對每一個u, d(s,u)= l2(u),根據(jù)根據(jù)l1(v)回溯找到回溯找到s到到u的最短路徑的最短路徑.25實例實例例例9.5 一個總部和一個總部和6個工地個工地, 求從總部到各工地的最短路徑求從總部到各工地的最短路徑解解 12345671510364451726總部總部1234567

25、1510364451726 (0,S)(+ ,S)(+ ,S)(+ ,S)(+ ,S)(+ ,S)(+ ,S)26實例實例12345671510364451726 (0,S)(15,1)(10,1)(+ ,S)(+ ,S)(+ ,S)(+ ,S)u=112345671510364451726 (0,S)(13,3)(10,1)(+ ,S)(14,3)(+ ,S)(+ ,S)u=327實例實例12345671510364451726 (0,S)(13,3)(10,1)(19,2)(14,3)(30,2)(+ ,S)u=212345671510364451726 (0,S)(13,3)(10,1)

26、(18,5)(14,3)(30,2)(16,5)u=528實例實例12345671510364451726 (0,S)(13,3)(10,1)(18,5)(14,3)(22,6)(16,5)u=612345671510364451726 (0,S)(13,3)(10,1)(18,5)(14,3)(22,6)(16,5)u=429實例實例v1v3v2, d(v1,v2)=13 v1v3, d(v1,v3)=10v1v3v5v4, d(v1,v4)=18 v1v3v5, d(v1,v5)=14v1v3v5v6, d(v1,v6)=16 v1v3v5v6v7, d(v1,v7)=2212345671

27、510364451726 (0,S)(13,3)(10,1)(18,5)(14,3)(22,6)(16,5)u=7309.3 圖的連通性圖的連通性定義定義9.13 設無向圖設無向圖G=，若，若u,v V之間存在通路，則稱之間存在通路，則稱u,v是是連通的連通的，記作，記作uv. 規(guī)定規(guī)定: v V vv 若無向圖若無向圖G是平凡圖或是平凡圖或G中任何兩個頂點都是連通的，則中任何兩個頂點都是連通的，則稱稱G為為連通圖連通圖，否則稱，否則稱G為為非連通圖非連通圖是是V上的等價關系上的等價關系, 具有自反性、對稱性和傳遞性具有自反性、對稱性和傳遞性定義定義9.14 設無向圖設無向圖G=，Vi是是V關

28、于頂點之間連通關關于頂點之間連通關系的一個等價類，稱導出子圖系的一個等價類，稱導出子圖GVi為為G的一個的一個連通分支連通分支. G的的連通分支數(shù)連通分支數(shù)記為記為p(G)31點割集與邊割集點割集與邊割集定義定義9.15 設無向圖設無向圖G=. 若若V V使得使得p(G V )p(G), 且且對于任意的對于任意的V V , 均有均有p(G V )=p(G), 則稱則稱V 是是G的的點割集點割集.若若V =v, 則稱則稱v為為割點割點定義定義9.16 設無向圖設無向圖G=, 若若E E使得使得p(G E )p(G), 且且對于任意的對于任意的E E , 均有均有p(G E )=p(G), 則稱則

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

30、連通圖的連通度為非連通圖的連通度為0.定義定義9.18 設設G為連通圖為連通圖, 稱稱 (G) = min|E | E 為邊割集為邊割集為為G的的邊連通度邊連通度. 若若 (G) r，則稱，則稱G是是 r 邊邊-連通圖連通圖. 規(guī)定非連通圖的邊連通度為規(guī)定非連通圖的邊連通度為0.v1v2v3v4v5e1e2e3e4e5e6e7例例 =2, 2-連通圖連通圖, 也是也是1-連通連通. =2, 2邊邊-連通圖連通圖, 也是也是1邊邊-連通連通.33幾點說明幾點說明l (Kn)= (Kn)=n 1l G非連通，則非連通，則 = =0l 若若G中有割點，則中有割點，則 =1，若有橋，則，若有橋，則 =

31、1l 若若 (G)=k, 則則G是是1-連通圖，連通圖，2-連通圖，連通圖，k-連通圖，但連通圖，但不是不是(k+s)-連通圖，連通圖，s 1l 若若 (G)=r, 則則G是是1邊邊-連通圖，連通圖，2邊邊-連通圖，連通圖，r邊邊-連通連通圖，但不是圖，但不是(r+s)-邊連通圖，邊連通圖，s 1定理定理9.6 (G) (G) (G)34有向圖的連通性及分類有向圖的連通性及分類定定義義9.19 設設D=為一個有向圖為一個有向圖, vi,vj V, 若從若從vi到到vj存在存在通路通路, 則稱則稱vi可達可達vj, 記作記作vivj . 規(guī)定規(guī)定vi vi. 若若vivj且且vjvi，則稱則稱v

32、i與與vj是是相互可達相互可達的的, 記作記作vivj. 規(guī)定規(guī)定vivi性質性質: 具有自反性具有自反性(vi vi)、傳遞性、傳遞性 具有自反性、對稱性、傳遞性具有自反性、對稱性、傳遞性 定義定義9.20 若有向圖若有向圖D=V,E)的基圖是連通圖的基圖是連通圖, 則稱則稱D是是弱連通弱連通圖圖, 簡稱為簡稱為連通圖連通圖. 若若 vi,vj V, vivj與與vjvi至少有一個成立，至少有一個成立，則稱則稱 D是是單向連通圖單向連通圖. 若若 vi,vj V, 均有均有vivj, 則稱則稱D是是強連強連通圖通圖35有向圖的連通性有向圖的連通性 強連通強連通 單向連通單向連通 弱連通弱連通

33、定理定理9.7 有向圖有向圖D=是強連通圖當且僅當是強連通圖當且僅當D中存在經過中存在經過每個頂點至少一次的回路每個頂點至少一次的回路證證 充分性顯然充分性顯然. 證必要性證必要性. 設設V=v1,v2,vn, i為為vi到到vi+1的通的通路路( i=1,2,n 1), n為為vn到到v1的通路的通路. 依次連接依次連接 1, 2, , n 1, n所得到的回路經過所得到的回路經過D中每個頂點至少一次中每個頂點至少一次定理定理9.8 有向圖有向圖D是單向連通圖當且僅當是單向連通圖當且僅當D中存在經過每個中存在經過每個頂點至少一次的通路頂點至少一次的通路例例擴大路徑法擴大路徑法設設G=為無向圖

34、為無向圖, 為為G中一條路徑中一條路徑. 若此路徑的兩個端若此路徑的兩個端點都不與通路外的頂點相鄰點都不與通路外的頂點相鄰, 則稱則稱 是是極大路徑極大路徑.任取一條邊任取一條邊, 如果它有一個端點與其他的頂點相鄰如果它有一個端點與其他的頂點相鄰, 就將這條就將這條邊延伸到這個頂點邊延伸到這個頂點. 繼續(xù)這一過程繼續(xù)這一過程, 直至得到一條極大路徑為直至得到一條極大路徑為止止. 稱此種方法為稱此種方法為“擴大路徑法擴大路徑法”. 用擴大路徑法總可以得到用擴大路徑法總可以得到一條極大路徑一條極大路徑. 在有向圖中可類似討論在有向圖中可類似討論.例例 由一條路徑擴大出的極大路徑不惟一，極大路徑不一

35、定是由一條路徑擴大出的極大路徑不惟一，極大路徑不一定是最長的路徑最長的路徑37擴大路徑法的應用擴大路徑法的應用例例4 設設 G 為為 n（n 3）階無向簡單圖，）階無向簡單圖， 2，證明，證明G 中存在中存在長度長度 +1 的圈的圈.證證 設設 = v0v1vl 是一條極大路徑是一條極大路徑, 則則 l . 因為因為v0 不與不與 外外頂點相鄰頂點相鄰, 又又 d(v0) , 因而在因而在 上除上除 v1外外, 至少還存在至少還存在 1個個頂點與頂點與 v0 相鄰相鄰. 設設 vx 是離是離 v0 最遠的頂點最遠的頂點, 于是于是v0v1vxv0 為為 G 中長度中長度 +1 的圈的圈. 38

36、9.4 圖的矩陣表示圖的矩陣表示無向圖的關聯(lián)矩陣無向圖的關聯(lián)矩陣定義定義9.21 無向圖無向圖G=，|V|=n，|E|=m，令，令 mij為為 vi 與與 ej的關聯(lián)次數(shù)，稱的關聯(lián)次數(shù)，稱(mij)n m為為G 的的關聯(lián)矩陣關聯(lián)矩陣，記為，記為M(G). 10000110000011001112)(GM例例39無向圖關聯(lián)矩陣的性質無向圖關聯(lián)矩陣的性質是孤立點是孤立點平行邊的列相同平行邊的列相同imjijjiijimjijniijvmmmnivdmmjm 0)5()4(2)3(,.,2 , 1,)()2(,.,2 , 1,2)1(1,1140 的的終終點點為為，不不關關聯(lián)聯(lián)與與，的的始始點點為為

37、jijijiijevevevm10,1定義定義9.22 設有向圖有向圖D=中無環(huán)，令中無環(huán)，令則稱則稱 (mij)n m為為D的的關聯(lián)矩陣關聯(lián)矩陣，記為，記為M(D). 例例有向圖(無環(huán))的關聯(lián)矩陣 11100110000011100011)(DM41(1) 每列恰好有一個每列恰好有一個+1和一個和一個-1(2) -1的個數(shù)等于的個數(shù)等于+1的個數(shù)，都等于邊數(shù)的個數(shù)，都等于邊數(shù)m.(3)第第i行中，行中，+1的個數(shù)等于的個數(shù)等于d+(vi)，-1的個數(shù)等于的個數(shù)等于d (vi)(4) 平行邊對應的列相同平行邊對應的列相同有向圖關聯(lián)矩陣的性質42有向圖的鄰接矩陣有向圖的鄰接矩陣定義定義9.23

38、設有向圖設有向圖D=, V=v1, v2, , vn, 令令 為頂點為頂點 vi 鄰接到頂點鄰接到頂點 vj 邊的條數(shù)，稱邊的條數(shù)，稱( )為為D的的鄰接矩陣鄰接矩陣，記作，記作A(D)，或簡記為，或簡記為A. )1(ija)1(ija 1100100001000120A例例43有向圖鄰接矩陣的性質有向圖鄰接矩陣的性質的回路數(shù)的回路數(shù)中長度為中長度為的通路數(shù)的通路數(shù)中長度為中長度為1)4(1)3(,.,2 , 1),()2(,.,2 , 1),()1(1)1(,)1(1)1(1)1(DaDmanjvdanivdaniiijiijjniijinjij 定理定理9.9 設設 A為有向圖為有向圖 D

39、 的鄰接矩陣的鄰接矩陣, 頂點集頂點集V=v1,v2, vn，則則 A 的的 l 次冪次冪 Al（l 1）中元素）中元素推論推論 設設Bl=A+A2+Al (l 1), 則則 ninjlijb11)( niliib1)(為長度小于或等于為長度小于或等于 l 的回路數(shù)的回路數(shù).為長度小于或等于為長度小于或等于 l 的通路數(shù)的通路數(shù), 鄰接矩陣的應用鄰接矩陣的應用為長度為 l 的通路總數(shù)，)(lija)(liia ninjlija11)( niliia1)(為vi 到vj長度為 l 的通路數(shù)，為vi到自身長度為 l 的回路數(shù)，為長度為為長度為 l 的回路總數(shù)的回路總數(shù). 45例例5 有向圖有向圖D

40、如圖所示，求如圖所示，求 A, A2, A3, A4，并回答諸問題：，并回答諸問題：(1) D 中長度為中長度為1, 2, 3, 4的通路各有多少條？其中回路分別為多的通路各有多少條？其中回路分別為多少條？少條？(2) D 中長度小于或等于中長度小于或等于4的通路為多少條？其中有多少條回路？的通路為多少條？其中有多少條回路？實例實例 0101100101020001A46 100401041005000101031003010400011002010210030001432AAA(1) D中長度為中長度為1的通路為的通路為8條，其中有條，其中有1條是回路條是回路. D中長度為中長度為2的通路為

41、的通路為11條，其中有條，其中有3條是回路條是回路. D中長度為中長度為3的通路為的通路為14條，其中有條，其中有1條是回路條是回路. D中長度為中長度為4的通路為的通路為17條，其中有條，其中有3條是回路條是回路. (2) D中長度小于等于中長度小于等于4的通路為的通路為50條，其中有條，其中有8條是回路條是回路.實例求解實例求解47 否否則則可可達達, 1, 0jiijvvp定義定義9.24 設設D=為有向圖為有向圖. V=v1, v2, , vn, 令令 有向圖的可達矩陣有向圖的可達矩陣稱稱 (pij)n n 為為D的的可達矩陣可達矩陣，記作，記作P(D)，簡記為，簡記為P. P(D)的

42、主對角線上的元素全為的主對角線上的元素全為1. D 強連通當且僅當強連通當且僅當 P(D)為全為全1矩陣矩陣. 1101110111110001P例例48第九章第九章 習題課習題課主要內容主要內容l 無向圖和有向圖及其有關的概念無向圖和有向圖及其有關的概念; 握手定理及其推論；圖握手定理及其推論；圖的同構的同構l 通路與回路通路與回路l 無向圖的連通性與連通度無向圖的連通性與連通度l 有向圖的連通性及其分類有向圖的連通性及其分類l 圖的矩陣表示圖的矩陣表示49基本要求基本要求l 深刻理解圖及其有關的概念深刻理解圖及其有關的概念l 深刻理解和靈活地應用握手定理及推論深刻理解和靈活地應用握手定理及推論l 記住通路與回路的定義、分類及表示法記住通路與回路的定義、分類及表示法l 深刻理解與無向圖連通性、連通度有關的諸多概念深刻理解與無向圖連通性、連通度有關的諸多概念l 會判別有向圖連通性的類型會判別有向圖連通性的類型l 熟練掌握用鄰接矩陣及其冪求有向圖中通路與回路數(shù)的方熟練掌握用鄰接矩陣及其冪求有向圖中通路與回路數(shù)的方法，會求可達矩陣法，會求可達矩陣 5019階無向圖階無向圖G中，每個頂點的度數(shù)不是中，每個頂點的度數(shù)不是5就是就是6. 證明證明G中至少有中至少有5個個6度頂點或至少有度頂點或至少有6個個5