離散數(shù)學圖的連通性

離散數(shù)學圖的連通性1第一頁，共二十八頁，編輯于2023年，星期日6.2圖的連通性(續(xù))6.2.3有向圖的連通性及其分類可達性弱連通、單向連通、強連通短程線與距離2第二頁，共二十八頁，編輯于2023年，星期日通路與回路定義6.13

給定圖G=<V,E>(無向或有向的),G中頂點與邊的交替序列=v0e1v1e2…elvl.若i(1il),ei=(vi1,vi)(對于有向圖,ei=<vi1,vi>),則稱為v0到vl的通路,v0和vl分別為通路的起點和終點,l為通路的長度.又若v0=vl,則稱為回路.若通路(回路)中所有頂點(對于回路,除v0=vl)各異,則稱為初級通路或路徑(初級回路或圈).長度為奇數(shù)的圈稱作奇圈,長度為偶數(shù)的圈稱作偶圈若通路(回路)中所有邊各異,則稱為簡單通路(簡單回路),否則稱為復雜通路(復雜回路)3第三頁，共二十八頁，編輯于2023年，星期日說明(1)表示方法①按定義用頂點和邊的交替序列,=v0e1v1e2…elvl②用邊序列,=e1e2…el③簡單圖中,用頂點序列,=v0v1…vl(2)在無向圖中,長度為1的圈由環(huán)構成.長度為2的圈由兩條平行邊構成.在無向簡單圖中,所有圈的長度3.在有向圖中,長度為1的圈由環(huán)構成.在有向簡單圖中,所有圈的長度2.4第四頁，共二十八頁，編輯于2023年，星期日說明(續(xù))(3)初級通路(回路)是簡單通路(回路),但反之不真初級通路非初級的簡單通路初級回路非初級的簡單回路5第五頁，共二十八頁，編輯于2023年，星期日通路與回路(續(xù))定理6.3

在n階圖中,若從頂點u到v(uv)存在通路,則從u到v存在長度小于等于n1的初級通路.證若通路中沒有相同的頂點(即初級通路),長度必n1.若有相同的頂點,刪去這兩個頂點之間的這一段,仍是u到v的通路.重復進行,直到?jīng)]有相同的頂點為止.定理6.4

在n階圖中,若存在v到自身的簡單回路,則一定存在v到自身長度小于等于n的初級回路.6第六頁，共二十八頁，編輯于2023年，星期日無向圖的連通性與連通分支設無向圖G=<V,E>,u,vVu與v連通:若u與v之間有通路.規(guī)定u與自身總是連通的.連通圖:任意兩點都連通的圖.平凡圖是連通圖連通關系R={<u,v>|u,v

V且u與v連通}.R是等價關系連通分支:V關于R的等價類的導出子圖設V/R={V1,V2,…,Vk},G的連通分支為G[V1],G[V2],…,G[Vk]連通分支數(shù)p(G)=kG是連通圖

p(G)=17第七頁，共二十八頁，編輯于2023年，星期日短程線與距離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(u,v)+d(v,w)d(u,w)例如a與e之間的短程線:ace,afe.d(a,e)=2,d(a,h)=abcdefghi8第八頁，共二十八頁，編輯于2023年，星期日點割集與邊割集設無向圖G=<V,E>,vV,eE,VV,EE.記Gv:從G中刪除v及關聯(lián)的邊GV:從G中刪除V中所有的頂點及關聯(lián)的邊Ge:從G中刪除eGE:從G中刪除E中所有邊定義6.15

設無向圖G=<V,E>,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為割邊或橋.9第九頁，共二十八頁，編輯于2023年，星期日實例說明：Kn無點割集n階零圖既無點割集，也無邊割集.若G連通，E為邊割集，則p(GE)=2若G連通，V為點割集，則p(GV)2abcdefge1e2e3e4e5e6e7e8e9e,f點割集:{e},{f},割點:{c,d}

橋:e8,e9邊割集:{e8},{e9},{e1,e2},{e1,e3,e6},{e1,e3,e4,e7}10第十頁，共二十八頁，編輯于2023年，星期日點連通度與邊連通度定義6.16

設無向連通圖G=<V,E>,(G)=min{|V||V是G的點割集或使G-V成為平凡圖}

稱為G的點連通度

