離散數(shù)學--62-3圖的連通性ppt課件

1、6.2 圖的連通性圖的連通性 6.2.1 通路與回路通路與回路 初級通路初級通路(回路回路)與簡單通路與簡單通路(回路回路) 6.2.2 無向圖的連通性與連通度無向圖的連通性與連通度 連通圖、連通分支連通圖、連通分支 短程線與距離短程線與距離 點割集、割點、邊割集、割邊點割集、割點、邊割集、割邊(橋橋) 點連通度與邊連通度點連通度與邊連通度6.2 圖的連通性圖的連通性(續(xù)續(xù)) 6.2.3 有向圖的連通性及其分類有向圖的連通性及其分類 可達性可達性 弱連通、單向連通、強連通弱連通、單向連通、強連通 短程線與距離短程線與距離通路與回路通路與回路定義定義6.13 給定圖給定圖G=(無向或有向的無向或

2、有向的), G中頂點與邊中頂點與邊的交替序列的交替序列 =v0e1v1e2elvl.假設假設i(1il), ei=(vi1,vi)(對于有向圖對于有向圖, ei=), 則稱則稱 為為v0到到vl的通路的通路, v0和和vl分別為通路的起點和終點分別為通路的起點和終點, l為通路的為通路的長度長度. 又若又若v0=vl, 則稱則稱 為回路為回路.若通路若通路(回路回路)中所有頂點中所有頂點(對于回路對于回路, 除除v0=vl)各異各異, 則稱為則稱為初級通路或路徑初級通路或路徑(初級回路或圈初級回路或圈). 長度為奇數(shù)的圈稱作奇長度為奇數(shù)的圈稱作奇圈圈,長度為偶數(shù)的圈稱作偶圈長度為偶數(shù)的圈稱作偶

3、圈若通路若通路(回路回路)中所有邊各異中所有邊各異, 則稱為簡單通路則稱為簡單通路(簡單回路簡單回路), 否則稱為復雜通路否則稱為復雜通路(復雜回路復雜回路)闡明闡明(1) 表示方法表示方法 按定義用頂點和邊的交替序列按定義用頂點和邊的交替序列, =v0e1v1e2elvl 用邊序列用邊序列, =e1e2el 簡單圖中簡單圖中, 用頂點序列用頂點序列, =v0v1vl(2) 在無向圖中在無向圖中, 長度為長度為1的圈由環(huán)構成的圈由環(huán)構成.長度為長度為2的圈由兩的圈由兩條平行邊構成條平行邊構成. 在無向簡單圖中在無向簡單圖中, 所有圈的長度所有圈的長度3. 在有向圖中在有向圖中, 長度為長度為1

4、的圈由環(huán)構成的圈由環(huán)構成. 在有向簡單圖中在有向簡單圖中, 所所有圈的長度有圈的長度2.闡明闡明(續(xù)續(xù))(3) 初級通路初級通路(回路回路)是簡單通路是簡單通路(回路回路), 但反之不真但反之不真初級通路初級通路非初級的簡單通路非初級的簡單通路初級回路初級回路非初級的非初級的簡單回路簡單回路通路與回路通路與回路(續(xù)續(xù))定理定理6.3 在在n階圖中階圖中, 若從頂點若從頂點u到到v(uv)存在通路存在通路, 則從則從u到到v存在長度小于等于存在長度小于等于n1的初級通路的初級通路.證證 若通路中沒有相同的頂點若通路中沒有相同的頂點(即初級通路即初級通路), 長度必長度必 n1.若有相同的頂點若有

5、相同的頂點, 刪去這兩個頂點之間的這一段刪去這兩個頂點之間的這一段, 仍是仍是u到到v的通路的通路. 重復進行重復進行, 直到?jīng)]有相同的頂點為止直到?jīng)]有相同的頂點為止.定理定理6.4 在在n階圖中階圖中, 若存在若存在v到自身的簡單回路到自身的簡單回路, 則一定存則一定存在在v到自身長度小于等于到自身長度小于等于n的初級回路的初級回路.無向圖的連通性與連通分支無向圖的連通性與連通分支設無向圖設無向圖G=, u,vVu與與v連通連通: 若若u與與v之間有通路之間有通路. 規(guī)定規(guī)定u與自身總是連通的與自身總是連通的.連通圖連通圖: 任意兩點都連通的圖任意兩點都連通的圖. 平凡圖是連通圖平凡圖是連通

