離散數(shù)學(xué)第七章第二節(jié)

1、1第7-2講 圖的連通性1. 路2. 連通的概念3. 刪除結(jié)點和邊與圖的連通性4. 有向圖的可達性5. 有向圖的連通性6. 課堂練習(xí)7. 第7-2講 作業(yè)21、路（1） 圖論中的一個典型問題是從給定的結(jié)點出發(fā)圖論中的一個典型問題是從給定的結(jié)點出發(fā),沿著邊連續(xù)移沿著邊連續(xù)移動動,到達另一指定結(jié)點的問題。所經(jīng)過的點邊序列就形成了路到達另一指定結(jié)點的問題。所經(jīng)過的點邊序列就形成了路的概念。的概念。定義1 給定圖給定圖G=,設(shè)設(shè)v0, v1, v2,vn V， e1, e2, , em E，其中其中ei是關(guān)聯(lián)結(jié)點是關(guān)聯(lián)結(jié)點ei-1、 ei的邊，的邊，點邊交替序列點邊交替序列v0 e1v1 e2 v2

2、envn稱為稱為v0到到vn的路的路。v0和和vn分別稱為該路的起點和終點。如分別稱為該路的起點和終點。如果果v0=vn，稱該路，稱該路回路回路。 若路中各邊均不相同，則稱為若路中各邊均不相同，則稱為跡跡；若路中各；若路中各結(jié)點結(jié)點均不相同，均不相同，則稱為則稱為通路通路；若閉合通路中各；若閉合通路中各結(jié)點結(jié)點均不相同，則稱為均不相同，則稱為圈圈。例如右圖中例如右圖中：v1 e1v2 e5 v4e8v5 e7v3是跡，也是通路；是跡，也是通路； v2 e3v3 e4v2e6v5 e8v4 e5v2是回路；是回路； v2 e3v3 e7v5e6v2 是圈。是圈。31、路（2）定理1 在具有在具有

3、n n個結(jié)點的圖中，如果從結(jié)點個結(jié)點的圖中，如果從結(jié)點v vj j到到v vk k存在一條路，存在一條路，則從結(jié)點則從結(jié)點v vj j到到v vk k必存在一條不多于必存在一條不多于n-1n-1邊的邊的路。路。證明：設(shè)設(shè)從結(jié)點從結(jié)點v vj j到到v vk k存在一條路，存在一條路，該路的結(jié)點序列為該路的結(jié)點序列為vj vi vk。如果。如果該路有該路有m條邊，則該路的結(jié)點序列中有條邊，則該路的結(jié)點序列中有m+1個結(jié)點。個結(jié)點。 若若mn-1，則必，則必存在存在結(jié)點結(jié)點vs，它在該路中不止出現(xiàn)一次，可設(shè)該路的結(jié)它在該路中不止出現(xiàn)一次，可設(shè)該路的結(jié)點序列為點序列為vj vs vs vk。去掉。去

4、掉vs 到到 vs 之間這段路，則之間這段路，則vj vs vk仍然仍然是是v vj j到到v vk k的路，只不過路中邊數(shù)已減少。的路，只不過路中邊數(shù)已減少。 如果所得的這條路中的邊如果所得的這條路中的邊仍然大于仍然大于n-1，重復(fù)上述步驟，可得一條，重復(fù)上述步驟，可得一條v vj j到到v vk k的路且路中邊數(shù)進一步減少。如此繼續(xù)下去，最終的路且路中邊數(shù)進一步減少。如此繼續(xù)下去，最終可得一條可得一條v vj j到到v vk k且路中且路中邊數(shù)不多于邊數(shù)不多于n-1條邊條邊的路。的路。例如左圖有例如左圖有5個結(jié)點，個結(jié)點，v1e1v2 e3v3e4v2 e6v5 e8v4是圖是圖中中從從v

5、1到到v4路，它有路，它有5條邊。去掉條邊。去掉v2到到 v2 之間的路之間的路e3v3e4 v2 ，所得的路，所得的路v1e1v2 e6v5 e8v4仍然是從仍然是從v1到到v4路，其邊數(shù)小于路，其邊數(shù)小于5-1。42、連通的概念定義2 在無向圖G中，如果從結(jié)點u到v存在一條路，則稱結(jié)點u到v是連通的。 對無向圖對無向圖G= 而言，結(jié)點集合而言，結(jié)點集合V上的連通關(guān)系是等價上的連通關(guān)系是等價關(guān)系。該連通關(guān)系將結(jié)點集合作出一個劃分，每個劃分塊連關(guān)系。該連通關(guān)系將結(jié)點集合作出一個劃分，每個劃分塊連同它們所關(guān)聯(lián)的邊稱為圖同它們所關(guān)聯(lián)的邊稱為圖G的一個的一個連通分支連通分支。 定義3 若圖圖G G中

