離散數(shù)學(xué)通路回路與圖的連通性

1、離散數(shù)學(xué)通路回路與圖的連通性1第1頁，共42頁。 在圖中，一條通路是頂點(diǎn)和邊的交替序列，以頂點(diǎn)在圖中，一條通路是頂點(diǎn)和邊的交替序列，以頂點(diǎn) 開始，以頂點(diǎn)結(jié)束。其中，第一條邊的終點(diǎn)與第二開始，以頂點(diǎn)結(jié)束。其中，第一條邊的終點(diǎn)與第二 條邊的始點(diǎn)重合條邊的始點(diǎn)重合.。第一條邊的始點(diǎn)稱為通路的。第一條邊的始點(diǎn)稱為通路的 始點(diǎn)，最后一條邊的終點(diǎn)稱為通路的終點(diǎn)。始點(diǎn)，最后一條邊的終點(diǎn)稱為通路的終點(diǎn)。 當(dāng)通路的終點(diǎn)和始點(diǎn)重合時(shí)，稱為回路。當(dāng)通路的終點(diǎn)和始點(diǎn)重合時(shí)，稱為回路。通路或回路中所含邊數(shù)稱為該通路或回路的長度。通路或回路中所含邊數(shù)稱為該通路或回路的長度。一、通路和回路一、通路和回路 2第2頁，共42頁

2、。1、簡單通路：如果通路中各邊都不相同。、簡單通路：如果通路中各邊都不相同。如簡單通路：如簡單通路：v1v2 v5 v6 v2 v3 v4長度為長度為6如簡單回路：如簡單回路：v1v2 v3 v5 v2 v6 v1長度為長度為62、簡單回路：如果回路中各邊都不相同。、簡單回路：如果回路中各邊都不相同。3第3頁，共42頁。3、基本通路：如果通路中各個(gè)頂點(diǎn)都不相同。、基本通路：如果通路中各個(gè)頂點(diǎn)都不相同。4、基本回路：如果回路中各個(gè)頂點(diǎn)都不相同。、基本回路：如果回路中各個(gè)頂點(diǎn)都不相同。如基本通路：如基本通路：v1v6 v3 v4長度為長度為3如基本回路：如基本回路：v1v6 v3 v2 v1顯然，

3、基本通路（回路）一定是簡單通路（回路）。顯然，基本通路（回路）一定是簡單通路（回路）。反之不然。反之不然。4第4頁，共42頁。若通路若通路(回路回路)中有邊重復(fù)出現(xiàn)中有邊重復(fù)出現(xiàn), 則稱為則稱為復(fù)雜通路復(fù)雜通路(回路回路).5第5頁，共42頁。關(guān)于通路與回路的幾點(diǎn)說明關(guān)于通路與回路的幾點(diǎn)說明n表示方法表示方法 用頂點(diǎn)和邊的交替序列用頂點(diǎn)和邊的交替序列(定義定義), 如如 =v0e1v1e2elvl 用邊的序列用邊的序列, 如如 =e1e2el 簡單圖中簡單圖中, 用頂點(diǎn)的序列用頂點(diǎn)的序列, 如如 =v0v1vl 非簡單圖中非簡單圖中,可用混合表示法可用混合表示法,如如 =v0v1e2v2e5v

4、3v4v5n環(huán)是長度為環(huán)是長度為1的圈的圈, 兩條平行邊構(gòu)成長度為兩條平行邊構(gòu)成長度為2的圈的圈.n在無向簡單圖中在無向簡單圖中, 所有圈的長度所有圈的長度 3; 在有向簡單圖中在有向簡單圖中, 所所有圈的長度有圈的長度 2. 6第6頁，共42頁。n在兩種意義下計(jì)算的圈個(gè)數(shù)在兩種意義下計(jì)算的圈個(gè)數(shù) 定義意義下定義意義下 在無向圖中在無向圖中, 一個(gè)長度為一個(gè)長度為l(l 3)的圈看作的圈看作2l個(gè)不同的圈個(gè)不同的圈. 如如v0v1v2v0 , v1v2v0v1 , v2v0v1v2看作看作3個(gè)不同的圈個(gè)不同的圈. 在有向圖中在有向圖中, 一個(gè)長度為一個(gè)長度為l(l 3)的圈看作的圈看作l個(gè)不同

