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

第7-2講圖的連通性1.路2.連通的概念3.

刪除結(jié)點(diǎn)和邊與圖的連通性4.有向圖的可達(dá)性5.有向圖的連通性6.課堂練習(xí)7.第7-2講作業(yè)11、路（1）圖論中的一個(gè)典型問(wèn)題是從給定的結(jié)點(diǎn)出發(fā),沿著邊連續(xù)移動(dòng),到達(dá)另一指定結(jié)點(diǎn)的問(wèn)題。所經(jīng)過(guò)的點(diǎn)邊序列就形成了路的概念。定義1

給定圖G=<V,E>,設(shè)v0,v1,v2,…vnV，e1,e2,…,emE，其中ei是關(guān)聯(lián)結(jié)點(diǎn)ei-1、ei的邊，點(diǎn)邊交替序列v0

e1v1e2v2…envn稱為v0到vn的路。v0和vn分別稱為該路的起點(diǎn)和終點(diǎn)。如果v0=vn，稱該路回路。若路中各邊均不相同，則稱為跡；若路中各結(jié)點(diǎn)均不相同，則稱為通路；若閉合通路中各結(jié)點(diǎn)均不相同，則稱為圈。例如右圖中：v1

e1v2e5v4e8v5e7v3是跡，也是通路；v2

e3v3e4v2e6v5e8v4e5v2是回路；v2

e3v3e7v5e6v2是圈。21、路（2）定理1

在具有n個(gè)結(jié)點(diǎn)的圖中，如果從結(jié)點(diǎn)vj到vk存在一條路，則從結(jié)點(diǎn)vj到vk必存在一條不多于n-1邊的路。證明：設(shè)從結(jié)點(diǎn)vj到vk存在一條路，該路的結(jié)點(diǎn)序列為vj…vi…vk。如果該路有m條邊，則該路的結(jié)點(diǎn)序列中有m+1個(gè)結(jié)點(diǎn)。若m>n-1，則必存在結(jié)點(diǎn)vs，它在該路中不止出現(xiàn)一次，可設(shè)該路的結(jié)點(diǎn)序列為vj…vs…vs…vk。去掉vs到vs之間這段路，則vj…vs…vk仍然是vj到vk的路，只不過(guò)路中邊數(shù)已減少。如果所得的這條路中的邊仍然大于n-1，重復(fù)上述步驟，可得一條vj到vk的路且路中邊數(shù)進(jìn)一步減少。如此繼續(xù)下去，最終可得一條vj到vk且路中邊數(shù)不多于n-1條邊的路。例如左圖有5個(gè)結(jié)點(diǎn)，v1e1v2e3v3e4v2e6v5e8v4是圖中從v1到v4路，它有5條邊。去掉v2到

v2之間的路e3v3e4v2，所得的路v1e1v2e6v5e8v4仍然是從v1到v4路，其邊數(shù)小于5-1。32、連通的概念定義2

在無(wú)向圖G中，如果從結(jié)點(diǎn)u到v存在一條路，則稱結(jié)點(diǎn)u到v是連通的。

對(duì)無(wú)向圖G=<V,E>而言，結(jié)點(diǎn)集合V上的連通關(guān)系是等價(jià)關(guān)系。該連通關(guān)系將結(jié)點(diǎn)集合作出一個(gè)劃分，每個(gè)劃分塊連同它們所關(guān)聯(lián)的邊稱為圖G的一個(gè)連通分支。

定義3若圖G中只有一個(gè)連通分支，則稱圖G是連通的。

右圖所示圖G有兩個(gè)連通分支G1和G243、刪除結(jié)點(diǎn)和邊與圖的連通性(1)定義4

設(shè)無(wú)向圖G=<V,E>中，若有結(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)。結(jié)點(diǎn)和邊的刪除在圖中刪除結(jié)點(diǎn)v,就是將結(jié)點(diǎn)v及v所關(guān)聯(lián)的邊統(tǒng)統(tǒng)刪除。在圖中刪除某邊,則只須刪除該邊，而保留邊所關(guān)聯(lián)的結(jié)點(diǎn)。例：刪除割點(diǎn)。53、刪除結(jié)點(diǎn)和邊與圖的連通性（2）由定義5可知，連通度是為了產(chǎn)生一個(gè)不連通圖所要?jiǎng)h除結(jié)點(diǎn)的最少數(shù)目。那么，非連通圖的連通度為0；存在割點(diǎn)的連通圖的連通度為1；完全圖Kn刪除m(m<n-1)個(gè)結(jié)點(diǎn)后仍是連通的，刪除n-1個(gè)結(jié)點(diǎn)后成為僅有一個(gè)孤立結(jié)點(diǎn)的平凡圖，故規(guī)定K(Kn)=n-1。定義5非完全圖G的點(diǎn)連通度(簡(jiǎn)稱連通度)定義為：K(G)=min{|Vi||Vi是點(diǎn)割集}63、刪除結(jié)點(diǎn)和邊與圖的連通性(3)定義6

