喬海燕-qhy-graph2道路與回路

第二章道路與回路[有向道路]

有向圖G=(V,A)中，一條有向道路指的是一個(gè)首尾相接的弧的有限非空序列

P=

a1

a2

……

ak

(k1)

其中viV(i=0..k),ajA(j=1..k)

且aj=<vj1,vj>(j=1..k)

v0

和vk分別稱為P的起點(diǎn)和終點(diǎn)，k稱為P的長(zhǎng)度。在簡(jiǎn)單圖中，也可記作P=(v0，v1，v2，…，vk

)或

v0

v1

v2

……

vp

2.1道路與回路[簡(jiǎn)單道路]若對(duì)任意的ij有ai

aj

，稱之為簡(jiǎn)單有向道路。(沒有重復(fù)邊的路徑)[回路]若v0=vn

，稱之為封閉的。簡(jiǎn)單封閉有向道路（閉跡）稱為有向回路。[初級(jí)道路]若對(duì)任意的ij有vi

vj

，稱之為初級(jí)道路/基本道路。

[圈]若對(duì)任意的ij有vi

vj

而例外地v0=vn，稱之為初級(jí)回路/圈。無向圖具有完全類似的定義。

2.1簡(jiǎn)單道路與圈容易證明：[定理2-1]（1）基本道路是簡(jiǎn)單道路；（2）如果存在u到v的道路，則存在u到v的基本道路；

(3)n階圖的基本道路長(zhǎng)度不超過n-1;(4)n階圖的圈的長(zhǎng)度不超過n.2.1基本道路[定理2-2]

無向圖G=(V,E)，u,v

V且uv。若u,v

之間存在兩條不同的路，則G中存在一條回路。[證明]

（構(gòu)造法）[定理2-3]

無向圖G=(V,E)中每個(gè)頂點(diǎn)的度均為偶數(shù)，且至少有一個(gè)頂點(diǎn)不是孤立點(diǎn)，則

G中存在一條回路。

[證明]

（反證法）設(shè)v不是孤立點(diǎn)，從v出發(fā)的最長(zhǎng)簡(jiǎn)單路徑經(jīng)過的頂點(diǎn)是v0(=v)v1…vn-1vn，則必存在0i<n使得vn=vi，否則,因?yàn)関n的度是偶數(shù)，存在與vn鄰接另一個(gè)頂點(diǎn)u,從而得到一條更長(zhǎng)的簡(jiǎn)單路徑。矛盾！2.1道路與回路的關(guān)系[可達(dá)性]

對(duì)于有向圖G=(V,A)中，若從

vi

到vj

存在一條路，則稱從

vi

到vj

是可達(dá)的，或稱

vi

可達(dá)vj

。對(duì)無向圖G=(V,E)，結(jié)點(diǎn)間的可達(dá)性是對(duì)稱的。[連通性]

對(duì)于無向圖G=(V,E)，任意兩點(diǎn)之間可達(dá)時(shí)，稱G為連通的（連通圖）。

G中的一個(gè)極大連通子圖稱為G的一個(gè)連通分支。一個(gè)圖總是由一些連通分支構(gòu)成的。G的連通分支數(shù)，記為W(G)。2.2連通性[強(qiáng)連通性]對(duì)于有向圖G=(V,A)，如果任意兩點(diǎn)之間相互可達(dá)，則稱G為強(qiáng)連通的.[弱連通性]對(duì)于有向圖G=(V,A),若不考慮弧的方向后得到的無向圖是連通的，則稱有向圖G是弱連通的。2.2有向圖的連通性[定理2-5]

G=(V,E)，n=|V|，若對(duì)任意u,v

V且

uv，都有：Deg(u)+Deg(v)n1，則G連通。[證明](反證法)設(shè)G可分為不連通的兩部分G1=(V1,E1)和G2=(V2,E2)，選取

uV1,vV2

則Deg(u)<=|V1|-1，

Deg(v)<|V2|-1，