5、的圈個(gè)不同的圈. 同構(gòu)意義下同構(gòu)意義下 所有長度相同的圈都是同構(gòu)的所有長度相同的圈都是同構(gòu)的, 因而是因而是1個(gè)圈個(gè)圈. 7第7頁，共42頁。定理定理 在在n階圖階圖G中，若從頂點(diǎn)中，若從頂點(diǎn)vi到到vj（vi vj）存在通路，）存在通路，則從則從vi到到vj存在長度小于等于存在長度小于等于n 1的通路的通路.推論推論 在在n階圖階圖G中，若從頂點(diǎn)中，若從頂點(diǎn)vi到到vj（vi vj）存在通）存在通路，則從路，則從vi到到vj存在長度小于等于存在長度小于等于n 1的初級(jí)通路的初級(jí)通路.定理定理 在一個(gè)在一個(gè)n階圖階圖G中，若存在中，若存在vi到自身的回路，則一到自身的回路，則一定存在定存在vi

6、到自身長度小于等于到自身長度小于等于n的回路的回路.推論推論 在一個(gè)在一個(gè)n階圖階圖G中，若存在中，若存在vi到自身的簡單回路，到自身的簡單回路，則一定存在長度小于等于則一定存在長度小于等于n的初級(jí)回路的初級(jí)回路. 8第8頁，共42頁。在圖在圖G中，如果中，如果A到到B存在一條通路，則稱存在一條通路，則稱A到到B是可達(dá)的。是可達(dá)的。1、無向圖的連通性、無向圖的連通性如果無向圖中，任意兩點(diǎn)是可達(dá)的，圖為連通圖。否則為如果無向圖中，任意兩點(diǎn)是可達(dá)的，圖為連通圖。否則為不連通圖。不連通圖。當(dāng)圖是不連通時(shí)，定是由幾個(gè)連通子圖構(gòu)成。稱這樣的連當(dāng)圖是不連通時(shí)，定是由幾個(gè)連通子圖構(gòu)成。稱這樣的連通圖是連通分

7、支。通圖是連通分支。二、圖的連通性：二、圖的連通性：9第9頁，共42頁。無向圖的連通性無向圖的連通性 設(shè)無向圖設(shè)無向圖G=,u與與v連通連通: 若若u與與v之間有通路之間有通路. 規(guī)定規(guī)定u與自身總連通與自身總連通.連通關(guān)系連通關(guān)系 R=| u,v V且且u v是是V上的等價(jià)關(guān)系上的等價(jià)關(guān)系連通圖連通圖: 平凡圖平凡圖, 任意兩點(diǎn)都連通的圖任意兩點(diǎn)都連通的圖連通分支連通分支: V關(guān)于關(guān)于R的等價(jià)類的導(dǎo)出子圖的等價(jià)類的導(dǎo)出子圖 設(shè)設(shè)V/R=V1,V2,Vk, GV1, GV2, ,GVk是是G的連通的連通分支分支, 其個(gè)數(shù)記作其個(gè)數(shù)記作p(G)=k.G是連通圖是連通圖 p(G)=110第10頁，

8、共42頁。設(shè)設(shè) A=1,2,8, R= | x,yAxy(mod 3) 即即:A上模上模3等價(jià)關(guān)系的關(guān)系圖為等價(jià)關(guān)系的關(guān)系圖為:11第11頁，共42頁。n 【例】【例】 求證：若圖中只有兩個(gè)奇度數(shù)頂點(diǎn)，則二頂求證：若圖中只有兩個(gè)奇度數(shù)頂點(diǎn)，則二頂點(diǎn)必連通。點(diǎn)必連通。n 證明證明 用反證法來證明。用反證法來證明。n 設(shè)二頂點(diǎn)不連通，則它們必分屬兩個(gè)不同的連通分設(shè)二頂點(diǎn)不連通，則它們必分屬兩個(gè)不同的連通分支，而對(duì)于每個(gè)連通分支，作為支，而對(duì)于每個(gè)連通分支，作為G的子圖只有一個(gè)奇的子圖只有一個(gè)奇度數(shù)頂點(diǎn)，余者均為偶度數(shù)頂點(diǎn)，與握手定理推論矛度數(shù)頂點(diǎn)，余者均為偶度數(shù)頂點(diǎn)，與握手定理推論矛盾，因此，若圖