6、圖連通關系連通關系 R=| u,v V且且u與與v連通連通. R是等價關系是等價關系連通分支連通分支: V關于關于R的等價類的導出子圖的等價類的導出子圖設設 V / R = V 1 , V 2 , , V k , G 的 連 通 分 支 為的 連 通 分 支 為GV1,GV2,GVk連通分支數(shù)連通分支數(shù)p(G)=kG是連通圖是連通圖 p(G)=1短程線與距離短程線與距離u與與v之間的短程線之間的短程線:u與與v之間長度最短的通路之間長度最短的通路(設設u與與v連通連通)u與與v之間的距離之間的距離d(u,v):u與與v之間短程線的長度之間短程線的長度若若u與與v不連通不連通, 規(guī)定規(guī)定d(u,

7、v)=.性質(zhì)：性質(zhì)：(1) d(u,v)0, 且且d(u,v)=0 u=v(2) d(u,v)=d(v,u)(3) d(u,v)+d(v,w)d(u,w) 例如例如 a與與e之間的短程線之間的短程線:ace,afe. d(a,e)=2, d(a,h)=abcde f ghi點割集與邊割集點割集與邊割集設無向圖設無向圖G=, vV, eE, VV, EE. 記記Gv: 從從G中刪除中刪除v及關聯(lián)的邊及關聯(lián)的邊GV: 從從G中刪除中刪除V中所有的頂點及關聯(lián)的邊中所有的頂點及關聯(lián)的邊Ge : 從從G中刪除中刪除eGE: 從從G中刪除中刪除E中所有邊中所有邊定義定義6.15 設無向圖設無向圖G=, V

8、V, 若若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為割邊或橋為割邊或橋.實例實例闡明：闡明：Kn無點割集無點割集n階零圖既無點割集，也無邊割集階零圖既無點割集，也無邊割集.若若G連通，連通，E為邊割集，則為邊割集，則p(GE)=2若若G連通，連通，V為點割集，則為點割集，則p(GV)2abcde fge1e2e3e4e5e6e7

9、e8e9e, f點割集點割集:e,f ,割點割點:c,d 橋橋: e8,e9邊割集邊割集:e8,e9,e1,e2,e1, e3, e6,e1, e3, e4, e7點連通度與邊連通度點連通度與邊連通度定義定義6.16 設無向連通圖設無向連通圖G=, (G)=min|V| | V是是G的點割集或使的點割集或使G-V成為平凡圖成為平凡圖 稱為稱為G的點連通度的點連通度 (G)=min|E| | E是是G的邊割集的邊割集稱為稱為G的邊連通度的邊連通度例如例如3 (G)=3 (G)=點連通度與邊連通度點連通度與邊連通度(續(xù)續(xù))闡明闡明:(1) 若若G是平凡圖是平凡圖, 那么那么(G)=0, (G)=0

10、.(2) 若若G是完全圖是完全圖Kn, 那么那么(G)=n-1, (G)= n-1(3) 若若G中存在割點中存在割點, 那么那么(G)=1;若若G中存在割邊中存在割邊, 那么那么(G)= 1(4) 規(guī)定非連通圖的點連通度和邊連通度均為規(guī)定非連通圖的點連通度和邊連通度均為0定理定理6.5 對任何無向圖對任何無向圖G, 有有 (G) (G) (G)有向圖的連通性及其分類有向圖的連通性及其分類設有向圖設有向圖D=, u,vV, u可達可達v: u到到v有通路有通路. 規(guī)定規(guī)定u到自身總是可達的到自身總是可達的.u與與v相互可達相互可達: u可達可達v且且v可達可達uD弱連通弱連通(連通連通): 略去

11、各邊的方向所得無向圖為連通圖略去各邊的方向所得無向圖為連通圖D單向連通單向連通: u,vV，u可達可達v 或或v可達可達u D強連通強連通: u,vV，u與與v相互可達相互可達D是強連通的當且僅當是強連通的當且僅當D中存在經(jīng)過所有頂點的回路中存在經(jīng)過所有頂點的回路D是單向連通的當且僅當是單向連通的當且僅當D中存在經(jīng)過所有頂點的通路中存在經(jīng)過所有頂點的通路實例實例 強連通強連通單連通單連通弱連通弱連通有向圖中的短程線與距離有向圖中的短程線與距離u到到v的短程線的短程線: u到到v長度最短的通路長度最短的通路 (設設u可達可達v)距離距離d: u到到v的短程線的長度的短程線的長度若若u不可達不可達

12、v, 規(guī)定規(guī)定d=.性質(zhì)：性質(zhì)： d0, 且且d=0 u=v d+d d 留意留意: 沒有對稱性沒有對稱性6.3 圖的矩陣表示圖的矩陣表示 6.3.1 無向圖的關聯(lián)矩陣無向圖的關聯(lián)矩陣 6.3.2 有向無環(huán)圖的關聯(lián)矩陣有向無環(huán)圖的關聯(lián)矩陣 6.3.3 有向圖的鄰接矩陣有向圖的鄰接矩陣 有向圖中的通路數(shù)與回路數(shù)有向圖中的通路數(shù)與回路數(shù) 6.3.4 有向圖的可達矩陣有向圖的可達矩陣無向圖的關聯(lián)矩陣無向圖的關聯(lián)矩陣設無向圖設無向圖G=, V=v1, v2, , vn, E=e1, e2, , em. 令令mij為為vi與與ej的關聯(lián)次數(shù)的關聯(lián)次數(shù), 稱稱(mij)nm為為G的關聯(lián)矩陣的關聯(lián)矩陣, 記