故Deg(u)+Deg(v)<=|V1|+|V2|-2=n-2，與Deg(u)+Deg(v)n1矛盾。注意：未加特別聲明時(shí)，我們討論的都是簡(jiǎn)單圖。2.2連通的判定[定理2-11]

設(shè)Ann是G的鄰接矩陣，則連接vi與vj（ij）的長(zhǎng)度為l的路徑的條數(shù)等于Al的第i行第j列的元素的數(shù)值。[證明]（數(shù)學(xué)歸納法：對(duì)l歸納）2.2圖的鄰接矩陣[道路矩陣]

對(duì)有向圖G=(V,R)，n=|V|，構(gòu)造矩陣P=(pij)nn，其中

pij

=1若vi

到vj可達(dá)0其他稱P為圖G的道路矩陣（或可達(dá)矩陣）。2.2道路矩陣及Warshall算法[算法]

求給定圖G的道路矩陣P

設(shè)A為G的鄰接矩陣，B=A+A2+A3+…+An1，由[定理2-11]，bij表示由vi至vj

，長(zhǎng)度為1或2或…或n1的路徑數(shù)目，即為由vi至vj的全部路徑總和。令

pij

=1若bij

>00其他可求得G的道路矩陣P。算法復(fù)雜度O(n4)2.2道路矩陣道路矩陣可以通過二值矩陣的邏輯運(yùn)算求得。[定義]

二值元素的邏輯運(yùn)算：

00=0，01=10=1，11=100=0，01=10=0，11=1[定義]

二值矩陣的邏輯運(yùn)算。設(shè)有矩陣A=(aij)，B=(bij)，矩陣元素值域?yàn)閧0,1}，定義運(yùn)算：2.2道路矩陣的計(jì)算[定義]

A(k)=A(k1)

A(k2)，A(1)=A注意A(k)與Ak

的區(qū)別[定理2-12]

設(shè)Ann是圖G的鄰接矩陣，若從vi

到vj存在長(zhǎng)度為l的路，則[A(l)]ij

=1，否則[A(l)]ij

=0。[證明]對(duì)l作歸納；或直接引用[定理2-11]。2.2道路矩陣的計(jì)算[Warshall算法]

設(shè)Ann是圖G的鄰接矩陣，求G的道路矩陣P。PAfori=1tondoforj=1tondofork=1tondo

pjk

pjk(pji

pik)計(jì)算復(fù)雜度O(n3)2.2道路矩陣及Warshall算法初始：pij表示有無長(zhǎng)度為1的直達(dá)路徑第i次外層循環(huán)結(jié)束時(shí)：pjk表示有中間通過{v1,v2,…,vi}的路徑。[例]

圖G的鄰接矩陣A如右，使用Warshall算法求G的道路矩陣P。[解]PA2.2道路矩陣及Warshall算法(1)i=1j

=1,2,3,4

增量方向i

=1矩陣元素處理次序：p11，

p12，

p13，

p14，

p21，

p22，

……

p31，……

p41，……，p44，2.2道路矩陣及Warshall算法如：p11

=p11(p1i

pi1)=p11(p11

p11)=0p12

=p12(p1i

pi2)=p12(p11

p12)=1p13

=p13(p1i

pi3)=p13(p11

p13)=0…………結(jié)果為2.2道路矩陣及Warshall算法2.2圖上的搜索可以使用搜索的方法判斷從一個(gè)頂點(diǎn)u到另一個(gè)頂點(diǎn)v是否有路徑。[深度優(yōu)先DFS]從頂點(diǎn)u出發(fā)檢查其后繼u1是否ｖ，如果不是，則從u1開始進(jìn)行深度優(yōu)先搜索；如果沒有后繼,則回溯，直至找到ｖ或者沒有可搜索的頂點(diǎn)。2.2圖上的搜索[廣度優(yōu)先BFS]從u出發(fā)，首先檢查其所有的直接后繼是否等于ｖ；然后依次檢查這些后繼的直接后繼，直到找到ｖ或者沒有可遍歷頂點(diǎn)。練習(xí)：編寫一個(gè)使用深度優(yōu)先或者廣度優(yōu)先搜索判定兩個(gè)點(diǎn)之間是否有道路的程序。[Euler回路]