9、中只有兩個(gè)奇度數(shù)頂點(diǎn)，則二頂點(diǎn)必盾，因此，若圖中只有兩個(gè)奇度數(shù)頂點(diǎn)，則二頂點(diǎn)必連通。連通。12第12頁，共42頁。 【例】【例】 在一次國際會(huì)議中，由七人組成的小在一次國際會(huì)議中，由七人組成的小組組a,b,c,d,e,f,g中，中，a會(huì)英語、阿拉伯語；會(huì)英語、阿拉伯語；b會(huì)英語、西班牙語；會(huì)英語、西班牙語；c會(huì)漢語、俄語；會(huì)漢語、俄語；d會(huì)會(huì)日語、西班牙語；日語、西班牙語；e會(huì)德語、漢語和法語；會(huì)德語、漢語和法語；f會(huì)日語、俄語；會(huì)日語、俄語；g會(huì)英語、法語和德語。問：會(huì)英語、法語和德語。問：他們中間任何二人是否均可對(duì)話（必要時(shí)可他們中間任何二人是否均可對(duì)話（必要時(shí)可通過別人翻譯）？通過別人翻

10、譯）？13第13頁，共42頁。dabfgcen解解 用頂點(diǎn)代表人，如果二人會(huì)同一種語言，則在代表二用頂點(diǎn)代表人，如果二人會(huì)同一種語言，則在代表二人的頂點(diǎn)間連邊，于是得到下圖。問題歸結(jié)為：在這個(gè)圖人的頂點(diǎn)間連邊，于是得到下圖。問題歸結(jié)為：在這個(gè)圖中，任何兩個(gè)頂點(diǎn)間是否都存在著通路？由于下圖是一個(gè)中，任何兩個(gè)頂點(diǎn)間是否都存在著通路？由于下圖是一個(gè)連通圖，因此，必要時(shí)通過別人翻譯，他們中間任何二人連通圖，因此，必要時(shí)通過別人翻譯，他們中間任何二人均可對(duì)話。均可對(duì)話。14第14頁，共42頁。定理定理 在在n階簡單圖階簡單圖G, 如果對(duì)如果對(duì)G的的每對(duì)頂點(diǎn)每對(duì)頂點(diǎn)u和和v, deg(u) + deg(v

11、) n1, 則則G是連通圖。是連通圖。證明證明 假設(shè)假設(shè)G不連通不連通, 則則G至少有兩個(gè)分圖至少有兩個(gè)分圖。設(shè)其中一個(gè)分圖含有設(shè)其中一個(gè)分圖含有q個(gè)頂點(diǎn)個(gè)頂點(diǎn), 而其余各分圖共含有而其余各分圖共含有n q個(gè)頂點(diǎn)。個(gè)頂點(diǎn)。在這兩部分中各取一個(gè)頂點(diǎn)在這兩部分中各取一個(gè)頂點(diǎn)u和和v, 則則0deg(u)q 1,0deg(v)n q 1,因此因此deg(u) + deg(v)n 2,這與題設(shè)這與題設(shè)deg(u ) + deg(v)n 1矛盾。矛盾。15第15頁，共42頁。短程線與距離短程線與距離u與與v之間的短程線之間的短程線: u與與v之間長度最短的通路之間長度最短的通路 (u與與v連通連通)u與

