8.2-3通路、回路與圖的連通性

1、8.2 通路、回路與圖的連通性 (回)路, 初級通(回)路, 復雜通(回)路無向連通圖, 弱連通圖, 單向連通圖, 點割集與割點邊割集與割邊(橋) 1通路與回路 定義 給定圖G=（無向或有向的），G中頂點與邊的交替序列=v0e1v1e2elvl，(1) 若i(1il), vi1, vi是ei的端點(對于有向圖, 要求vi1是始點, vi是終點), 則稱為通路, v0是通路的起點, vl是通路的終點, l為通路的長度. 又若v0=vl，則稱為回路.(2) 若通路(回路)中所有頂點(對于回路, 除v0=vl)各異，則稱為初級通路(初級回路).初級通路又稱作路徑, 初級回路又稱作圈.(3) 若通路(

2、回路)中所有邊各異, 則稱為簡單通路(簡單回路), 否則稱為復雜通路(復雜回路).2通路與回路(續(xù))說明:表示方法 用頂點和邊的交替序列(定義), 如=v0e1v1e2elvl 用邊的序列, 如=e1e2el 簡單圖中, 用頂點的序列, 如=v0v1vl 非簡單圖中,可用混合表示法,如=v0v1e2v2e5v3v4v5環(huán)是長度為1的圈, 兩條平行邊構(gòu)成長度為2的圈.在無向簡單圖中, 所有圈的長度3; 在有向簡單圖中, 所有圈的長度2. 3通路與回路(續(xù))在兩種意義下計算的圈個數(shù) 定義意義下 在無向圖中, 一個長度為l(l3)的圈看作2l個不同的圈. 如v0v1v2v0 , v1v2v0v1 ,

3、 v2v0v1v2看作3個不同的圈. 在有向圖中, 一個長度為l(l3)的圈看作l個不同的圈. 同構(gòu)意義下 所有長度相同的圈都是同構(gòu)的, 因而是1個圈. 4通路與回路(續(xù)) 定理 在n階圖G中，若從頂點vi到vj（vivj）存在通路，則從vi到vj存在長度小于等于n1的通路.推論 在n階圖G中，若從頂點vi到vj（vivj）存在通路，則從vi到vj存在長度小于等于n1的初級通路.定理 在一個n階圖G中，若存在vi到自身的回路，則一定存在vi到自身長度小于等于n的回路.推論 在一個n階圖G中，若存在vi到自身的簡單回路，則一定存在長度小于等于n的初級回路. 5無向圖的連通性 設無向圖G=,u與v

4、連通: 若u與v之間有通路. 規(guī)定u與自身總連通.連通關(guān)系 R=| u,v V且uv是V上的等價關(guān)系連通圖: 平凡圖, 任意兩點都連通的圖連通分支: V關(guān)于R的等價類的導出子圖 設V/R=V1,V2,Vk, GV1, GV2, ,GVk是G的連通分支, 其個數(shù)記作p(G)=k.G是連通圖 p(G)=16短程線與距離u與v之間的短程線: u與v之間長度最短的通路 (u與v連通)u與v之間的距離d(u,v): u與v之間短程線的長度若u與v不連通, 規(guī)定d(u,v)=.性質(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) 7點割集

5、 記 Gv: 從G中刪除v及關(guān)聯(lián)的邊 GV: 從G中刪除V中所有的頂點及關(guān)聯(lián)的邊 Ge : 從G中刪除e GE: 從G中刪除E中所有邊定義 設無向圖G=, VV, 若p(GV)p(G)且VV, p(GV)=p(G), 則稱V為G的點割集. 若v為點割集, 則稱v為割點.8點割集(續(xù))例 v1,v4, v6是點割集, v6是割點. v2,v5是點割集嗎？ 9邊割集定義 設無向圖G=, EE, 若p(GE)p(G)且EE, p(GE)=p(G), 則稱E為G的邊割集. 若e為邊割集, 則稱e為割邊或橋.在上一頁的圖中，e1,e2，e1,e3,e5,e6，e8等是邊割集，e8是橋，e7,e9,e5,

6、e6是邊割集嗎？幾點說明：Kn無點割集n階零圖既無點割集，也無邊割集.若G連通，E為邊割集，則p(GE)=2若G連通，V為點割集，則p(GV)2 10有向圖的連通性 設有向圖D=u可達v: u到v有通路. 規(guī)定u到自身總是可達的.可達具有自反性和傳遞性D弱連通(連通): 基圖為無向連通圖D單向連通: u,vV，u可達v 或v可達u D強連通: u,vV，u與v相互可達強連通單向連通弱連通 11有向圖的連通性(續(xù)) 定理(強連通判別法) D強連通當且僅當D中存在經(jīng)過每個頂點至少一次的回路定理(單向連通判別法) D單向連通當且僅當D中存在經(jīng)過每個頂點至少一次的通路 (1)(2)(3)例 下圖(1)

7、強連通, (2)單連通, (3) 弱連通12有向圖的短程線與距離u到v的短程線: u到v長度最短的通路 (u可達v)u與v之間的距離d: u到v的短程線的長度若u不可達v, 規(guī)定d=.性質(zhì)： d0, 且d=0 u=v d+d d 注意: 沒有對稱性138.3 圖的矩陣表示 無向圖的關(guān)聯(lián)矩陣有向圖的關(guān)聯(lián)矩陣有向圖的鄰接矩陣有向圖的可達矩陣 14無向圖的關(guān)聯(lián)矩陣定義 設無向圖G=, V=v1, v2, , vn, E=e1, e2, , em, 令mij為vi與ej的關(guān)聯(lián)次數(shù)，稱(mij)nm為G的關(guān)聯(lián)矩陣，記為M(G). 性質(zhì)15有向圖的關(guān)聯(lián)矩陣定義 設無環(huán)有向圖D=, V=v1, v2, ,

8、vn, E=e1, e2, , em, 令 則稱(mij)nm為D的關(guān)聯(lián)矩陣，記為M(D).16有向圖的關(guān)聯(lián)矩陣(續(xù))性質(zhì) (4) 平行邊對應的列相同17定義 設有向圖D=, V=v1, v2, , vn, E=e1, e2, , em, 令 為頂點vi鄰接到頂點vj邊的條數(shù)，稱( )mn為D的鄰接矩陣, 記作A(D), 簡記為A. 性質(zhì)有向圖的鄰接矩陣18 D中的通路及回路數(shù)定理 設A為n階有向圖D的鄰接矩陣, 則Al(l1)中元素 為D中vi到vj長度為 l 的通路數(shù)， 為vi到自身長度為 l 的回路數(shù)， 為D中長度為 l 的通路總數(shù)， 為D中長度為 l 的回路總數(shù). 19D中的通路及回路數(shù)(續(xù))例 有向圖D如圖所示, 求A, A2, A3, A4, 并回答諸問題：(1) D中長度為1, 2, 3, 4的通路各有多 少條？其中回路分別為多少條？(2) D中長度小于或等于4的通路為多 少條？其中有多少條回路？ 推論 設Bl=A+A2+Al(l1), 則Bl中元素 為D中長度小于或等于l 的通路數(shù)， 為D中長度小于或等于l 的回路數(shù).20例(續(xù)) 長度 通路 回路 合計 50 818 1211 3314 1417 321有向圖的