6、只有一個連通分支，則稱中只有一個連通分支，則稱圖圖G G是連通的是連通的。 右圖所示圖右圖所示圖G有有兩個連通分支兩個連通分支G1和和G253、刪除結(jié)點和邊與圖的連通性(1)定義4 設(shè)無向圖G=中，若有結(jié)點集V1V,使圖G刪除了V1的所有結(jié)點后所得的子圖是不連通的,而刪除了V1的任一真子集后所得的子圖仍是連通的,則稱V1是圖G的點割集。如果某個結(jié)點構(gòu)成一個點割集,則稱該結(jié)點為割點。v 結(jié)點和邊的刪除結(jié)點和邊的刪除 在圖中在圖中刪除結(jié)點刪除結(jié)點v,就是將結(jié)點就是將結(jié)點v及及v所關(guān)聯(lián)的邊統(tǒng)統(tǒng)刪除。所關(guān)聯(lián)的邊統(tǒng)統(tǒng)刪除。 在圖中在圖中刪除某邊刪除某邊,則只須刪除該邊，而保留邊所關(guān)聯(lián)的結(jié)點。則只須刪除該

7、邊，而保留邊所關(guān)聯(lián)的結(jié)點。例：刪除割點。刪除割點。63、刪除結(jié)點和邊與圖的連通性（2） 由定義5可知，連通度是為了產(chǎn)生一個不連通圖所要刪除結(jié)點的最少數(shù)目。那么，非連通圖的連通度為0；存在割點的連通圖的連通度為1；完全圖Kn刪除m(mn-1)個結(jié)點后仍是連通的，刪除n-1個結(jié)點后成為僅有一個孤立結(jié)點的平凡圖，故規(guī)定K(Kn)=n-1。定義5 非完全圖G的點連通度點連通度( (簡稱連通度) )定義為： K(G)=min|Vi| Vi是點割集73、刪除結(jié)點和邊與圖的連通性(3)定義6 設(shè)無向圖G=為連通圖，若有邊集E1E,使圖G刪除了E1中的所有邊后所得的子圖是不連通的,而刪除了E1的任一真子集后所

8、得的子圖仍是連通的,則稱E1是圖G的邊割集。如果某條邊構(gòu)成一個邊割集,則稱該邊為割邊(亦稱為橋)。例：右圖中，右圖中，E E1 1=e=e1 1,e,e2 2 E E2 2=e=e1 1,e,e3 3,e,e5 5,e,e7 7 是邊割集；是邊割集；E E3 3=e=e8 8 是橋。是橋。84、有向圖的可達性n 無向無向圖的圖的連通連通概念不能直接推廣到有向圖。概念不能直接推廣到有向圖。n 在有在有向向圖圖G=G=中，如果從結(jié)點中，如果從結(jié)點u u和和v v有一條路，則稱從有一條路，則稱從u u可達可達v v。n 如果如果u u可達可達v v，則，則u u、v v之間的最短路（之間的最短路（短

9、程線短程線）的長度稱為）的長度稱為結(jié)點u u、v v之間的之間的距離距離，記作，記作dd。 dd 0 0 dd=0=0 dd+ +dd dd如果從如果從u u到到v v不可達，則記不可達，則記d=d= 。 距離的概念也適用于無距離的概念也適用于無向向圖圖n 注意，因為是有注意，因為是有向向圖，圖，dd一般不等于一般不等于dd。n 將將D=maxd|u,vD=maxd|u,v G G 稱為稱為圖圖G G的直徑的直徑。n 可達性是有可達性是有向向圖結(jié)點集上的二元關(guān)系，它是自反的和傳遞圖結(jié)點集上的二元關(guān)系，它是自反的和傳遞的，但一般不是對稱的。所以可達不是等價關(guān)系。的，但一般不是對稱的。所以可達不是

10、等價關(guān)系。95、有向圖的連通性（1）定義8 在簡單有向圖G中，任何一對結(jié)點間，如果至少從一個結(jié)點到另一個結(jié)點可達，則稱該圖是單側(cè)連通的。如果圖G中任何一對結(jié)點之間相互可達，則稱圖G是強連通的。如果在圖G中略去邊的方向視為無向圖是連通的，則稱圖G是弱連通的。例：分析下列各有向圖的連通性。例：分析下列各有向圖的連通性。解：解：圖圖G G1 1是是強連通的；強連通的； G G2 2是是單側(cè)連通的；單側(cè)連通的； G G3 3是是弱連通的。弱連通的。105、有向圖的連通性（2）定理4 一個有向圖是強連通的，當(dāng)且僅當(dāng)G中有一個回路，它至少包含每個結(jié)點一次。證：充分性。充分性。如果如果圖圖G G中有一個回路

