復(fù)試2離散結(jié)構(gòu)

17.2通路、回路、圖的連通性

簡(jiǎn)單通(回)路,初級(jí)通(回)路,復(fù)雜通(回)路無向連通圖,連通分支弱連通圖,單向連通圖,強(qiáng)連通圖點(diǎn)割集與割點(diǎn)邊割集與割邊(橋)2通路與回路

定義給定圖G=<V,E>（無向或有向的），G中頂點(diǎn)與邊的交替序列=v0e1v1e2…elvl，(1)若i(1il),vi1,vi是ei的端點(diǎn)(對(duì)于有向圖,要求vi1是始點(diǎn),vi是終點(diǎn)),則稱為通路,v0是通路的起點(diǎn),vl是通路的終點(diǎn),l為通路的長(zhǎng)度.又若v0=vl，則稱為回路.(2)若通路(回路)中所有頂點(diǎn)(對(duì)于回路,除v0=vl)各異，則稱為初級(jí)通路(初級(jí)回路).初級(jí)通路又稱作路徑,初級(jí)回路又稱作圈.(3)若通路(回路)中所有邊各異,則稱為簡(jiǎn)單通路(簡(jiǎn)單回路),否則稱為復(fù)雜通路(復(fù)雜回路).3說明(1)初級(jí)通路(回路)是簡(jiǎn)單通路(回路),但反之不真初級(jí)通路非初級(jí)的簡(jiǎn)單通路初級(jí)回路非初級(jí)的簡(jiǎn)單回路4通路與回路(續(xù))說明:表示方法①用頂點(diǎn)和邊的交替序列(定義),如=v0e1v1e2…elvl②用邊的序列,如=e1e2…el③簡(jiǎn)單圖中,用頂點(diǎn)的序列,如=v0v1…vl④非簡(jiǎn)單圖中,可用混合表示法,如=v0v1e2v2e5v3v4v5環(huán)是長(zhǎng)度為1的圈,兩條平行邊構(gòu)成長(zhǎng)度為2的圈.在無向簡(jiǎn)單圖中,所有圈的長(zhǎng)度3;在有向簡(jiǎn)單圖中,所有圈的長(zhǎng)度2.5通路與回路(續(xù))在兩種意義下計(jì)算的圈個(gè)數(shù)①定義意義下在無向圖中,一個(gè)長(zhǎng)度為l(l3)的圈看作2l個(gè)不同的圈.如v0v1v2v0,v1v2v0v1

,v2v0v1v2,v0v2v1v0,v1v0v2v1

,v2v1v0v2看作6個(gè)不同的圈.

在有向圖中,一個(gè)長(zhǎng)度為l(l3)的圈看作l個(gè)不同的圈.②同構(gòu)意義下所有長(zhǎng)度相同的圈都是同構(gòu)的,因而是1個(gè)圈.6通路與回路(續(xù))定理在n階圖G中，若從頂點(diǎn)vi到vj（vivj）存在通路，則從vi到vj存在長(zhǎng)度小于等于n1的通路.推論在n階圖G中，若從頂點(diǎn)vi到vj（vivj）存在通路，則從vi到vj存在長(zhǎng)度小于等于n1的初級(jí)通路.定理在一個(gè)n階圖G中，若存在vi到自身的回路，則一定存在vi到自身長(zhǎng)度小于等于n的回路.推論在一個(gè)n階圖G中，若存在vi到自身的簡(jiǎn)單回路，則一定存在長(zhǎng)度小于等于n的初級(jí)回路.7無向圖的連通性設(shè)無向圖G=<V,E>,u與v連通:若u與v之間有通路.規(guī)定u與自身總連通.連通關(guān)系R={<u,v>|u,v

V且uv}是V上的等價(jià)關(guān)系連通圖:任意兩點(diǎn)都連通的圖.平凡圖是連通圖.連通分支:V關(guān)于連通關(guān)系R的等價(jià)類的導(dǎo)出子圖設(shè)V/R={V1,V2,…,Vk},G[V1],G[V2],…,G[Vk]是G的連通分支,其個(gè)數(shù)記作p(G)=k.G是連通圖

p(G)=18短程線與距離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)=∞abcdefghi9點(diǎn)割集

記Gv:從G中刪除v及關(guān)聯(lián)的邊

GV:從G中刪除V中所有的頂點(diǎn)及關(guān)聯(lián)的邊

