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

刪除結點和邊與圖的連通性4.有向圖的可達性5.有向圖的連通性6.課堂練習7.第7-2講作業11、路（1）圖論中的一個典型問題是從給定的結點出發,沿著邊連續移動,到達另一指定結點的問題。所經過的點邊序列就形成了路的概念。定義1

給定圖G=<V,E>,設v0,v1,v2,…vnV，e1,e2,…,emE，其中ei是關聯結點ei-1、ei的邊，點邊交替序列v0

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

e1v2e5v4e8v5e7v3是跡，也是通路；v2

e3v3e4v2e6v5e8v4e5v2是回路；v2

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

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

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

在無向圖G中，如果從結點u到v存在一條路，則稱結點u到v是連通的。

對無向圖G=<V,E>而言，結點集合V上的連通關系是等價關系。該連通關系將結點集合作出一個劃分，每個劃分塊連同它們所關聯的邊稱為圖G的一個連通分支。

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

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

設無向圖G=<V,E>中，若有結點集V1V,使圖G刪除了V1的所有結點后所得的子圖是不連通的,而刪除了V1的任一真子集后所得的子圖仍是連通的,則稱V1是圖G的點割集。如果某個結點構成一個點割集,則稱該結點為割點。結點和邊的刪除在圖中刪除結點v,就是將結點v及v所關聯的邊統統刪除。在圖中刪除某邊,則只須刪除該邊，而保留邊所關聯的結點。例：刪除割點。53、刪除結點和邊與圖的連通性（2）由定義5可知，連通度是為了產生一個不連通圖所要刪除結點的最少數目。那么，非連通圖的連通度為0；存在割點的連通圖的連通度為1；完全圖Kn刪除m(m<n-1)個結點后仍是連通的，刪除n-1個結點后成為僅有一個孤立結點的平凡圖，故規定K(Kn)=n-1。定義5非完全圖G的點連通度(簡稱連通度)定義為：K(G)=min{|Vi||Vi是點割集}63、刪除結點和邊與圖的連通性(3)定義6

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

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

在有向圖G=<V,E>中，如果從結點u和v有一條路，則稱從u可達v。如果u可達v，則u、v之間的最短路（短程線）的長度稱為結點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<u,v>=。

距離的概念也適用于無向圖

注意，因為是有向圖，d<u,v>一般不等于d<v,u>。將D=max{d<u,v>|u,vG}稱為圖G的直徑。可達性是有向圖結點集上的二元關系，它是自反的和傳遞的，但一般不是對稱的。所以可達不是等價關系。85、有向圖的連通性（1）定義8在簡單有向圖G中，任何一對結點間，如果至少從一個結點到另一個結點可達，則稱該圖是單側連通的。如果圖G中任何一對結點之間相互可達，則稱圖G是強連通的。如果在圖G中略去邊的方向視為無向圖是連通的，則稱圖G是弱連通的。例：分析下列各有向圖的連通性。解：圖G1是強連通的；G2是單側連通的；G3是弱連通的。95、有向圖的連通性（2）定理4一個有向圖是強連通的，當且僅當G中有一個回路，它至少包含每個結點一次。證：充分性。如果圖G中有一個回路，它至少包含每個結點一次，則G中任何兩個結點相互可達，故圖G是強連通的。

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