13、為記為M(G). mij的可能取值為的可能取值為:0,1,2例如例如e1e2e3e4e5e6v5v1v2v3v4M(G)=2 1 1 0 0 00 1 0 1 1 10 0 0 0 1 10 0 0 0 0 00 0 1 1 0 0 關聯(lián)矩陣的性質(zhì)關聯(lián)矩陣的性質(zhì)列相同列相同列與第列與第第第是平行邊是平行邊與與kjeemmnivdmmjmkjjiijimjijniij)4(2)3(,.,2 , 1),()2(,.,2 , 1, 2)1(,11(6) ej是環(huán)是環(huán) 第第j列的一個元素為列的一個元素為2, 其余為其余為0(5) vi是孤立點是孤立點 第第i行全為行全為0無環(huán)有向圖的關聯(lián)矩陣無環(huán)有向圖

14、的關聯(lián)矩陣則稱則稱(mij)nm為為D的關聯(lián)矩陣的關聯(lián)矩陣, 記為記為M(D).的的終終點點為為，不不關關聯(lián)聯(lián)與與，的的始始點點為為jijijiijevevevm10,1設無環(huán)有向圖設無環(huán)有向圖D=, V=v1, v2, , vn, E=e1, e2, , em. 令令(3) ej與與ek是平行邊是平行邊 第第j列與第列與第k列相同列相同(2) 第第i行行1的個數(shù)等于的個數(shù)等于d+(v), 第第i行行-1的個數(shù)等于的個數(shù)等于d-(v)性質(zhì)性質(zhì): (1) 每列恰好有一個每列恰好有一個1和一個和一個-1實例實例v1v2v3v4e2e1e3e4e5e6e7M(D)=-1 1 0 0 0 1 1 0

15、-1 1 0 0 0 0 0 0 -1 -1 -1 1 -1 1 0 0 1 1 0 0有向圖的鄰接矩陣有向圖的鄰接矩陣環(huán)環(huán)的的個個數(shù)數(shù)中中等等于于性性質(zhì)質(zhì)Damanjvdanivdaniiijiijjniijinjij1)1(,)1(1)1(1)1()4()3(,.,2 , 1),()2(,.,2 , 1),()1(:設有向圖設有向圖D=, V=v1, v2, , vn, E=e1, e2, , em, 令令 為頂點為頂點vi鄰接到頂點鄰接到頂點vj邊的條數(shù)，稱邊的條數(shù)，稱( )mn為為D的鄰接矩的鄰接矩陣陣, 記作記作A(D), 簡記作簡記作A.)1(ija)1(ija實例實例A=1 1

16、0 00 0 1 01 0 0 01 0 2 0v1v2v3v4有向圖中的通路數(shù)與回路數(shù)有向圖中的通路數(shù)與回路數(shù)定理定理6.6 設設A為為n階有向圖階有向圖D的鄰接矩陣的鄰接矩陣, 則則Al(l1)中元素中元素 等于等于D中中vi到到vj長度為長度為 l 的通路的通路(含回路含回路)數(shù)數(shù), 等于等于vi到自身到自身長長度為度為l 的回路數(shù)的回路數(shù), 等于等于D中長度為中長度為 l 的通路的通路(含回路含回路)總數(shù)總數(shù), 等于等于D中長度為中長度為 l 的回路總數(shù)的回路總數(shù). )(liia)(lija ninjlija11)( niliia1)(有向圖中的通路數(shù)與回路數(shù)有向圖中的通路數(shù)與回路數(shù)(

17、續(xù)續(xù))推論推論 設設Bl=A+A2+Al(l1), 則則Bl中元素中元素 等于等于D中中vi到到vj長度小于等于長度小于等于 l 的通路的通路(含回路含回路)數(shù)數(shù), 等于等于D中中vi到到vi長長度度小于等于小于等于 l 的回路數(shù)的回路數(shù), 等于等于D中長度小于等于中長度小于等于l 的的通路通路(含回路含回路)數(shù)數(shù), 為為D中長度小于等于中長度小于等于l 的回路數(shù)的回路數(shù). ninjlijb11)( niliib1)()(lijb)(liib實例實例(續(xù)續(xù)) 闡明闡明: 在這里在這里, 通路和回路數(shù)是定義意義下的通路和回路數(shù)是定義意義下的A=1 1 0 00 0 1 01 0 0 01 0 2

18、 0A2=1 1 1 01 0 0 01 1 0 03 1 0 0A3=2 1 1 01 1 0 01 1 0 03 3 1 0A4=3 2 1 01 1 0 02 1 1 04 3 1 0v1到到v2長為長為3的通路有的通路有1條條v1到到v3長為長為3的通路有的通路有1條條v1到自身長為到自身長為3的回路有的回路有2條條D中長為中長為3的通路共有的通路共有15條條,其中回路其中回路3條條v1v2v3v4有向圖的可達矩陣有向圖的可達矩陣性質(zhì)性質(zhì):P(D)主對角線上的元素全為主對角線上的元素全為1. D強連通當且僅當強連通當且僅當P(D)的元素全為的元素全為1.設有向圖設有向圖D=, V=v1, v2, , vn, 令令 稱稱(