Ge:從G中刪除e

GE:從G中刪除E中所有邊定義設(shè)無向圖G=<V,E>,VV,若p(GV)>p(G)且VV,p(GV)=p(G),則稱V為G的點(diǎn)割集.若{v}為點(diǎn)割集,則稱v為割點(diǎn).10點(diǎn)割集(續(xù))例{v1,v4},{v6}是點(diǎn)割集,v6是割點(diǎn).{v2,v5}是點(diǎn)割集嗎？11邊割集定義設(shè)無向圖G=<V,E>,EE,若p(GE)>p(G)且EE,p(GE)=p(G),則稱E為G的邊割集.若{e}為邊割集,則稱e為割邊或橋.在上一頁的圖中，{e1,e2}，{e1,e3,e5,e6}，{e8}等是邊割集，e8是橋，{e7,e9,e5,e6}是邊割集嗎？幾點(diǎn)說明：Kn無點(diǎn)割集n階零圖既無點(diǎn)割集，也無邊割集.若G連通，E為邊割集，則p(GE)=2若G連通，V為點(diǎn)割集，則p(GV)212有向圖的連通性

設(shè)有向圖D=<V,E>u可達(dá)v:u到v有通路.規(guī)定u到自身總是可達(dá)的.可達(dá)具有自反性和傳遞性D弱連通(連通):基圖為無向連通圖D單向連通:u,vV，u可達(dá)v

或v可達(dá)u

D強(qiáng)連通:u,vV，u與v相互可達(dá)強(qiáng)連通單向連通弱連通13有向圖的連通性(續(xù))

定理(強(qiáng)連通判別法)

D強(qiáng)連通當(dāng)且僅當(dāng)D中存在經(jīng)過每個(gè)頂點(diǎn)至少一次的回路定理(單向連通判別法)

D單向連通當(dāng)且僅當(dāng)D中存在經(jīng)過每個(gè)頂點(diǎn)至少一次的通路(1)(2)(3)例下圖(1)強(qiáng)連通,(2)單連通,(3)弱連通14有向圖的短程線與距離u到v的短程線:u到v長(zhǎng)度最短的通路(u可達(dá)v)u與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作業(yè)：P173:T7.16自由練習(xí):T7.17167.3圖的矩陣表示無向圖的關(guān)聯(lián)矩陣有向圖的關(guān)聯(lián)矩陣有向圖的鄰接矩陣有向圖的可達(dá)矩陣17無向圖的關(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)=21100001011100001100000000110018關(guān)聯(lián)矩陣的性質(zhì)(6)ej是環(huán)第j列的一個(gè)元素為2,其余為0(5)vi是孤立點(diǎn)第i行全為019無環(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ì):20實(shí)例v1v2v3v4e2e1e3e4e5e6e7M(D)=–

11000–110–11000000

–1

–1

–11–1100110

021有向圖的鄰接矩陣設(shè)有向圖D=<V,E>,V={v1,v2,…,vn},E={e1,e2,…,em},令為頂點(diǎn)vi鄰接到頂點(diǎn)vj邊的條數(shù)，稱()nn為D的鄰接矩陣,記作A(D),簡(jiǎn)記作A.22實(shí)例A=1100001010001020v1v2v3v423

D中的通路及回路數(shù)定理設(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ù).24D中的通路及回路數(shù)(續(xù))例有向圖D如圖所示,求A,A2,A3,A4,

并回答諸問題：(1)D中長(zhǎng)度為1,2,3,4的通路各有多少條？其中回路分別為多少條？(2)D中長(zhǎng)度小于或等于4的通路為多少條？其中有多少條回路？推論設(shè)Bl=A+A2+…+Al(l1),則Bl中元素為D中長(zhǎng)度小于或等于l的通路數(shù)，為D中長(zhǎng)度小于或等于l的回路數(shù).25例(續(xù))

長(zhǎng)度通路回路

合計(jì)50818121133141417326有向圖的可達(dá)矩陣性質(zhì):P(D)主對(duì)角線上的元素pii全為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),簡(jiǎn)記為P.27實(shí)例例6.11(1)v1到v4,v4到v1長(zhǎng)為3的通路各有多少條?(2)v1到自身長(zhǎng)為1,2,3,4的回路各有多少條?(3)長(zhǎng)為4的通路共有多少條?其中有多少條回路?(4)長(zhǎng)度小于等于