1、1,6.2 圖的連通性,6.2.1 通路與回路 初級通路(回路)與簡單通路(回路) 6.2.2 無向圖的連通性與連通度 連通圖、連通分支 短程線與距離 點割集、割點、邊割集、割邊(橋) 點連通度與邊連通度,2,6.2 圖的連通性(續(xù)),6.2.3 有向圖的連通性及其分類 可達性 弱連通、單向連通、強連通 短程線與距離,3,通路與回路,定義6.13 給定圖G=(無向或有向的), G中頂點與邊 的交替序列=v0e1v1e2elvl. 若i(1il), ei=(vi1,vi)(對于有向圖, ei=), 則稱為 v0到vl的通路, v0和vl分別為通路的起點和終點, l為通路的 長度. 又若v0=vl

2、, 則稱為回路. 若通路(回路)中所有頂點(對于回路, 除v0=vl)各異, 則稱為 初級通路或路徑(初級回路或圈). 長度為奇數(shù)的圈稱作奇 圈,長度為偶數(shù)的圈稱作偶圈 若通路(回路)中所有邊各異, 則稱為簡單通路(簡單回路), 否則稱為復雜通路(復雜回路),4,說明,(1) 表示方法 按定義用頂點和邊的交替序列, =v0e1v1e2elvl 用邊序列, =e1e2el 簡單圖中, 用頂點序列, =v0v1vl (2) 在無向圖中, 長度為1的圈由環(huán)構成.長度為2的圈由兩 條平行邊構成. 在無向簡單圖中, 所有圈的長度3. 在有向圖中, 長度為1的圈由環(huán)構成. 在有向簡單圖中, 所 有圈的長度

3、2.,5,說明(續(xù)),(3) 初級通路(回路)是簡單通路(回路), 但反之不真,初級通路,非初級的簡單通路,初級回路,非初級的 簡單回路,6,通路與回路(續(xù)),定理6.3 在n階圖中, 若從頂點u到v(uv)存在通路, 則從u 到v存在長度小于等于n1的初級通路. 證 若通路中沒有相同的頂點(即初級通路), 長度必 n1. 若有相同的頂點, 刪去這兩個頂點之間的這一段, 仍是u到 v的通路. 重復進行, 直到沒有相同的頂點為止. 定理6.4 在n階圖中, 若存在v到自身的簡單回路, 則一定存 在v到自身長度小于等于n的初級回路.,7,無向圖的連通性與連通分支,設無向圖G=, u,vV u與v連

4、通: 若u與v之間有通路. 規(guī)定u與自身總是連通的. 連通圖: 任意兩點都連通的圖. 平凡圖是連通圖 連通關系 R=| u,v V且u與v連通. R是等價關系 連通分支: V關于R的等價類的導出子圖 設V/R=V1,V2,Vk, G的連通分支為GV1,GV2,GVk 連通分支數(shù)p(G)=k G是連通圖 p(G)=1,8,短程線與距離,u與v之間的短程線:u與v之間長度最短的通路(設u與v連通) u與v之間的距離d(u,v):u與v之間短程線的長度 若u與v不連通, 規(guī)定d(u,v)=. 性質： (1) d(u,v)0, 且d(u,v)=0 u=v (2) d(u,v)=d(v,u) (3) d

5、(u,v)+d(v,w)d(u,w),例如 a與e之間的短程線:ace,afe. d(a,e)=2, d(a,h)=,9,點割集與邊割集,設無向圖G=, vV, eE, VV, EE. 記 Gv: 從G中刪除v及關聯(lián)的邊 GV: 從G中刪除V中所有的頂點及關聯(lián)的邊 Ge : 從G中刪除e GE: 從G中刪除E中所有邊 定義6.15 設無向圖G=, VV, 若p(GV)p(G)且 VV, p(GV)=p(G), 則稱V為G的點割集. 若v為點割 集, 則稱v為割點. 設EE, 若p(GE)p(G)且EE, p(GE)=p(G), 則稱E 為G的邊割集. 若e為邊割集, 則稱e為割邊或橋.,10,