設(shè)無(wú)向圖G=<V,E>為連通圖，若有邊集E1E,使圖G刪除了E1中的所有邊后所得的子圖是不連通的,而刪除了E1的任一真子集后所得的子圖仍是連通的,則稱E1是圖G的邊割集。如果某條邊構(gòu)成一個(gè)邊割集,則稱該邊為割邊(亦稱為橋)。例：右圖中，E1={e1,e2}E2={e1,e3,e5,e7}是邊割集；E3={e8}是橋。74、有向圖的可達(dá)性

無(wú)向圖的連通概念不能直接推廣到有向圖。

在有向圖G=<V,E>中，如果從結(jié)點(diǎn)u和v有一條路，則稱從u可達(dá)v。如果u可達(dá)v，則u、v之間的最短路（短程線）的長(zhǎng)度稱為結(jié)點(diǎn)u、v之間的距離，記作d<u,v>。

d<u,v>0

d<u,u>=0

d<u,v>+d<v,w>d<u,w>如果從u到v不可達(dá)，則記d<u,v>=。

距離的概念也適用于無(wú)向圖

注意，因?yàn)槭怯邢驁D，d<u,v>一般不等于d<v,u>。將D=max{d<u,v>|u,vG}稱為圖G的直徑。可達(dá)性是有向圖結(jié)點(diǎn)集上的二元關(guān)系，它是自反的和傳遞的，但一般不是對(duì)稱的。所以可達(dá)不是等價(jià)關(guān)系。85、有向圖的連通性（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是弱連通的。例：分析下列各有向圖的連通性。解：圖G1是強(qiáng)連通的；G2是單側(cè)連通的；G3是弱連通的。95、有向圖的連通性（2）定理4一個(gè)有向圖是強(qiáng)連通的，當(dāng)且僅當(dāng)G中有一個(gè)回路，它至少包含每個(gè)結(jié)點(diǎn)一次。證：充分性。如果圖G中有一個(gè)回路，它至少包含每個(gè)結(jié)點(diǎn)一次，則G中任何兩個(gè)結(jié)點(diǎn)相互可達(dá)，故圖G是強(qiáng)連通的。

必要性。如果有向圖G是強(qiáng)連通的，則G中任何兩個(gè)結(jié)點(diǎn)相互可達(dá)，故可從圖中任一結(jié)點(diǎn)v出發(fā)，經(jīng)由圖中所有的結(jié)點(diǎn)，再返回v，從而形成一個(gè)回路。105、有向圖的連通性（3）定義9在簡(jiǎn)單有向圖G中，具有強(qiáng)連通性的最大子圖稱為強(qiáng)分圖；具有單側(cè)連通性的最大子圖稱為單側(cè)分圖；具有弱連通性的最大子圖稱為弱分圖。例如，下圖右側(cè)圖中，包含結(jié)點(diǎn){v1,v2,v3,v4}的子圖是強(qiáng)分圖；僅包含一個(gè)孤立結(jié)點(diǎn)v5的子圖也是強(qiáng)分圖，但包含結(jié)點(diǎn){v1,v2,v4}的子圖不是強(qiáng)分圖115、有向圖的連通性（4）定理5有向圖G=<V,E>的每個(gè)結(jié)點(diǎn)位于且只位于一個(gè)強(qiáng)分圖中。證：設(shè)任意vV,令S是圖G中所有與v相互可達(dá)的結(jié)點(diǎn)集合，當(dāng)然vS。則S是G的一個(gè)強(qiáng)分圖。因此，G的每個(gè)結(jié)點(diǎn)必位于一個(gè)強(qiáng)分圖中。假設(shè)v位于兩個(gè)強(qiáng)分圖S1和S2中，因S1中每個(gè)結(jié)點(diǎn)與v相互可達(dá),而v與S2中每個(gè)結(jié)點(diǎn)也相互可達(dá),故S1和S2中任何一對(duì)結(jié)點(diǎn)通過(guò)v都是相互可達(dá)的。這與S1和S2為強(qiáng)分圖矛盾。故G的每個(gè)結(jié)點(diǎn)位于且只位于一個(gè)強(qiáng)分圖中。126、課堂練習(xí)練習(xí)1若無(wú)向圖G中恰有兩個(gè)奇數(shù)度結(jié)點(diǎn)u和v,則u、v之間必有一條路。解：由7-1定理2，任何圖中奇數(shù)度結(jié)點(diǎn)為偶數(shù)個(gè)。所以u(píng)、v必位于G的同一連通分支中。從u出發(fā)構(gòu)造一條跡(邊不重復(fù)的路)，方法是從u出發(fā)經(jīng)關(guān)聯(lián)u的一條邊e1到達(dá)u1，若deg(u1)為偶數(shù)，則可經(jīng)關(guān)聯(lián)u1的一條邊e2到達(dá)u2。如此繼續(xù)，每邊只取一次，直到一個(gè)