12、與v之間的距離之間的距離d(u,v): u與與v之間短程線的長之間短程線的長度度若若u與與v不連通不連通, 規(guī)定規(guī)定d(u,v)=.性質(zhì)：性質(zhì)： d(u,v) 0, 且且d(u,v)=0 u=v d(u,v)=d(v,u) d(u,v)+d(v,w) d(u,w) 16第16頁，共42頁。n在實(shí)際問題中在實(shí)際問題中, 除了考察一個(gè)圖是否連除了考察一個(gè)圖是否連通外通外, 往往還要研究一個(gè)圖往往還要研究一個(gè)圖連通的程度連通的程度, 作為某些系統(tǒng)的作為某些系統(tǒng)的可靠性度量可靠性度量。n圖的連通性在計(jì)算機(jī)網(wǎng)、通信網(wǎng)和電力圖的連通性在計(jì)算機(jī)網(wǎng)、通信網(wǎng)和電力網(wǎng)等方面有著重要的應(yīng)用。網(wǎng)等方面有著重要的應(yīng)用。

13、圖的連通性的應(yīng)用圖的連通性的應(yīng)用17第17頁，共42頁。點(diǎn)割集點(diǎn)割集 在連通圖中，如果刪去一些頂點(diǎn)或邊，則可在連通圖中，如果刪去一些頂點(diǎn)或邊，則可能會(huì)影響圖的連通性。所謂從圖中刪去某個(gè)能會(huì)影響圖的連通性。所謂從圖中刪去某個(gè)頂點(diǎn)頂點(diǎn)v，就是將頂點(diǎn)，就是將頂點(diǎn)v和與和與v關(guān)聯(lián)的所有的邊關(guān)聯(lián)的所有的邊均刪去；均刪去；刪除邊只需將該邊刪除刪除邊只需將該邊刪除18第18頁，共42頁。 例如例如”國際會(huì)議對(duì)話”任何一人請(qǐng)假，圖任何一人請(qǐng)假，圖G-v還連通，還連通，小組對(duì)話仍可繼續(xù)進(jìn)行，但如果小組對(duì)話仍可繼續(xù)進(jìn)行，但如果f、g二人同時(shí)不在，二人同時(shí)不在，G-f，g是分離圖，則小組中的對(duì)話無法再繼續(xù)進(jìn)行。是分

14、離圖，則小組中的對(duì)話無法再繼續(xù)進(jìn)行。 dabfgce19第19頁，共42頁。點(diǎn)割集點(diǎn)割集 記記 G v: 從從G中刪除中刪除v及關(guān)聯(lián)的邊及關(guān)聯(lián)的邊 G V : 從從G中刪除中刪除V 中所有的頂點(diǎn)及關(guān)聯(lián)的邊中所有的頂點(diǎn)及關(guān)聯(lián)的邊 G e : 從從G中刪除中刪除e G E : 從從G中刪除中刪除E 中所有邊中所有邊定義定義 設(shè)無向圖設(shè)無向圖G=, VV, 若若p(G V )p(G)且且 V V , p(G V )=p(G), 則稱則稱V 為為G的的點(diǎn)割集點(diǎn)割集. 若若v為為點(diǎn)割集點(diǎn)割集, 則稱則稱v為為割點(diǎn)割點(diǎn).20第20頁，共42頁。點(diǎn)割集點(diǎn)割集( (續(xù)續(xù)) )例例 v1,v4, v6是點(diǎn)割集是

15、點(diǎn)割集, v6是割點(diǎn)是割點(diǎn). 21第21頁，共42頁。例例 v2, v7, v3, v4為為點(diǎn)割集點(diǎn)割集, v3, v4均為均為割點(diǎn)割點(diǎn)例例 在下圖中的那些是在下圖中的那些是割點(diǎn)割點(diǎn) v3和和v2都都是割點(diǎn)是割點(diǎn), v2, v3,v4,v1, v2, v4,v5都都不不是點(diǎn)割集。是點(diǎn)割集。v7v2v3v1v4v5v6e4e2e3e1e7e9e8e6e522第22頁，共42頁。邊割集邊割集定義定義 設(shè)無向圖設(shè)無向圖G=, EE, 若若p(G E )p(G)且且 E E , p(G E )=p(G), 則稱則稱E 為為G的的邊割集邊割集. 若若e為邊割集為邊割集, 則稱則稱e為為割邊割邊或或橋橋.