6、實例,說明：Kn無點割集 n階零圖既無點割集，也無邊割集. 若G連通，E為邊割集，則p(GE)=2 若G連通，V為點割集，則p(GV)2,e,f,點割集:e,f ,割點:,c,d,橋:,e8,e9,邊割集:e8,e9,e1,e2,e1, e3, e6,e1, e3, e4, e7,11,點連通度與邊連通度,定義6.16 設無向連通圖G=, (G)=min|V| | V是G的點割集或使G-V成為平凡圖 稱為G的點連通度 (G)=min|E| | E是G的邊割集 稱為G的邊連通度,例如,3,(G)=,3,(G)=,12,點連通度與邊連通度(續(xù)),說明: (1) 若G是平凡圖, 則(G)=0, (G

7、)=0. (2) 若G是完全圖Kn, 則(G)=n-1, (G)= n-1 (3) 若G中存在割點, 則(G)=1;若G中存在割邊, 則(G)= 1 (4) 規(guī)定非連通圖的點連通度和邊連通度均為0 定理6.5 對任何無向圖G, 有 (G) (G) (G),13,有向圖的連通性及其分類,設有向圖D=, u,vV, u可達v: u到v有通路. 規(guī)定u到自身總是可達的. u與v相互可達: u可達v且v可達u D弱連通(連通): 略去各邊的方向所得無向圖為連通圖 D單向連通: u,vV，u可達v 或v可達u D強連通: u,vV，u與v相互可達 D是強連通的當且僅當D中存在經過所有頂點的回路 D是單向

8、連通的當且僅當D中存在經過所有頂點的通路,14,實例,15,有向圖中的短程線與距離,u到v的短程線: u到v長度最短的通路 (設u可達v) 距離d: u到v的短程線的長度 若u不可達v, 規(guī)定d=. 性質： d0, 且d=0 u=v d+d d 注意: 沒有對稱性,16,6.3 圖的矩陣表示,6.3.1 無向圖的關聯(lián)矩陣 6.3.2 有向無環(huán)圖的關聯(lián)矩陣 6.3.3 有向圖的鄰接矩陣 有向圖中的通路數(shù)與回路數(shù) 6.3.4 有向圖的可達矩陣,17,無向圖的關聯(lián)矩陣,設無向圖G=, V=v1, v2, , vn, E=e1, e2, , em. 令mij為vi與ej的關聯(lián)次數(shù), 稱(mij)nm為

9、G的關聯(lián)矩陣, 記為 M(G). mij的可能取值為:0,1,2,例如,18,關聯(lián)矩陣的性質,(6) ej是環(huán) 第j列的一個元素為2, 其余為0,(5) vi是孤立點 第i行全為0,19,無環(huán)有向圖的關聯(lián)矩陣,20,實例,21,有向圖的鄰接矩陣,設有向圖D=, V=v1, v2, , vn, E=e1, e2, , em, 令 為頂點vi鄰接到頂點vj邊的條數(shù)，稱( )mn為D的鄰接矩陣, 記作A(D), 簡記作A.,22,實例,23,有向圖中的通路數(shù)與回路數(shù),定理6.6 設A為n階有向圖D的鄰接矩陣, 則Al(l1)中元素 等于D中vi到vj長度為 l 的通路(含回路)數(shù), 等于vi到自身長

10、 度為l 的回路數(shù), 等于D中長度為 l 的通路(含回路) 總數(shù), 等于D中長度為 l 的回路總數(shù).,24,有向圖中的通路數(shù)與回路數(shù)(續(xù)),推論 設Bl=A+A2+Al(l1), 則Bl中元素 等于D中vi到 vj長度小于等于 l 的通路(含回路)數(shù), 等于D中vi到vi長度 小于等于 l 的回路數(shù), 等于D中長度小于等于l 的 通路(含回路)數(shù), 為D中長度小于等于l 的回路數(shù).,25,實例(續(xù)),說明: 在這里, 通路和回路數(shù)是定義意義下的,v1到v2長為3的通路有1條 v1到v3長為3的通路有1條 v1到自身長為3的回路有2條 D中長為3的通路共有15條,其中回路3條,26,有向圖的可達矩陣,性質: P(D)主對角線上的元素全為1. D強連通當且僅當P(D)的元素全為1.,設有向圖D=, V=v1, v2, , vn, 令 稱(pij)nn為D的可達矩陣, 記作P(D), 簡記為P.,27,實例,例1 (1) v1到v4,v4到v1長為3的通路各有多少條? (2) v1到自身長為1,2,3,4的回路各有多少條? (3) 長為4的通路共有多少條?其中有多少條回路? (4)