離散數(shù)學623圖連性

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

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

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

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

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

6、都連通的圖任意兩點都連通的圖. 平凡圖是連通圖平凡圖是連通圖連通關(guān)系連通關(guān)系 r=| u,v v且且u與與v連通連通. r是等價關(guān)系是等價關(guān)系連通分支連通分支: v關(guān)于關(guān)于r的等價類的導出子圖的等價類的導出子圖設(shè)設(shè)v/r=v1,v2,vk, g的連通分支為的連通分支為gv1,gv2,gvk連通分支數(shù)連通分支數(shù)p(g)=kg是連通圖是連通圖 p(g)=1課件8短程線與距離短程線與距離u與與v之間的短程線之間的短程線:u與與v之間長度最短的通路之間長度最短的通路(設(shè)設(shè)u與與v連通連通)u與與v之間的距離之間的距離d(u,v):u與與v之間短程線的長度之間短程線的長度若若u與與v不連通不連通, 規(guī)定

7、規(guī)定d(u,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課件9點割集與邊割集點割集與邊割集設(shè)無向圖設(shè)無向圖g=, v v, e e, vv, ee. 記記g v: 從從g中刪除中刪除v及關(guān)聯(lián)的邊及關(guān)聯(lián)的邊g v : 從從g中刪除中刪除v 中所有的頂點及關(guān)聯(lián)的邊中所有的頂點及關(guān)聯(lián)的邊g e : 從從g中刪除中刪除eg e : 從從g中刪除中刪除e 中所有邊中所有邊

8、定義定義6.15 設(shè)無向圖設(shè)無向圖g=, vv, 若若p(g v )p(g)且且 v v , p(g v )=p(g), 則稱則稱v 為為g的的點割集點割集. 若若v為點割為點割集集, 則稱則稱v為為割點割點.設(shè)設(shè)ee, 若若p(g e )p(g)且且 e e , p(g e )=p(g), 則稱則稱e 為為g的的邊割集邊割集. 若若e為邊割集為邊割集, 則稱則稱e為為割邊割邊或或橋橋.課件10實例實例說明：說明：kn無點割集無點割集n階零圖既無點割集，也無邊割集階零圖既無點割集，也無邊割集.若若g連通，連通，e 為邊割集，則為邊割集，則p(g e )=2若若g連通，連通，v 為點割集，則為點

9、割集，則p(g v ) 2abcde fge1e2e3e4e5e6e7e8e9e, f點割集點割集:e,f ,割點割點:c,d 橋橋: e8, e9邊割集邊割集:e8,e9, e1,e2,e1, e3, e6, e1, e3, e4, e7課件11點連通度與邊連通度點連通度與邊連通度定義定義6.16 設(shè)無向連通圖設(shè)無向連通圖g=, (g)=min|v | | v 是是g的點割集或使的點割集或使g-v 成為平凡圖成為平凡圖 稱為稱為g的的點連通度點連通度 (g)=min|e | | e 是是g的邊割集的邊割集稱為稱為g的的邊連通度邊連通度例如例如3 (g)=3 (g)=課件12點連通度與邊連通度

10、點連通度與邊連通度(續(xù)續(xù))說明說明:(1) 若若g是平凡圖是平凡圖, 則則 (g)=0, (g)=0.(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)課件13有向圖的連通性及其分類有向圖的連通性及其分類設(shè)有向圖設(shè)有向圖d=, u,v v, u可達可達v: u到到v有通路有通路. 規(guī)定規(guī)定u到自身總是可達的到自

11、身總是可達的.u與與v相互可達相互可達: u可達可達v且且v可達可達ud弱連通弱連通(連通連通): 略去各邊的方向所得無向圖為連通圖略去各邊的方向所得無向圖為連通圖d單向連通單向連通: u,v v，u可達可達v 或或v可達可達u d強連通強連通: u,v v，u與與v相互可達相互可達d是強連通的當且僅當是強連通的當且僅當d中存在經(jīng)過所有頂點的回路中存在經(jīng)過所有頂點的回路d是單向連通的當且僅當是單向連通的當且僅當d中存在經(jīng)過所有頂點的通路中存在經(jīng)過所有頂點的通路課件14實例實例 強連通強連通單連通單連通弱連通弱連通課件15有向圖中的短程線與距離有向圖中的短程線與距離u到到v的短程線的短程線: u

12、到到v長度最短的通路長度最短的通路 (設(shè)設(shè)u可達可達v)距離距離d: u到到v的短程線的長度的短程線的長度若若u不可達不可達v, 規(guī)定規(guī)定d=.性質(zhì)：性質(zhì)： d 0, 且且d=0 u=v d+d d 注意注意: 沒有對稱性沒有對稱性課件166.3 圖的矩陣表示圖的矩陣表示 6.3.1 無向圖的關(guān)聯(lián)矩陣無向圖的關(guān)聯(lián)矩陣 6.3.2 有向無環(huán)圖的關(guān)聯(lián)矩陣有向無環(huán)圖的關(guān)聯(lián)矩陣 6.3.3 有向圖的鄰接矩陣有向圖的鄰接矩陣 有向圖中的通路數(shù)與回路數(shù)有向圖中的通路數(shù)與回路數(shù) 6.3.4 有向圖的可達矩陣有向圖的可達矩陣課件17無向圖的關(guān)聯(lián)矩陣無向圖的關(guān)聯(lián)矩陣設(shè)無向圖設(shè)無向圖g=, v=v1, v2, ,

13、 vn, e=e1, e2, , em. 令令mij為為vi與與ej的關(guān)聯(lián)次數(shù)的關(guān)聯(lián)次數(shù), 稱稱(mij)n m為為g的關(guān)聯(lián)矩陣的關(guān)聯(lián)矩陣, 記為記為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 課件18關(guān)聯(lián)矩陣的性質(zhì)關(guān)聯(lián)矩陣的性質(zhì)列相同列相同列與第列與第第第是平行邊是平行邊與與kjeemmnivdmmjmkjjiijimjijniij)4(2)3(,.,2 , 1),()2(,.,2 , 1, 2)1(,11(6

14、) ej是環(huán)是環(huán) 第第j列的一個元素為列的一個元素為2, 其余為其余為0(5) vi是孤立點是孤立點 第第i行全為行全為0課件19無環(huán)有向圖的關(guān)聯(lián)矩陣無環(huán)有向圖的關(guān)聯(lián)矩陣則稱則稱(mij)n m為為d的關(guān)聯(lián)矩陣的關(guān)聯(lián)矩陣, 記為記為m(d).的終點的終點為為，不關(guān)聯(lián)不關(guān)聯(lián)與與，的始點的始點為為jijijiijevevevm10,1設(shè)無環(huán)有向圖設(shè)無環(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)

15、性質(zhì)性質(zhì): (1) 每列恰好有一個每列恰好有一個1和一個和一個-1課件20實例實例v1v2v3v4e2e1e3e4e5e6e7m(d)=-1 1 0 0 0 1 1 0 -1 1 0 0 0 0 0 0 -1 -1 -1 1 -1 1 0 0 1 1 0 0課件21有向圖的鄰接矩陣有向圖的鄰接矩陣環(huán)的個數(shù)環(huán)的個數(shù)中中等于等于性質(zhì)性質(zhì)damanjvdanivdaniiijiijjniijinjij1)1(,)1(1)1(1)1()4()3(,.,2 , 1),()2(,.,2 , 1),()1(:設(shè)有向圖設(shè)有向圖d=, v=v1, v2, , vn, e=e1, e2, , em, 令令 為頂點

16、為頂點vi鄰接到頂點鄰接到頂點vj邊的條數(shù)，稱邊的條數(shù)，稱( )m n為為d的鄰接矩陣的鄰接矩陣, 記作記作a(d), 簡記作簡記作a.)1(ija)1(ija課件22實例實例a=1 1 0 00 0 1 01 0 0 01 0 2 0v1v2v3v4課件23有向圖中的通路數(shù)與回路數(shù)有向圖中的通路數(shù)與回路數(shù)定理定理6.6 設(shè)設(shè)a為為n階有向圖階有向圖d的鄰接矩陣的鄰接矩陣, 則則al(l 1)中元素中元素 等于等于d中中vi到到vj長度為長度為 l 的通路的通路(含回路含回路)數(shù)數(shù), 等于等于vi到自身長到自身長度為度為l 的回路數(shù)的回路數(shù), 等于等于d中長度為中長度為 l 的通路的通路(含回

17、路含回路)總數(shù)總數(shù), 等于等于d中長度為中長度為 l 的回路總數(shù)的回路總數(shù). )(liia)(lija ninjlija11)( niliia1)(課件24有向圖中的通路數(shù)與回路數(shù)有向圖中的通路數(shù)與回路數(shù)(續(xù)續(xù))推論推論 設(shè)設(shè)bl=a+a2+al(l 1), 則則bl中元素中元素 等于等于d中中vi到到vj長度小于等于長度小于等于 l 的通路的通路(含回路含回路)數(shù)數(shù), 等于等于d中中vi到到vi長度長度小于等于小于等于 l 的回路數(shù)的回路數(shù), 等于等于d中長度小于等于中長度小于等于l 的的通路通路(含回路含回路)數(shù)數(shù), 為為d中長度小于等于中長度小于等于l 的回路數(shù)的回路數(shù). ninjlij

18、b11)( niliib1)()(lijb)(liib課件25實例實例(續(xù)續(xù)) 說明說明: 在這里在這里, 通路和回路數(shù)是定義意義下的通路和回路數(shù)是定義意義下的a=1 1 0 00 0 1 01 0 0 01 0 2 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課件26有向圖的可達矩陣有向圖的可達矩陣性質(zhì)性質(zhì):p(d)主對角線上的元素全為主對角線上的元素全為1. d強連通當且僅當強連通當且僅當p(d)的元素全為的元素全為1.設(shè)有向圖設(shè)有向圖d=, v=v1, v2, , vn, 令令