11、，它至少包含每個結(jié)點中有一個回路，它至少包含每個結(jié)點一次，則一次，則G G中任何兩個結(jié)點相互可達，故圖中任何兩個結(jié)點相互可達，故圖G G是強連通的。是強連通的。 必要性。必要性。如果有如果有向圖向圖G G是強連通的，則是強連通的，則G G中任何兩個結(jié)點相中任何兩個結(jié)點相互可達，故可從圖中任一結(jié)點互可達，故可從圖中任一結(jié)點v v出發(fā)，經(jīng)由圖中所有的結(jié)點，出發(fā)，經(jīng)由圖中所有的結(jié)點，再返回再返回v v，從而形成一個回路。，從而形成一個回路。115、有向圖的連通性（3）定義9 在簡單有向圖G中，具有中，具有強連通性的最大子圖稱為強分圖；具有具有單側(cè)連通性的最大子圖稱為單側(cè)分圖；具有具有弱連通性的最大子

12、圖稱為弱分圖。例如，下圖右側(cè)圖中，包含結(jié)點例如，下圖右側(cè)圖中，包含結(jié)點vv1 1,v,v2 2,v,v3 3,v,v4 4 的子圖是強分的子圖是強分圖；僅包含一個孤立結(jié)點圖；僅包含一個孤立結(jié)點v v5 5的子圖也是強分圖，但包含結(jié)點的子圖也是強分圖，但包含結(jié)點vv1 1,v,v2 2,v,v4 4 的子圖不是強分圖的子圖不是強分圖125、有向圖的連通性（4）定理5 有向圖G=的每個結(jié)點位于且只位于一個強分圖中。證：設(shè)任意設(shè)任意v v V,令S是圖圖G G中所有與中所有與v v相互可達的結(jié)點集合，相互可達的結(jié)點集合，當(dāng)然當(dāng)然v S S。則則S是G G的一個強分圖。因此，的一個強分圖。因此，G G

13、的每個結(jié)點必位于的每個結(jié)點必位于一個強分圖中。一個強分圖中。 假設(shè)假設(shè)v v位于兩個強分圖位于兩個強分圖S S1 1和和S S2 2中，因中，因S S1 1中每個結(jié)點與中每個結(jié)點與v v相互可相互可達達, ,而而v v與與S S2 2中每個結(jié)點也相互可達中每個結(jié)點也相互可達, , 故故S S1 1和和S S2 2中任何一對結(jié)點中任何一對結(jié)點通過通過v v都是相互可達的。這與都是相互可達的。這與S S1 1和和S S2 2為強分圖矛盾。故為強分圖矛盾。故G G的的每每個結(jié)點位于且只位于一個強分圖中。個結(jié)點位于且只位于一個強分圖中。136 6、課堂練習(xí)課堂練習(xí)練習(xí)1 若無向圖若無向圖G G中恰有兩

14、個奇數(shù)度結(jié)點中恰有兩個奇數(shù)度結(jié)點u u和和v,v,則則u u、v v之間必有之間必有一條路。一條路。解：由由7-1定理定理2，任何圖中，任何圖中奇數(shù)度結(jié)點為奇數(shù)度結(jié)點為偶數(shù)個。所以偶數(shù)個。所以u、v必必位于位于G的同一連通分支中。的同一連通分支中。 從從u出發(fā)構(gòu)造一條跡出發(fā)構(gòu)造一條跡(邊不重復(fù)的路邊不重復(fù)的路)，方法是從，方法是從u出發(fā)經(jīng)關(guān)聯(lián)出發(fā)經(jīng)關(guān)聯(lián)u的一條邊的一條邊e1到達到達u1，若，若deg(u1)為偶數(shù)，則可經(jīng)關(guān)聯(lián)為偶數(shù)，則可經(jīng)關(guān)聯(lián)u1的一條的一條邊邊e2到達到達u2。如此繼續(xù)，每邊只取一次，直到一個。如此繼續(xù)，每邊只取一次，直到一個奇數(shù)度結(jié)點奇數(shù)度結(jié)點為止。如果該點是為止。如果該點是v v，則命題得證。如果該點仍是，則命題得證。如果該點仍是u u