若連通圖G=(V,E)中存在一條簡(jiǎn)單回路（無重復(fù)邊）經(jīng)過G的所有邊，則稱該回路為G中的一條Euler回路。存在Euler回路的圖稱為Euler圖。[定理2-6-1]

設(shè)有連通圖G=(V,E)，則下述命題等價(jià)：

(1)G是一個(gè)Euler圖；

(2)G的每一個(gè)頂點(diǎn)的度是偶數(shù)；[證明]（見戴一奇教材p16定理2.3.1）2.3Euler回路注意定理中對(duì)圖的連通性的假定；Euler回路經(jīng)過圖的所有邊一次且僅僅一次。定理對(duì)非簡(jiǎn)單圖也成立；定理的證明過程給出了為一個(gè)Euler圖構(gòu)造Euler回路的構(gòu)造算法。[定理2-7]

設(shè)連通圖G=(V,E)中恰有2個(gè)頂點(diǎn)度為奇數(shù)，則G存在Euler道路。[證明]連接兩個(gè)奇度數(shù)結(jié)點(diǎn)形成Euler圖，再刪除該邊即可。2.3Euler回路[有向圖的Euler回路]

若有向連通圖G=(V,A)中存在一條簡(jiǎn)單有向回路經(jīng)過G的所有弧，則稱該回路為G中的一條Euler回路，稱該圖為Euler有向圖。[定理2-6-2]

設(shè)連通有向圖G=(V,A)，則下述命題等價(jià)：

(1)G是一個(gè)Euler有向圖；

(2)G的每一個(gè)頂點(diǎn)的入度等于出度；[證明]（略）2.3Euler回路[Hamilton路]

若連通圖G=(V,E)中存在一條初級(jí)道路（無重復(fù)頂點(diǎn)）經(jīng)過G中每個(gè)頂點(diǎn)一次，則稱該道路為G中的一條Hamilton路。存在Hamilton回路（圈）的圖稱為Hamilton圖。Hamilton路經(jīng)過圖的所有頂點(diǎn)一次且僅僅一次。引入記號(hào)：G=(V,E)，SV。從G中去除S中的頂點(diǎn)及其關(guān)聯(lián)邊得到的G的子圖記為GS。2.4Hamilton道路2.４Hamilton圖構(gòu)造Hamilton圈的簡(jiǎn)單規(guī)則：Halmilton圈含n條邊；Halmilton圈正好包含每個(gè)結(jié)點(diǎn)的兩條關(guān)聯(lián)邊，其他邊可以刪除；左圖如有H圈，則必包含三個(gè)二度結(jié)點(diǎn)的鄰接邊，從而中心結(jié)點(diǎn)至少有三個(gè)鄰接邊包含在其中，故不可能有Ｈ圈。

[定理2-8]

若G=(V,E)是一個(gè)Hamilton圖，SV且S，則G的子圖GS的連通分支數(shù)

W(GS)|S|[證明]

記G中H-回路為C，C中包含了G中所有頂點(diǎn)?？疾霤S：每從C中去除屬于S的一個(gè)頂點(diǎn)，連通分支數(shù)至多增加1（第一次以及當(dāng)該頂點(diǎn)處于邊緣時(shí)操作不會(huì)增加連通分支數(shù)），故

W(CS)|S|

而G可視為向C中添加邊構(gòu)成，故W(GS)W(CS)

所以W(GS)|S|2.４Hamilton圖[例]

圖G12345786令S={2,6}，則W(GS)=3。而|S|=2，即W(GS)>|S|故圖G不可能是Hamilton圖。134578圖G-S2.４Hamilton圖[例]

Petersen圖。|V|=10，對(duì)任何SV，都有W(GS)S

，但Petersen圖不是Hamilton圖（留作習(xí)題）。Peterson圖存在Hamilton道路。2.４Hamilton圖刪除一個(gè)或者兩個(gè)頂點(diǎn)仍然連通，刪除三個(gè)頂點(diǎn)最多得到兩個(gè)連通分支，．．．[例]