16、在下圖中，在下圖中，e1,e2，e1,e3,e5,e6，e8等是邊割集，等是邊割集，e8是橋，是橋，e7,e9,e5,e6是邊割集嗎？是邊割集嗎？23第23頁，共42頁。圖中圖中 e1, e2, e1, e3, e4, e6, e7, e8, e2, e3, e4, e2, e3, e5, e4, e5, e7, e9, e8, e9,等都是割集等都是割集, 其中其中e6為為橋。橋。n割點(diǎn)或割邊都是圖連通的割點(diǎn)或割邊都是圖連通的關(guān)鍵部位關(guān)鍵部位, 并不是所有的圖都有并不是所有的圖都有割點(diǎn)或割邊割點(diǎn)或割邊。n沒有割點(diǎn)和割邊的連通圖沒有割點(diǎn)和割邊的連通圖, 需要去掉幾條邊或幾個(gè)點(diǎn)需要去掉幾條邊或幾

17、個(gè)點(diǎn), 圖才會(huì)圖才會(huì)變得不連通。變得不連通。v7v2v3v1v4v5v6e4e2e3e1e7e9e8e6e524第24頁，共42頁。幾點(diǎn)說明：幾點(diǎn)說明：Kn無點(diǎn)割集無點(diǎn)割集n階零圖既無點(diǎn)割集，也無邊割集階零圖既無點(diǎn)割集，也無邊割集.若若G連通，連通，E 為邊割集，則為邊割集，則p(G E )=2若若G連通，連通，V 為點(diǎn)割集，則為點(diǎn)割集，則p(G V ) 2 一個(gè)連通圖一個(gè)連通圖G，若存在點(diǎn)割集和邊割集，一般并不唯，若存在點(diǎn)割集和邊割集，一般并不唯一，且各個(gè)點(diǎn)（邊）割集中所含的點(diǎn)（邊）的個(gè)數(shù)一，且各個(gè)點(diǎn)（邊）割集中所含的點(diǎn)（邊）的個(gè)數(shù)也不盡相同。我們用含元素個(gè)數(shù)最少的點(diǎn)割集和邊也不盡相同。我們

18、用含元素個(gè)數(shù)最少的點(diǎn)割集和邊割集來刻畫它的連通度割集來刻畫它的連通度25第25頁，共42頁。下面從下面從數(shù)量觀點(diǎn)數(shù)量觀點(diǎn)來描述圖的連通性。來描述圖的連通性。定義定義 設(shè)設(shè)G = (V, E)是連通圖是連通圖, k(G) = min| V | | V 是是G的點(diǎn)割集的點(diǎn)割集稱為稱為G的的點(diǎn)連通度點(diǎn)連通度; (G) = min| E | | E 是是G的邊割集的邊割集稱為稱為G的的邊連通度邊連通度。n圖圖G的點(diǎn)連通度是為了使的點(diǎn)連通度是為了使G成為一個(gè)成為一個(gè)非連通圖非連通圖,需要?jiǎng)h需要?jiǎng)h除的點(diǎn)的最少數(shù)目除的點(diǎn)的最少數(shù)目。若圖若圖G中存在割點(diǎn)中存在割點(diǎn), k(G) = 1。n圖圖G的邊連通度是為了

