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

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

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

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

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

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

p(G)=17第七頁，共二十八頁，編輯于2023年，星期日短程線與距離u與v之間的短程線:u與v之間長(zhǎng)度最短的通路(設(shè)u與v連通)u與v之間的距離d(u,v):u與v之間短程線的長(zhǎng)度若u與v不連通,規(guī)定d(u,v)=∞.性質(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)=abcdefghi8第八頁，共二十八頁，編輯于2023年，星期日點(diǎn)割集與邊割集設(shè)無向圖G=<V,E>,vV,eE,VV,EE.記Gv:從G中刪除v及關(guān)聯(lián)的邊GV:從G中刪除V中所有的頂點(diǎn)及關(guān)聯(lián)的邊Ge:從G中刪除eGE:從G中刪除E中所有邊定義6.15

設(shè)無向圖G=<V,E>,VV,若p(GV)>p(G)且VV,p(GV)=p(G),則稱V為G的點(diǎn)割集.若{v}為點(diǎn)割集,則稱v為割點(diǎn).設(shè)EE,若p(GE)>p(G)且EE,p(GE)=p(G),則稱E為G的邊割集.若{e}為邊割集,則稱e為割邊或橋.9第九頁，共二十八頁，編輯于2023年，星期日實(shí)例說明：Kn無點(diǎn)割集n階零圖既無點(diǎn)割集，也無邊割集.若G連通，E為邊割集，則p(GE)=2若G連通，V為點(diǎn)割集，則p(GV)2abcdefge1e2e3e4e5e6e7e8e9e,f點(diǎn)割集:{e},{f},割點(diǎn):{c,d}

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

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

稱為G的點(diǎn)連通度

(G)=min{|E||E是G的邊割集}稱為G的邊連通度例如3(G)=3(G)=11第十一頁，共二十八頁，編輯于2023年，星期日點(diǎn)連通度與邊連通度(續(xù))說明:(1)若G是平凡圖,則(G)=0,(G)=0.(2)若G是完全圖Kn,則(G)=n-1,(G)=n-1(3)若G中存在割點(diǎn),則(G)=1;若G中存在割邊,則(G)=1(4)規(guī)定非連通圖的點(diǎn)連通度和邊連通度均為0定理6.5

對(duì)任何無向圖G,有

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

或v可達(dá)u

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

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

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

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

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

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

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

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