下圖不存在Hamilton圈。給圖的相鄰頂點(diǎn)標(biāo)以A，B，則Hamilton圈包含相同個(gè)數(shù)的A,B.2.４Hamilton圖[定理2-9]

簡(jiǎn)單圖G=(V,E)，n=|V|，若對(duì)任一對(duì)不相鄰頂點(diǎn)u,vV,uv，有deg(u)+deg(v)n1，則G中存在一條Hamilton路。[證明](見戴一奇教材p18定理2.4.1)梗概:(1)G是連通的；

(2)如果v1,v2,…,vp是一條基本道路，p<n,則可以擴(kuò)展這條道路：(a)v1,vp存在{v1,…,vp}之外的鄰接點(diǎn)，可以立即擴(kuò)展；(b)v1,vp僅與{v1,…,vp}鄰接，則存在包含這些點(diǎn)的圈。

由連通性，存在圈外的結(jié)點(diǎn)與圈上某結(jié)點(diǎn)鄰接，所以，這樣的圈可以擴(kuò)展成更長(zhǎng)的基本道路，直至p=n.2.４Hamilton道路[推論]

上述有deg(u)+deg(v)n時(shí)，G為Hamilton圖。[證明]（見戴一奇教材p19推論2.4.1）假設(shè)v1,v2,…,vn

是Hamilton路，如果v1與vn

不鄰接，設(shè)v1的鄰接點(diǎn)集是{vi1,vi2,…,vik},則vn必與{vi1-1,vi2-1,…,vik-1}之一鄰接，否則deg(vn)<=n-1-k,deg(v1)=k,deg(v1)+deg(vn)<=n-1。矛盾！2.４Hamilton道路定理及其推論給出了Hamilton圖成立的充分條件，可用于對(duì)Hamilton圖的肯定性判定。Hamilton圖成立的充要條件尚未得到解決，是圖論求解的課題之一。2.４Hamilton圖[旅行商問題]

已知n個(gè)城市，任兩個(gè)城市之間都有無向路相通，求一條經(jīng)過所有城市一次且僅僅一次，并且總路程最短的回路。在一個(gè)邊帶正權(quán)的n階無向完全圖中，存在不同的Hamilton回路。旅行商問題在其中尋找一條最短的Hamilton回路。精確算法：分支與界法近似算法：最近鄰法；最近插入法；2.５旅行商問題[最近鄰法]

設(shè)城市之間道路長(zhǎng)度符合三角不等式。[算法]從v1出發(fā),找到其最近鄰城市vi2,再從vi2出發(fā)…vin,將vin與v1連接得到H-回路。2.５旅行商問題[例]結(jié)果是：

v1v2v5v6v3v4v1

回路長(zhǎng)度=407但是：

v1v2v4v6v5v3v1

回路長(zhǎng)度=404[最近插入法]

先構(gòu)成一個(gè)初始旅行圈，再選擇與該圈最接近的城市擴(kuò)展。擴(kuò)展時(shí)可采用某種策略，如便宜算法，直至得到H-回路。2.５旅行商問題v1v1C1設(shè)v2是距C1最近的點(diǎn)C2v1v2設(shè)v3是距C2最近的點(diǎn)v1v2C3v3設(shè)v3是距C2最近的點(diǎn)v1v2C2v3如果w(v1,v4)-w(v1,v2)<w(v3,v4)-w(v2,v3),則連接v1,v4,否則,連接v3,v4.設(shè)v4是距C3上v2最近的點(diǎn)v1v2C3v3v4[網(wǎng)絡(luò)]

有向圖G=(V,A)中，給每條邊a=<vi,vj>賦予一個(gè)非負(fù)實(shí)數(shù)權(quán)wij

，得到一個(gè)有向網(wǎng)絡(luò)。[距離矩陣]

對(duì)上述網(wǎng)絡(luò)，定義D=(dij)nn，n=|V|

wij

當(dāng)<vi,vj>A

dij=其它[帶權(quán)路徑長(zhǎng)度]

