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

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

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

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

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

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

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

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

8、得的子圖仍是連通的,則稱E1是圖G的邊割集。如果某條邊構(gòu)成一個(gè)邊割集,則稱該邊為割邊(亦稱為橋)。例：右圖中，右圖中，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、有向圖的可達(dá)性n 無(wú)向無(wú)向圖的圖的連通連通概念不能直接推廣到有向圖。概念不能直接推廣到有向圖。n 在有在有向向圖圖G=G=中，如果從結(jié)點(diǎn)中，如果從結(jié)點(diǎn)u u和和v v有一條路，則稱從有一條路，則稱從u u可達(dá)可達(dá)v v。n 如果如果u u可達(dá)可達(dá)v v，則，則u u、v v之間的最短路（之間的最短路（短

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

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

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

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

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

14、個(gè)奇數(shù)度結(jié)點(diǎn)中恰有兩個(gè)奇數(shù)度結(jié)點(diǎn)u u和和v,v,則則u u、v v之間必有之間必有一條路。一條路。解：由由7-1定理定理2，任何圖中，任何圖中奇數(shù)度結(jié)點(diǎn)為奇數(shù)度結(jié)點(diǎn)為偶數(shù)個(gè)。所以偶數(shù)個(gè)。所以u(píng)、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到達(dá)到達(dá)u1，若，若deg(u1)為偶數(shù)，則可經(jīng)關(guān)聯(lián)為偶數(shù)，則可經(jīng)關(guān)聯(lián)u1的一條的一條邊邊e2到達(dá)到達(dá)u2。如此繼續(xù)，每邊只取一次，直到一個(gè)。如此繼續(xù)，每邊只取一次，直到一個(gè)奇數(shù)度結(jié)點(diǎn)奇數(shù)度結(jié)點(diǎn)為止。如果該點(diǎn)是為止。如果該點(diǎn)是v v，則命題得證。如果該點(diǎn)仍是，則命題得證。如果該點(diǎn)仍是u u