(G)=min{|E||E是G的邊割集}稱為G的邊連通度例如3(G)=3(G)=11第十一頁，共二十八頁，編輯于2023年，星期日點連通度與邊連通度(續(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ī)定非連通圖的點連通度和邊連通度均為0定理6.5

對任何無向圖G,有

(G)(G)(G)12第十二頁，共二十八頁，編輯于2023年，星期日有向圖的連通性及其分類設有向圖D=<V,E>,u,vV,u可達v:u到v有通路.規(guī)定u到自身總是可達的.u與v相互可達:u可達v且v可達uD弱連通(連通):略去各邊的方向所得無向圖為連通圖D單向連通:u,vV，u可達v

或v可達u

D強連通:u,vV，u與v相互可達D是強連通的當且僅當D中存在經(jīng)過所有頂點的回路D是單向連通的當且僅當D中存在經(jīng)過所有頂點的通路13第十三頁，共二十八頁，編輯于2023年，星期日實例

強連通單連通弱連通14第十四頁，共二十八頁，編輯于2023年，星期日有向圖中的短程線與距離u到v的短程線:u到v長度最短的通路(設u可達v)距離d<u,v>:u到v的短程線的長度若u不可達v,規(guī)定d<u,v>=∞.性質：

d<u,v>0,且d<u,v>=0

u=vd<u,v>+d<v,w>d<u,w>

注意:沒有對稱性15第十五頁，共二十八頁，編輯于2023年，星期日6.3

圖的矩陣表示6.3.1無向圖的關聯(lián)矩陣6.3.2有向無環(huán)圖的關聯(lián)矩陣6.3.3有向圖的鄰接矩陣有向圖中的通路數(shù)與回路數(shù)6.3.4有向圖的可達矩陣16第十六頁，共二十八頁，編輯于2023年，星期日無向圖的關聯(lián)矩陣設無向圖G=<V,E>,V={v1,v2,…,vn},E={e1,e2,…,em}.

令mij為vi與ej的關聯(lián)次數(shù),稱(mij)nm為G的關聯(lián)矩陣,記為M(G).mij的可能取值為:0,1,2例如e1e2e3e4e5e6v5v1v2v3v4M(G)=21100001011100001100000000110017第十七頁，共二十八頁，編輯于2023年，星期日關聯(lián)矩陣的性質(6)ej是環(huán)第j列的一個元素為2,其余為0(5)vi是孤立點第i行全為018第十八頁，共二十八頁，編輯于2023年，星期日無環(huán)有向圖的關聯(lián)矩陣則稱(mij)nm為D的關聯(lián)矩陣,記為M(D).設無環(huán)有向圖D=<V,E>,V={v1,v2,…,vn},E={e1,e2,…,em}.令(3)ej與ek是平行邊第j列與第k列相同(2)第i行1的個數(shù)等于d+(v),第i行-1的個數(shù)等于d-(v)性質:(1)每列恰好有一個1和一個-119第十九頁，共二十八頁，編輯于2023年，星期日實例v1v2v3v4e2e1e3e4e5e6e7M(D)=-11000–110-11000000-1-1-11-1100110020第二十頁，共二十八頁，編輯于2023年，星期日有向圖的鄰接矩陣設有向圖D=<V,E>,V={v1,v2,…,vn},E={e1,e2,…,em},令為頂點vi鄰接到頂點vj邊的條數(shù)，稱()mn為D的鄰接矩陣,記作A(D),簡記作A.21第二十一頁，共二十八頁，編輯于2023年，星期日實例A=1100001010001020v1v2v3v422第二十二頁，共二十八頁，編輯于2023年，星期日有向圖中的通路數(shù)與回路數(shù)定理6.6設A為n階有向圖D的鄰接矩陣,則Al(l1)中元素等于D中vi到vj長度為l的通路(含回路)數(shù),等于vi到自身長度為l的回路數(shù),等于D中長度為l的通路(含回路)總數(shù),等于D中長度為l的回路總數(shù).23第二十三頁，共二十八頁，編輯于2023年，星期日有向圖中的通路數(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ù).24第二十四頁，共二十八頁，編輯于2023年，星期日實例(續(xù))

說明:在這里,通路和回路數(shù)是定義意義下的A=1100001010001020A2=1110100011003100A3=2110110011003310A4=3210110021104310v1到v2長為3的通路有1條v1到v3長為3的通路有1條v1到自身長為3的回路有2條D中長為3的通路共有15條,其中回路3條v1v2v3v425第二十五頁，共二十八頁，編輯于2023年，星期日有向圖的可達矩陣性質:P(D)主對角線上的元素全為1.D強連通當且僅當P(D)的元素全為1.設有向圖D=<V,E>,V={v1,v2,…,vn},令

稱(pij)nn為D的可達矩陣,記作P(D),