對(duì)上述網(wǎng)絡(luò)，路徑v1,v2,…,vk

的帶權(quán)路徑長(zhǎng)度定義為2.6最短路徑[兩點(diǎn)間的最短距離]

對(duì)上述網(wǎng)絡(luò)，結(jié)點(diǎn)vi到vj可達(dá)時(shí)，vi到vj的所有路徑中具有最小帶權(quán)路徑長(zhǎng)度者稱為vi到vj的最短路徑，其帶權(quán)路徑長(zhǎng)度稱為vi到vj的最短距離。[引理]

在有向網(wǎng)絡(luò)中，若路徑v1,v2,…,vk-1,vk是v1到vk的最短路，則路徑v1,v2,…,vk-1是v1到vk-1的最短路。2.6最短路徑[證明]

如果路徑v1,v2

,…,vk-1

不是v1到vk-1的最短路，則v1,v2,…,vk-1

,vk不是v1到vk的最短路。2.6Dijkstra

算法[Dijkstra算法基本思想]:如果v0至u的最短路經(jīng)經(jīng)過v1,那么v0到v1的路徑也是v0至v1的最短路經(jīng)。按路徑長(zhǎng)度的遞增次序，逐步產(chǎn)生最短路徑.

設(shè)源點(diǎn)為v0首先求出v0為源點(diǎn)長(zhǎng)度最短的一條最短路徑，即具有最小權(quán)的邊<v0,v>;求出源點(diǎn)到各個(gè)頂點(diǎn)下一個(gè)最短路徑：設(shè)其終點(diǎn)是u，則v0到u的最短路徑或者是邊<v0,u>，或者由一條已求得的最短路徑（v0…v)和邊<v,u>構(gòu)成；重復(fù)2直到從頂點(diǎn)v0到其它各頂點(diǎn)的最短路徑全部求出為止。2.6Dijkstra

算法例：求v0其他各點(diǎn)的最短路徑用S表示已求出最短路徑的結(jié)點(diǎn)集初始狀態(tài)：S={v0}v5v4v3v2v1v0

1006030101020

550第一條最短路徑：(v0,v2)S={v0,v2}求下一條最短路徑：先求v0到其他頂點(diǎn)vi的只經(jīng)過S結(jié)點(diǎn)的路徑：v0---v1:∞v0---v3:(v0,v2,v3)60v0---v4:(v0,v4)30v0---v5:(v0,v5)100第二條最短路徑：(v0,v4)

，S={v0,v2,v4}2.6Dijkstra

算法v5v4v3v2v1v0

1006030101020

550第一條最短路徑：(v0,v2)S={v0,v2}求下一條最短路徑：先求v0到其他頂點(diǎn)vi的只經(jīng)過S結(jié)點(diǎn)的路徑：v0---v1:∞v0---v3:(v0,v2,v3)60,(v0,v4,v3)50v0---v5:(v0,v5)100,(v0,v4,v5)90第二條最短路徑：

(v0,v4)

，S={v0,v2,v4}第三條最短路徑：(v0,v4,v3)

，S={v0,v2,v4,v3}第四條最短路徑：(v0,v4,v3,v5)

，S={v0,v2,v4,v3,v5}2.6Dijkstra

算法用S表示當(dāng)前找到最短路徑的終點(diǎn)集；引入一個(gè)輔助數(shù)組D,D[j]表示當(dāng)前找到的從源點(diǎn)v0到終點(diǎn)vi

的途徑S的最短路徑的長(zhǎng)度。初始狀態(tài)：S={v0}若從源點(diǎn)v0到頂點(diǎn)vi有邊，則D[i]為該邊上的權(quán)值；若從源點(diǎn)v0到頂點(diǎn)vi

沒有邊，則D[i]為+一般情況下，2.6Dijkstra