19、使的邊連通度是為了使G成為一個(gè)成為一個(gè)非連通圖非連通圖, 需要?jiǎng)h需要?jiǎng)h除的邊的最少數(shù)目除的邊的最少數(shù)目。若圖若圖G中存在割邊中存在割邊, (G) = 1。26第26頁，共42頁。G1G2【例】【例】 下圖中的兩個(gè)連通圖都是下圖中的兩個(gè)連通圖都是n=8，e=16，其，其中中,（G1）=4,(G1）=4,（G2）=1，（G2）=3。27第27頁，共42頁。n假設(shè)假設(shè)n n個(gè)頂點(diǎn)代表個(gè)頂點(diǎn)代表n個(gè)站，個(gè)站，e e條邊表示鐵路或者條邊表示鐵路或者橋梁或者電話線，橋梁或者電話線，en-1en-1。為了使。為了使n n個(gè)站之間個(gè)站之間的連接不容易被破壞，必須構(gòu)造一個(gè)具有的連接不容易被破壞，必須構(gòu)造一個(gè)具有

20、n n個(gè)個(gè)頂點(diǎn)頂點(diǎn)e e條邊的連通圖，并使其具有最大的點(diǎn)連條邊的連通圖，并使其具有最大的點(diǎn)連通度和邊連通度。按圖中通度和邊連通度。按圖中G G1 1的連接法，如果的連接法，如果3 3個(gè)站被破壞，或者個(gè)站被破壞，或者3 3條鐵路被破壞，余下的站條鐵路被破壞，余下的站仍能繼續(xù)相互聯(lián)系，也就是仍具有連通性。仍能繼續(xù)相互聯(lián)系，也就是仍具有連通性。但按圖中但按圖中G G2 2的連接法，如果的連接法，如果v v站被破壞，余下站被破壞，余下的站就不能保持連通。的站就不能保持連通。 28第28頁，共42頁。定理定理 對(duì)任意的圖對(duì)任意的圖G = (V, E),有有 k(G) (G) (G)(*)證明證明 若若G

21、是平凡圖或非連通圖是平凡圖或非連通圖, 則則 k(G) = (G) = 0, 上式顯然成立。上式顯然成立。n若若G是連通圖是連通圖, 則因則因每一頂點(diǎn)的所有關(guān)聯(lián)邊每一頂點(diǎn)的所有關(guān)聯(lián)邊構(gòu)成一個(gè)構(gòu)成一個(gè)邊割邊割集集, 所以所以 (G) (G)。n下面證明下面證明k (G) (G)。若若 (G) = 1, 則則G有一割邊有一割邊,此時(shí)此時(shí) k(G) = (G) = 1, (*) 式成立。式成立。29第29頁，共42頁。n若若 (G)2, 則必可刪去某則必可刪去某 (G)邊邊, 使使G不連通不連通,而刪去而刪去其中其中 (G) 1條邊條邊, G仍然連通仍然連通, 且有一條橋且有一條橋e = u, v。

22、n對(duì)對(duì) (G) 1條邊中的每一條邊都選取一個(gè)不同于條邊中的每一條邊都選取一個(gè)不同于u, v的的頂點(diǎn)頂點(diǎn), 把這些把這些 (G) 1個(gè)頂點(diǎn)刪去則必至少刪去個(gè)頂點(diǎn)刪去則必至少刪去 (G) 1邊。邊。n若剩下的圖是若剩下的圖是不連通不連通的的, 則則k(G) (G)1 (G); n若剩下的圖是若剩下的圖是連通連通的的, 則則e仍是橋仍是橋, 此時(shí)此時(shí)再刪去再刪去u和和v, 就就必產(chǎn)生一個(gè)必產(chǎn)生一個(gè)非連通圖非連通圖, 也有也有k (G) (G)。n綜上所述綜上所述, 對(duì)任意的圖對(duì)任意的圖G, 有有k (G) (G) (G)。 30第30頁，共42頁。例例 在下圖中在下圖中, k(G) = 1, (G)

23、 = 2, (G) = 3定義定義 設(shè)有圖設(shè)有圖G = (V, E), 若若k(G)h, 則稱則稱G是是h-連通連通的的; 若若 (G)h, 則稱則稱G是是h-邊連通邊連通的。的。例例 上上圖所示的圖是圖所示的圖是1-連通連通的的, 是是2-邊連通邊連通的。的。 31第31頁，共42頁。n簡單圖都是簡單圖都是1-連通的和連通的和1-邊連通的邊連通的。nn階完全圖是階完全圖是(n1)-連通的和連通的和(n1)-邊連通的邊連通的。n對(duì)于任何對(duì)于任何n階連通圖階連通圖, 當(dāng)且僅當(dāng)沒有割點(diǎn)時(shí)當(dāng)且僅當(dāng)沒有割點(diǎn)時(shí), 它是它是2-連通的連通的; n當(dāng)且僅當(dāng)沒有割邊時(shí)當(dāng)且僅當(dāng)沒有割邊時(shí), 它是它是2-邊連通的

24、邊連通的。n若圖若圖G是是h-連通的連通的, 則則G也是也是h-邊邊連通的。連通的。(k(G) (G)n由定義可知由定義可知, 若若h1h2, 圖圖G是是h1-連通的連通的, 則則G也是也是h2-連通的。連通的。n若若h1h2, 圖圖G是是h1-邊連通的邊連通的, 則則G也是也是h2-邊邊連通。連通。n一個(gè)一個(gè)圖的連通度越大圖的連通度越大, 它的連通性能就越好它的連通性能就越好。32第32頁，共42頁。n例如例如:下圖的邊連通度是下圖的邊連通度是3，所以它是，所以它是3邊連通邊連通的，也是的，也是2邊連通的和邊連通的和1-邊連通的，但不是邊連通的，但不是4邊連通的。邊連通的。33第33頁，共4

25、2頁。2、有向圖的連通性、有向圖的連通性對(duì)于有向圖，對(duì)于有向圖，“圖中任意兩點(diǎn)都有通路相連圖中任意兩點(diǎn)都有通路相連”，這個(gè)要求，這個(gè)要求很高，因?yàn)橛邢驁D雖然是連在一起的，但受到邊的方向很高，因?yàn)橛邢驁D雖然是連在一起的，但受到邊的方向的限制，任意兩點(diǎn)不一定有通路。以下分三種情況討論：的限制，任意兩點(diǎn)不一定有通路。以下分三種情況討論：34第34頁，共42頁。1）強(qiáng)連通圖：有向圖中，任意）強(qiáng)連通圖：有向圖中，任意A、B是互為可達(dá)的。如圖是互為可達(dá)的。如圖(a)2）單向連通圖：在有向圖中，任意兩點(diǎn)）單向連通圖：在有向圖中，任意兩點(diǎn)A、B存在著存在著A到到B的通路的通路 或存在著或存在著B到到A的通路。

