11.2路、回路、圖的連通性

路,通路,跡無向圖的連通性

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

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

定義給定圖G=<V,E>（無向或有向的），G中頂點與邊的交替序列=v0e1v1e2…elvl，(1)若i(1il),vi1,vi是ei的端點(對于有向圖,要求vi1是始點,vi是終點),則稱為路,v0是路的起點,vl是路的終點,l為路的長度.又若v0=vl，則稱為回路.(2)若路(回路)中所有頂點(對于回路,允許v0=vl)各異，則稱為通路(圈).

(3)若路(回路)中所有邊各異,則稱為跡(閉跡).路中不含重復頂點，則一定不含重復邊。通路一定是跡。按通暢性要求由高到低：通路>跡>路按可能的復雜或曲折程度由高到低：路>跡>通路路與回路試分別畫出：一條通路一條非通路的跡一條非跡的路從中直觀感受一下路、跡和通路對通暢程度的不同要求路與回路實例45路與回路(續(xù))說明:表示方法①用頂點和邊的交替序列(定義),如=v0e1v1e2…elvl②用邊的序列,如=e1e2…el③簡單圖中,用頂點的序列,如=v0v1…vl④非簡單圖中,可用混合表示法,如=v0v1e2v2e5v3v4v5環(huán)是長度為1的圈,兩條平行邊構成長度為2的圈.在無向簡單圖中,所有圈的長度3;在有向簡單圖中,所有圈的長度2.6路與回路(續(xù))在兩種意義下計算圈的個數(shù)①定義意義下在無向圖中,一個長度為l(l3)的圈看作2l個不同的圈.如v0v1v2v0,v1v2v0v1

,v2v0v1v2,v0v2v1v0,v1v0v2v1

,v2v1v0v2看作6個不同的圈.

在有向圖中,一個長度為l(l3)的圈看作l個不同的圈.②同構意義下所有長度相同的圈都是同構的,因而是1個圈.7路與回路(續(xù))定理在n階圖G中，若從頂點u到v（uv）存在通路，則從u到v存在長度小于等于n1的路.推論在n階圖G中，若從頂點u到v（uv）存在通路，則從u到v存在長度小于等于n1的通路.定理在一個n階圖G中，若存在v到自身的回路，則一定存在v到自身長度小于等于n的回路.推論在一個n階圖G中，若存在v到自身的回路，則存在v到自身長度小于等于n的圈.8無向圖的連通性設無向圖G=<V,E>,u與v連通:u與v間有路，記為uv.規(guī)定u與自身總連通.連通關系R={<u,v>|u,v

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

p(G)=1例9點割集

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

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

Ge:從G中刪除e

GE:從G中刪除E中所有邊定義設無向圖G=<V,E>,VV,若p(GV)>p(G)且VV,p(GV)=p(G),則稱V為G的點割集.若{v}為點割集,則稱v為割點.10點割集實例例{v1,v4},{v6}是點割集,v6是割點.{v2,v5}不是點割集11邊割集定義設無向圖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}不是邊割集說明：Kn無點割集n階零圖既無點割集，也無邊割集.若G連通，E為邊割集，則p(GE)=2若G連通，V為點割集，則p(GV)212有向圖的連通性

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

或v可達u

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

定理(強連通判別法)

D強連通當且僅當D中存在經過每個頂點至少一次的回路定理(單向連通判別法)

D單向連通當且僅當D中存在經過每個頂點至少一次的路例

強連通單向連通弱連通141.3

帶權圖、最短路徑、圖著色帶權圖與最短路徑圖著色問題15最短路徑帶權圖G=<V,E,w>,其中w:ER.eE,w(e)稱作e的權.若e=(vi,vj),記w(e)=wij.若vi,vj不相鄰,記wij=.路L的權:L的所有邊的權之和,記作w(L).u和v之間的最短路徑:u和v之間權最小的路.例

L1=v0v1v3v5,w(L1)=10,L2=v0v1v4v5,w(L2)=12,L3=v0v2v4v5,w(L3)=11.著色定義

設無向圖G無環(huán),對G的每個頂點涂一種顏色，使相鄰的頂點涂不同的顏色，稱為圖G的一種點著色,簡稱著色．若能用k種顏色給G的頂點著色，則稱G是k-可著色的．圖的著色問題:用盡可能少的顏色給圖著色.16例121222111111222322221111311122234例例2171122221112123213321232314例例3學生會下設6個委員會,第一委員會={張,李,王},第二委員會={李,趙,劉},第三委員會={張,劉,王},第四委員會={趙,劉,孫