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

簡單通(回)路,初級通(回)路,復雜通(回)路無向圖的連通性

無向連通圖,連通分支有向連通圖

弱連通圖,單向連通圖,強連通圖點割集與割點邊割集與割邊(橋)2通路與回路

定義給定圖G=<V,E>（無向或有向的），G中頂邊交替序列

=v0e1v1e2…elvl

(此處的下標代表頂邊在序列中的次序)(1)若

i(1

i

l),vi

1,vi是ei的端點(對于有向圖,要求vi

1是始點,vi是終點),則稱

為通路,v0是通路的起點,vl是通路的終點,l為通路的長度.又若v0=vl，則稱

為回路.(2)若通路(回路)中無重復邊,則稱為簡單通路(簡單回路),否則稱為復雜通路(復雜回路).(3)若簡單通路(回路)中無重復頂(對于回路,除v0=vl)

，則稱為初級通路(初級回路).初級通路又稱作路徑,初級回路又稱作圈.通路與回路實例34通路與回路(續)通（回）路的多種表示法①用頂邊交替序列(定義),如

=v0e1v1e2…elvl②僅用邊序列,如

=e1e2…el③

簡單圖中,可用頂序列,如

=v0v1…vl④非簡單圖中,可用混合表示法,如

=v0v1e2v2e5v3v4v5環是長度為1的圈,兩條平行邊構成長度為2的圈.在無向簡單圖中,所有圈的長度

3;在有向簡單圖中,所有圈的長度

2.5通路與回路(續)兩種意義下，圈的計數問題①定義意義下

無向圖中,一個長度為l(l

3)的圈看作2l個不同的圈.如v0v1v2v0,v1v2v0v1

,v2v0v1v2,v0v2v1v0,v1v0v2v1

,v2v1v0v2看作6個不同的圈.

有向圖中,一個長度為l(l

3)的圈看作l個不同的圈.②同構意義下

長度相同的圈都是同構的,因而只計1個圈.6通路與回路(續)定理在n階圖G中，若從頂點u到v（u

v）存在通路，則從u到v存在長度小于等于n

1的通路.推論在n階圖G中，若從頂點u到v（u

v）存在通路，則從u到v存在長度小于等于n

1的初級通路.定理在一個n階圖G中，若存在v到自身的回路，則一定存在v到自身長度小于等于n的回路.推論在一個n階圖G中，若存在v到自身的簡單回路，則存在v到自身長度小于等于n的初級回路.7無向圖的連通性設無向圖G=<V,E>,u與v連通:u,v間有通路.規定u與自身總連通.連通關系R={<u,v>|u,v

V且u與v聯通}是V上的等價關系連通圖:任意兩頂都連通的圖.平凡圖是連通圖.G的連通分支:G關于連通關系R等價類的導出子圖設V/R={V1,V2,…,Vk},G[V1],G[V2],…,G[Vk]是G的連通分支,其個數記作p(G)=k.G是連通圖當且僅當

p(G)=1例8點割集

記G

v:從G中刪除頂v及v關聯的邊

G

V

:從G中刪除V

中所有頂及其關聯的邊

G

e

:從G中刪除邊e

G

E

:從G中刪除E

中所有邊定義設無向圖G=<V,E>,V

V,若p(G

V

)>p(G)且

V

V

,p(G

V

)=p(G),則稱V

為G的點割集.若單元集{v}已為點割集,則稱v為割點.9點割集實例例{v1,v4},{v6}是點割集,v6是割點.{v2,v5}不是點割集10邊割集定義設無向圖G=<V,E>,E

E,若p(G

E

)>p(G)且

E

E

,p(G

E

)=p(G),則稱E

為G的邊割集.若單元集{e}為邊割集,則稱e為割邊或橋.在前例中，{e1,e2}，{e1,e3,e5,e6}，{e8}等是邊割集，e8是橋，{e7,e9,e5,e6}不是邊割集一些重要事實Kn無點割集n階零圖既無點割集，也無邊割集.若G連通，E

為邊割集，則p(G

E

)=2若G連通，V

為點割集，則p(G

V

)

211有向圖的連通性

設有向圖D=<V,E>u可達v:由u到v有通路.規定u到自身總是可達的.可達關系一定是自反和傳遞的（但不一定是對稱的）D弱連通:當基圖連通D單向連通:

u,v

V，u可達v

或v可達u

D強連通:

u,v

V，u與v相互可達強連通

單向連通

弱連通12有向圖的連通性(續)

定理(連通判別法則)

D強連通當且僅當D中存在途經所有頂的回路.D單向連通當且僅當D中存在途徑所有頂的通路.例

強連通單向連通弱連通135.3圖的矩陣表示無向圖的關聯矩陣有向圖的關聯矩陣有向圖的鄰接矩陣有向圖的可達矩陣14無向圖的關聯矩陣定義設無向圖G=<V,E>,V={v1,v2,…,vn},E={e1,e2,…,em},

令mij為vi與ej的關聯次數，稱(mij)n

m為G的關聯矩陣，記為M(G).例

M(G)=

15關聯矩陣的性質(1)每一列（代表邊）恰好有兩個1或一個216有向圖的關聯矩陣定義設無環有向圖D=<V,E>,V={v1,v2,…,vn},E={e1,e2,…,em},令

則稱(mij)n

m為D的關聯矩陣，記為M(D).性質(1)每一列恰好有一個1和一個-1(2)第i行1的個數等于d+(vi)，-1的個數等于d-(vi)(3)1的總個數等于-1的總個數,且都等于m(4)平行邊對應的列相同17例

M(D)=

18定義設有向圖D=<V,E>,V={v1,v2,…,vn},|E|=m,令

aij

為頂點vi鄰接到頂點vj邊的條數，稱(aij

)n

n為D的鄰接矩陣(必是方陣),記作A(D),簡記為A.性質有向圖的鄰接矩陣

有向圖的鄰接矩陣實例19定理設A為n階有向圖D的鄰接矩陣,則A的l次冪Al(l

1)中，元素

代表D中vi到vj長度為l的通路數，特別地代表vi到自身長度為l的回路數，代表D中長度為l的通路總數，代表D中長度為l的回路總數.20

D中的通路及回路數21D中的通路及回路數(續)例右圖有向圖D中(1)長度為1,2,3,4的通路各有多少條？其中回路分別為多少條？(2)長度小于等于4的通路為多少條？其中有多少條回路？推論設Bl=A+A2+…+Al(l

1),則Bl中元素為D中長度小于等于l的通路數，為D中長度小于等于l的回路數.22例(續)

合計

508181211331414173長度通路回路

23有向圖的可達矩陣

定義設D=<V,E>為有向圖,V={v1,v2,…,vn},令

稱(pij)n

n為D的可達矩陣,記作P(D),簡記為P.性質:

P(D)主對角線上的元素全為1.（頂點到自身可達）D強連通當且僅當P(D)的元素全為1.24有向圖的可達矩陣實例例<例題>1.若圖G僅有兩個奇度頂u、v,

則u與v必連通.【證】（反證法）

若u與v不連通，即u、v分屬兩個連通分支G1、G2

.但若如此，對于連通圖G1或G2而言，都只有1個奇度頂，違背握手定理推論。

因此u、v必連通252.設有2k階單圖G

，其中每個頂的度至少為k，則G連通。【證明】（反證法）

若G不連通，則必存在連通分支G1滿足|V(G1)|≤k，但單圖G1的最大度不可能超過k-1，這與已知