26、如圖的通路。如圖(b)3）弱連通圖：在有向圖中，如果其底圖是無向連通圖。如圖）弱連通圖：在有向圖中，如果其底圖是無向連通圖。如圖(c) 顯然：在有向圖中，如果有一條通過圖中所有點(diǎn)的回路，顯然：在有向圖中，如果有一條通過圖中所有點(diǎn)的回路，則此圖是強(qiáng)連通的。則此圖是強(qiáng)連通的。 如果有一條通過圖中所有點(diǎn)的通路，如果有一條通過圖中所有點(diǎn)的通路，則此圖是單向連通圖。則此圖是單向連通圖。 (a) (b) (c)35第35頁，共42頁。單向連通圖都是弱連通圖，但弱連通圖單向連通圖都是弱連通圖，但弱連通圖卻不一定是單向連通圖。卻不一定是單向連通圖。 在弱連通圖中，存在這樣的頂點(diǎn)在弱連通圖中，存在這樣的頂點(diǎn)A、B，從從A到到B不可達(dá)，且從不可達(dá)，且從B 到到A也不可達(dá)。也不可達(dá)。 強(qiáng)連通圖既是單向連通圖，又是弱連通圖。強(qiáng)連通圖既是單向連通圖，又是弱連通圖。即即強(qiáng)連通強(qiáng)連通單向連通單向連通弱連通弱連通 36第36頁，共42頁。有向圖的連通性有向圖的連通性( (續(xù)續(xù)) ) 定理定理(強(qiáng)連通判別法強(qiáng)連通判別法) D強(qiáng)連通當(dāng)且僅當(dāng)強(qiáng)連通當(dāng)且僅當(dāng)D中存在經(jīng)過每個(gè)中存在經(jīng)過每個(gè)頂點(diǎn)至少一次的回路頂點(diǎn)至少一次的回路定理定理(單向連通判別法單向連通判別法) D單向連通當(dāng)且僅當(dāng)單向連通當(dāng)且僅當(dāng)D中存在經(jīng)中存在經(jīng)過每個(gè)頂點(diǎn)至少一次的通路過每個(gè)頂點(diǎn)至少一次的通路 (1