算法初始化S：S[0]=1;S[1..n-1]=0；初始化D:D[j]=W<v0,vj>;在D中選擇最小的路徑長(zhǎng)度D[k],并將vk加入S；修改數(shù)組D:D[j]=min{D[j],D[k]+W<vk,vj>};重復(fù)3，4n-1次，直至求得v0到所有頂點(diǎn)的最短路徑此外,增設(shè)一個(gè)數(shù)組P記錄v0到各點(diǎn)的最短路徑：若v0，w1,…,wk,v是v0到v的最短路徑，則P[v]=wk,P[wk]=w(i-1),…,P[w1]=v0.2.6Dijkstra

算法Dijkstra算法要求圖上的權(quán)是非負(fù)數(shù)，否則結(jié)果不正確；Dijkstra算法同樣適用于無向圖，此時(shí)一個(gè)無向邊次相當(dāng)于兩個(gè)有向邊。[習(xí)題]證明Dijkstra算法的正確性。[例]2.6求單源點(diǎn)最短距離的Dijkstra算法

結(jié)果：U=(0,50,55,40,25)計(jì)算復(fù)雜度：O(n2)［Dijkstra算法的證明］對(duì)于任意結(jié)點(diǎn)v,假如在將ｖ加入Ｓ之前另外有一條更短的路徑，首先經(jīng)過ｘ，然后到達(dá)ｖ，那么ｘ在ｖ之前加入Ｓ，矛盾。2.7關(guān)鍵路徑[作業(yè)網(wǎng)絡(luò)]一項(xiàng)工程通常包括多個(gè)工序，這些工序間存在次序的約束：一個(gè)工序的開始的前提是某些工序已經(jīng)結(jié)束。每個(gè)工序有預(yù)計(jì)的完成時(shí)間。1CS10132CS10213CS201CS101CS10224CS302CS20115CS305CS30216CS405CS3021編號(hào)課程號(hào)先修課時(shí)間2.7AOV網(wǎng)1CS10132CS10213CS201CS101CS10224CS302CS10215CS305CS201CS30216CS405CS3021142365311211頂點(diǎn)表示活動(dòng)的圖(AOV網(wǎng))：工序用頂點(diǎn)表示，工序j在工序i之后開始用有向邊<i,j>表示，其權(quán)表示工序i所需的時(shí)間。2.7AOV網(wǎng)142365311211一個(gè)工程的兩個(gè)問題：工程能否順利進(jìn)行，即可否找到工序的一個(gè)線性排列：v1,v2,v3,v4,v5,v6,使得如果<vi,vj>是一條有向邊，那么i<j.－拓?fù)渑判騿栴}。

估算工程完成所需要的最短時(shí)間。－求關(guān)鍵路徑問題。2.7拓?fù)渑判?42365311211[拓?fù)渑判騗將一個(gè)n階有向圖G=(V,A)的所有頂點(diǎn)排列成一個(gè)線性序v1,v2,…,vn，使得如果<vi,vj>A,則i<j.稱這樣的序列為Ｇ的一個(gè)拓?fù)渑判?。例如，左圖的一個(gè)拓?fù)渑判蚴牵?,2,3,4,6,52.7拓?fù)渑判騕定理]若有向圖G=(V,A)不存在有向回路，則Ｇ存在拓?fù)渑判?。[證明]設(shè)v0是出度為零的頂點(diǎn)，記G1=G-v0,令v1是G1中出度為零的結(jié)點(diǎn)，由此反復(fù)，則序列v0,v1,…,vn是G的一個(gè)拓?fù)渑判颉?/p>

[引理]若有向圖G=(V,A)不存在有向回路，則Ｇ存在入度為零和出度為零的結(jié)點(diǎn)。[AOV網(wǎng)絡(luò)]有向連通網(wǎng)絡(luò)G=(V,A)：①每一結(jié)點(diǎn)表示一個(gè)作業(yè)，有向邊<vi,vj>表示作業(yè)vj必須在vi完成之后開始；②邊<vi,vj>所帶的非負(fù)實(shí)數(shù)權(quán)為完成作業(yè)vi所需時(shí)間；③作業(yè)開始條件：該作業(yè)的所有前驅(qū)作業(yè)全部完成；④無回路假設(shè)(DAG:DirectedAcyclicGraph有向無環(huán)圖)