喬海燕_qhy_graph2道路與回路

1、1第二章 道路與回路2有向道路有向道路 有向圖G=(V, A) 中，一條有向道路指的是一個(gè)首尾相接的弧的有限非空序列 P = a1 a2 ak (k1) 其中 viV ( i =0. k ), ajA ( j =1.k ) 且 aj= ( 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 2.1 道路與回路道路與回路3簡(jiǎn)單道路簡(jiǎn)單道路 若對(duì)任意的ij有ai aj ，稱之為簡(jiǎn)單有向道簡(jiǎn)單有向道路路。(沒(méi)有重復(fù)邊的路徑)回路回路 若 v0 = vn ，稱之為封閉的。封閉的。

2、簡(jiǎn)單封閉有向道路（閉跡）稱為有向回路有向回路。初級(jí)道路初級(jí)道路若對(duì)任意的ij有 vi vj ，稱之為初級(jí)道路初級(jí)道路/基本道路基本道路。 圈圈若對(duì)任意的ij有vi vj 而例外地v0 = vn，稱之為初初級(jí)回路級(jí)回路/圈圈。無(wú)向圖具有完全類似的定義。 2.1 2.1 簡(jiǎn)單道路與圈簡(jiǎn)單道路與圈4容易證明：定理定理2-1（1）基本道路是簡(jiǎn)單道路；（2）如果存在u到v的道路，則存在u到v 的基本道路； (3) n階圖的基本道路長(zhǎng)度不超過(guò)n-1; (4) n階圖的圈的長(zhǎng)度不超過(guò)n. 2.1 基本道路基本道路5定理定理2-2 無(wú)向圖G=(V, E)，u, v V 且 uv。若 u,v 之間存在兩條不同的

3、路，則 G 中存在一條回路。證明證明 （構(gòu)造法）定理定理2-3 無(wú)向圖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)過(guò)的頂點(diǎn)是v0(=v)v1vn-1vn，則必存在0in使得vn=vi，否則, 因?yàn)関n的度是偶數(shù)，存在與vn鄰接另一個(gè)頂點(diǎn)u, 從而得到一條更長(zhǎng)的簡(jiǎn)單路徑。矛盾！2.1 2.1 道路與回路的關(guān)系道路與回路的關(guān)系6可達(dá)性可達(dá)性 對(duì)于有向圖G=(V, A)中，若從 vi 到 vj 存在一條路，則稱從 vi 到 vj 是可達(dá)的，或稱 vi 可達(dá) vj 。對(duì)無(wú)向圖 G=(V, E

4、)，結(jié)點(diǎn)間的可達(dá)性是對(duì)稱的。連通性連通性 對(duì)于無(wú)向圖G=(V, E)，任意兩點(diǎn)之間可達(dá)時(shí)，稱G為連通的（連通圖）。 G中的一個(gè)極大連通子圖稱為G的一個(gè)連通分支。一個(gè)圖總是由一些連通分支構(gòu)成的。 G的連通分支數(shù)，記為W(G)。2.2 2.2 連通性連通性7強(qiáng)連通性強(qiáng)連通性對(duì)于有向圖G=(V, A)，如果任意兩點(diǎn)之間相互可達(dá)，則稱G為強(qiáng)連通的.弱弱 連通性連通性對(duì)于有向圖G=(V, A), 若不考慮弧的方向后得到的無(wú)向圖是連通的，則稱有向圖G是弱連通的。2.2 2.2 有向圖的連通性有向圖的連通性8定理定理2-5 G=(V, E)，n=|V|，若對(duì)任意 u, v V 且 uv，都有：Deg(u)

5、+ 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) 00 其他 可求得G的道路矩陣 P。 算法復(fù)雜度 O(n4)2.2 2.2 道路矩陣道路矩陣12道路矩陣可以通過(guò)二值矩陣的邏輯運(yùn)算求得。定義定義 二值元素的邏輯運(yùn)算： 0 0=0，0 1=1 0=1，1 1=1 0 0=0，0 1=1 0=0，1 1=1定義定義 二值矩陣的邏輯運(yùn)算。設(shè)有矩陣A = (aij)，B = (bij)，矩陣元素

6、值域?yàn)?0,1，定義運(yùn)算：ijijikkjababijnijk=1(AB) =(AB) =()2.2 2.2 道路矩陣的計(jì)算道路矩陣的計(jì)算13定義定義 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 2.2 道路矩陣的計(jì)算道路矩陣的計(jì)算14Warshall算法算法 設(shè) A nn是圖G的鄰接矩陣，求G的道路矩陣P。1. P A2. for i=1 to n d

7、o3. for j=1 to n do4. for k=1 to n do5. pjk pjk (pji pik) 計(jì)算復(fù)雜度 O(n3)2.2 2.2 道路矩陣及道路矩陣及WarshallWarshall算法算法初始：pij表示有無(wú)長(zhǎng)度為1 的直達(dá)路徑第i次外層循環(huán)結(jié)束時(shí)：pjk表示有中間通過(guò)v1,v2,vi的路徑。15例例 圖G的鄰接矩陣A如右，使用Warshall算法求G的道路矩陣P。01000011A = 11011000解解 P A01000011P = 110110002.2 2.2 道路矩陣及道路矩陣及WarshallWarshall算法算法16(1) i =101000011P

8、 = 11011000 j =1,2,3,4 增量方向i =1 矩陣元素處理次序： p11， p12， p13， p14， p21， p22， p31， p41， ， p44，2.2 2.2 道路矩陣及道路矩陣及WarshallWarshall算法算法17 如： p11 = p11 (p1i pi1) = p11 (p11 p11) = 0 p12 = p12 (p1i pi2) = p12 (p11 p12) = 1 p13 = p13 (p1i pi3) = p13 (p11 p13) = 0 01000011P = 11011100 結(jié)果為2.2 2.2 道路矩陣及道路矩陣及Warsha

9、llWarshall算法算法182.2 圖上的搜索圖上的搜索可以使用搜索的方法判斷從一個(gè)頂點(diǎn)u到另一個(gè)頂點(diǎn)v是否有路徑。深度優(yōu)先DFS從頂點(diǎn)u出發(fā)檢查其后繼u1是否，如果不是，則從u1開(kāi)始進(jìn)行深度優(yōu)先搜索；如果沒(méi)有后繼,則回溯，直至找到或者沒(méi)有可搜索的頂點(diǎn)。192.2 圖上的搜索圖上的搜索廣度優(yōu)先BFS從u出發(fā)，首先檢查其所有的直接后繼是否等于；然后依次檢查這些后繼的直接后繼，直到找到或者沒(méi)有可遍歷頂點(diǎn)。練習(xí)：編寫一個(gè)使用深度優(yōu)先或者廣度優(yōu)先搜索判定兩個(gè)點(diǎn)之間是否有道路的程序。20Euler回路回路 若連通圖 G=(V, E) 中存在一條簡(jiǎn)單回路（無(wú)重復(fù)邊）經(jīng)過(guò)G的所有邊，則稱該回路為G中的一

10、條Euler回路。存在Euler回路的圖稱為Euler圖。定理定理2-6-1 設(shè)有連通圖G=(V, E)，則下述命題等價(jià)： (1) G是一個(gè)Euler圖； (2) G的每一個(gè)頂點(diǎn)的度是偶數(shù)；證明證明（見(jiàn)戴一奇教材 p16定理2.3.1）2.3 Euler 2.3 Euler 回路回路21注意定理中對(duì)圖的連通性的假定；Euler回路經(jīng)過(guò)圖的所有邊一次且僅僅一次。定理對(duì)非簡(jiǎn)單圖也成立；定理的證明過(guò)程給出了為一個(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圖，再刪除該邊即可

11、。2.3 Euler 2.3 Euler 回路回路22有向圖的有向圖的Euler回路回路 若有向連通圖 G=(V, A) 中存在一條簡(jiǎn)單有向回路經(jīng)過(guò)G的所有弧，則稱該回路為G中的一條Euler回路，稱該圖為Euler有向圖。定理定理2-6-2 設(shè)連通有向圖G=(V, A)，則下述命題等價(jià)： (1) G是一個(gè)Euler有向圖； (2) G的每一個(gè)頂點(diǎn)的入度等于出度；證明證明（略）2.3 Euler 2.3 Euler 回路回路23Hamilton路路 若連通圖 G=(V, E) 中存在一條初級(jí)道路（無(wú)重復(fù)頂點(diǎn)）經(jīng)過(guò)G中每個(gè)頂點(diǎn)一次，則稱該道路為G中的一條Hamilton路。存在Hamilton回

12、路（圈）的圖稱 為Hamilton圖。Hamilton路經(jīng)過(guò)圖的所有頂點(diǎn)一次且僅僅一次。引入記號(hào)：G =(V, E)，SV。從G中去除S中的頂點(diǎn)及其關(guān)聯(lián)邊得到的G的子圖記為GS。2.4 Hamilton 2.4 Hamilton 道路道路242.2. Hamilton 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è)鄰接邊包含在其中，故不可能有圈。25定理定理2-8 若G=(V, E)是一個(gè)Hamilton圖，SV且S，則

13、G的子圖GS的連通分支數(shù) W(GS) |S|證明證明 記G中H-回路為C，C中包含了G中所有頂點(diǎn)。 考察CS：每從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.2. Hamilton Hamilton 圖圖26例例 圖 G12345786令S=2,6，則W(GS)=3。而|S|=2，即W(GS)|S|故圖G不可能是Hamilton圖。134578圖圖 G-S2.2. Hamilton Hamilton 圖圖27例例 Petersen圖

14、。|V|=10，對(duì)任何SV，都有W(GS)S ，但Petersen圖不是Hamilton圖（留作習(xí)題）。Peterson 圖存在Hamilton道路。2.2. Hamilton Hamilton 圖圖刪除一個(gè)或者兩個(gè)頂點(diǎn)仍然連通，刪除三個(gè)頂點(diǎn)最多得到兩個(gè)連通分支，28例例 下圖不存在Hamilton圈。給圖的相鄰頂點(diǎn)標(biāo)以A，B，則Hamilton圈包含相同個(gè)數(shù)的A,B. 2.2. Hamilton Hamilton 圖圖29定理定理2-9 簡(jiǎn)單圖 G=(V, E)，n=|V|，若對(duì)任一對(duì)不相鄰頂點(diǎn) u, vV, uv，有deg(u) + deg(v) n1，則G中存在一條Hamilton路。證

15、明證明 (見(jiàn)戴一奇教材p18定理2.4.1)梗概: (1) G是連通的； (2) 如果v1,v2,vp是一條基本道路，pn, 則可以擴(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.2. Hamilton Hamilton 道路道路30推論推論 上述有 deg(u) + deg(v) n 時(shí)，G為Hamilton圖。證明證明 （見(jiàn)戴一奇教材p19推論2.4.1）假設(shè) v1,v2,vn 是Hamilton路，如果v

16、1與 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.2. Hamilton Hamilton 道路道路31 定理及其推論 給出了Hamilton圖成立的充分條件，可用于對(duì)Hamilton圖的肯定性判定。 Hamilton圖成立的充要條件尚未得到解決，是圖論求解的課題之一。2.2. Hamilton Hamilton 圖圖32旅行商問(wèn)題旅行商問(wèn)題 已知n個(gè)城市，任兩個(gè)城市之間都有無(wú)向路相通，求一條經(jīng)

17、過(guò)所有城市一次且僅僅一次，并且總路程最短的回路。在一個(gè)邊帶正權(quán)的n階無(wú)向完全圖中，存在不同的Hamilton回路。旅行商問(wèn)題在其中尋找一條最短的Hamilton回路。精確算法：分支與界法近似算法：最近鄰法；最近插入法；2.2. 旅行商問(wèn)題旅行商問(wèn)題33最近鄰法最近鄰法 設(shè)城市之間道路長(zhǎng)度符合三角不等式。算法算法 從v1出發(fā),找到其最近鄰城市vi2,再?gòu)膙i2出發(fā)vin, 將vin與v1連接得到H-回路。2.2. 旅行商問(wèn)題旅行商問(wèn)題123456123456508691978350966558798696886754916588787097586778668379547066vvvvvvvvvv

18、vv例例結(jié)果是： v1 v2 v5 v6 v3 v4 v1 回路長(zhǎng)度=407但是： v1 v2 v4 v6 v5 v3 v1 回路長(zhǎng)度=40434最近插入法最近插入法 先構(gòu)成一個(gè)初始旅行圈，再選擇與該圈最接近的城市擴(kuò)展。擴(kuò)展時(shí)可采用某種策略，如便宜算法，直至得到H-回路。2.2. 旅行商問(wèn)題旅行商問(wèn)題v1v1C1設(shè)v2是距C1最近的點(diǎn)C2v1v2設(shè)v3是距C2最近的點(diǎn)v1v2C3 v3設(shè)v3是距C2最近的點(diǎn)v1v2C2 v335如果w(v1,v4)-w(v1,v2) w(v3,v4)-w(v2,v3),則連接v1,v4, 否則,連接v3,v4.設(shè)v4是距C3 上v2最近的點(diǎn)v1v2C3 v3v

19、436網(wǎng)絡(luò)網(wǎng)絡(luò) 有向圖有向圖 G=(V, A) 中，給每條邊中，給每條邊 a= 賦予賦予一個(gè)非負(fù)實(shí)數(shù)權(quán)一個(gè)非負(fù)實(shí)數(shù)權(quán) wij ，得到一個(gè)有向網(wǎng)絡(luò)。，得到一個(gè)有向網(wǎng)絡(luò)。距離矩陣距離矩陣 對(duì)上述網(wǎng)絡(luò)，定義對(duì)上述網(wǎng)絡(luò)，定義 D=(dij)n n，n=|V| wij 當(dāng)當(dāng) A dij = 其它其它帶權(quán)路徑長(zhǎng)度帶權(quán)路徑長(zhǎng)度 對(duì)上述網(wǎng)絡(luò)，路徑對(duì)上述網(wǎng)絡(luò)，路徑 v1, v2 , ,vk 的帶權(quán)的帶權(quán)路徑長(zhǎng)度定義為路徑長(zhǎng)度定義為2.6 2.6 最短路徑最短路徑1,11ki iidw37兩點(diǎn)間的最短距離兩點(diǎn)間的最短距離 對(duì)上述網(wǎng)絡(luò)，結(jié)點(diǎn)對(duì)上述網(wǎng)絡(luò)，結(jié)點(diǎn)vi到到vj可達(dá)時(shí)，可達(dá)時(shí)， vi到到vj的所有路徑中具有最

20、小帶權(quán)路徑長(zhǎng)度者稱為的所有路徑中具有最小帶權(quán)路徑長(zhǎng)度者稱為vi到到vj的最短路徑，其帶權(quán)路徑長(zhǎng)度稱為的最短路徑，其帶權(quán)路徑長(zhǎng)度稱為vi到到vj的最短的最短距離。距離。引理引理 在有向網(wǎng)絡(luò)中，若路徑在有向網(wǎng)絡(luò)中，若路徑 v1, v2 , ,vk-1 ,vk是是v1到到vk的最短路，則的最短路，則路徑路徑 v1, v2 , ,vk-1 是是v1到到vk-1的最的最短路。短路。2.6 2.6 最短路徑最短路徑證明證明如果路徑 v1, v2 , ,vk-1 不是v1到vk-1的最短路，則v1, v2 , ,vk-1 ,vk不是v1到vk的最短路。382.6 Dijkstra 算法算法Dijkstra算

21、法基本思想: 如果v0至u的最短路經(jīng)經(jīng)過(guò)v1,那么v0到v1的路徑也是v0至v1的最短路經(jīng)。 按路徑長(zhǎng)度的遞增次序，逐步產(chǎn)生最短路徑. 設(shè)源點(diǎn)為v01.首先求出v0為源點(diǎn)長(zhǎng)度最短的一條最短路徑， 即具有最小權(quán)的邊;2.求出源點(diǎn)到各個(gè)頂點(diǎn)下一個(gè)最短路徑：設(shè)其終點(diǎn)是u，則v0到u的最短路徑或者是邊，或者由一條已求得的最短路徑（v0v)和邊構(gòu)成；3.重復(fù)2直到從頂點(diǎn)v0到其它各頂點(diǎn)的最短路徑全部求出為止392.6 Dijkstra 算法算法例：求例：求v0其他各點(diǎn)的最短路徑其他各點(diǎn)的最短路徑用用S表示已求出最短路徑的結(jié)點(diǎn)集表示已求出最短路徑的結(jié)點(diǎn)集初始狀態(tài)：初始狀態(tài)：S=v0v5v4v3v2v1v0

22、 100 6030101020 5 50第一條最短路徑：第一條最短路徑：( v0, v2)S = v0,v2求下一條最短路徑：求下一條最短路徑：先求先求v0到其他頂點(diǎn)到其他頂點(diǎn)vi的的只經(jīng)過(guò)只經(jīng)過(guò)S結(jié)點(diǎn)的路徑：結(jié)點(diǎn)的路徑：v0 -v1: v0-v3: (v0,v2,v3) 60v0-v4: (v0,v4) 30v0-v5: (v0,v5) 100第二條最短路徑：第二條最短路徑： (v0,v4) ， S = v0,v2, v4402.6 Dijkstra 算法算法v5v4v3v2v1v0 100 6030101020 5 50第一條最短路徑：第一條最短路徑：( v0, v2)S = v0,v2求

23、下一條最短路徑：求下一條最短路徑：先求先求v0到其他頂點(diǎn)到其他頂點(diǎn)vi的的只經(jīng)過(guò)只經(jīng)過(guò)S結(jié)點(diǎn)的路徑：結(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, v5412.6 Dijkstra 算法算法 用S表示當(dāng)前找

24、到最短路徑的終點(diǎn)集；Dj表示0 0 一般情況下，一般情況下，),(),(=0ikiSvvvWkDvvWMiniDk422.6 Dijkstra 算法算法1. 初始化S：S0=1;S1.n-1=0；2. 初始化D: Dj = W;3. 在D中選擇最小的路徑長(zhǎng)度Dk, 并將vk加入S；4. 修改數(shù)組D: Dj=minDj, Dk + W;5. 重復(fù)3，4 n-1次， 直至求得v0到所有頂點(diǎn)的最短路徑此外此外 , , 增設(shè)一個(gè)數(shù)組增設(shè)一個(gè)數(shù)組P P記錄記錄v0v0到各點(diǎn)的最短路徑：到各點(diǎn)的最短路徑：若若v v0 0，w w1 1, , ,w,wk k,v,v是是v v0 0到到v v的最短路徑，的最

25、短路徑， 則則PvPv=w=wk k, Pw, Pwk k=w=w(i-1)(i-1), , , Pw, Pw1 1=v=v0 0. .432.6 Dijkstra 算法算法 Dijkstra算法要求圖上的權(quán)是非負(fù)數(shù)，否則結(jié)果不正確； Dijkstra算法同樣適用于無(wú)向圖，此時(shí)一個(gè)無(wú)向邊次相當(dāng)于兩個(gè)有向邊。 習(xí)題 證明Dijkstra算法的正確性。44例例2.6 2.6 求單源點(diǎn)最短距離的求單源點(diǎn)最短距離的DijkstraDijkstra算法算法12345554025520402010202520102555vDvvvv 結(jié)果：結(jié)果：U = (0, 50 , 55 , 40 , 25) 計(jì)算復(fù)

26、雜度：計(jì)算復(fù)雜度：O(n2)45Dijkstra算法的證明對(duì)于任意結(jié)點(diǎn)v, 假如在將加入之前另外有一條更短的路徑，首先經(jīng)過(guò)，然后到達(dá)，那么在之前加入，矛盾。462.7 2.7 關(guān)鍵路徑關(guān)鍵路徑作業(yè)網(wǎng)絡(luò)作業(yè)網(wǎng)絡(luò) 一項(xiàng)工程通常包一項(xiàng)工程通常包括多個(gè)工序，這些工序括多個(gè)工序，這些工序間存在次序的約束：一間存在次序的約束：一個(gè)工序的開(kāi)始的前提是個(gè)工序的開(kāi)始的前提是某些工序已經(jīng)結(jié)束。每某些工序已經(jīng)結(jié)束。每個(gè)工序有預(yù)計(jì)的完成時(shí)個(gè)工序有預(yù)計(jì)的完成時(shí)間。間。1CS10132CS10213CS201 CS101CS10224CS302 CS20115CS305 CS30216CS405 CS3021編號(hào) 課程號(hào)

27、 先修課 時(shí)間472.7 AOV網(wǎng)網(wǎng)1CS10132CS10213CS201CS101CS10224CS302CS10215CS305CS201 CS30216CS405CS3021142365311211頂點(diǎn)表示活動(dòng)的圖(AOV網(wǎng))：工序用頂點(diǎn)表示，工序j在工序i之后開(kāi)始用有向邊表示，其權(quán)表示工序i所需的時(shí)間。482.7 AOV網(wǎng)網(wǎng)142365311211一個(gè)工程的兩個(gè)問(wèn)題：工程能否順利進(jìn)行，即可否找到工序的一個(gè)線性排列：v1,v2,v3,v4,v5,v6,使得如果是一條有向邊，那么ij.拓?fù)渑判騿?wèn)題。 估算工程完成所需要的最短時(shí)間。求關(guān)鍵路徑問(wèn)題。492.7 拓?fù)渑判蛲負(fù)渑判?423653

28、11211拓?fù)渑判?將一個(gè)n階有向圖G=(V,A)的所有頂點(diǎn)排列成一個(gè)線性序v1,v2,vn，使得如果A, 則ij.稱這樣的序列為的一個(gè)拓?fù)渑判?。例如，左圖的一個(gè)拓?fù)渑判蚴牵?,2,3,4,6,5502.7 拓?fù)渑判蛲負(fù)渑判蚨ɡ?若有向圖G=(V,A) 不存在有向回路，則存在拓?fù)渑判颉ＷC明設(shè)v0是出度為零的頂點(diǎn)，記G1=G-v0, 令v1是G1中出度為零的結(jié)點(diǎn)，由此反復(fù)，則序列v0,v1, vn是G的一個(gè)拓?fù)渑判颉?引理 若有向圖G=(V,A) 不存在有向回路，則存在入度為零和出度為零的結(jié)點(diǎn)。51AOV網(wǎng)絡(luò)網(wǎng)絡(luò) 有向連通網(wǎng)絡(luò)有向連通網(wǎng)絡(luò) G=(V, A)： 每一結(jié)點(diǎn)表示一個(gè)作業(yè)，有向邊每一結(jié)點(diǎn)

29、表示一個(gè)作業(yè)，有向邊表示作業(yè)表示作業(yè)vj必須在必須在vi完成之后開(kāi)始；完成之后開(kāi)始； 邊邊所帶的非負(fù)實(shí)數(shù)權(quán)為完成作業(yè)所帶的非負(fù)實(shí)數(shù)權(quán)為完成作業(yè)vi所需時(shí)間；所需時(shí)間； 作業(yè)開(kāi)始條件：該作業(yè)的所有前驅(qū)作業(yè)全部完成；作業(yè)開(kāi)始條件：該作業(yè)的所有前驅(qū)作業(yè)全部完成； 無(wú)回路假設(shè)無(wú)回路假設(shè) (DAG: Directed Acyclic Graph 有向無(wú)環(huán)圖有向無(wú)環(huán)圖)； 網(wǎng)絡(luò)中有且只有一點(diǎn)入度為網(wǎng)絡(luò)中有且只有一點(diǎn)入度為0，稱為源點(diǎn)，表示工程開(kāi)始；，稱為源點(diǎn)，表示工程開(kāi)始；有且只有一點(diǎn)出度為有且只有一點(diǎn)出度為0，稱為匯點(diǎn)，表示工程結(jié)束。，稱為匯點(diǎn)，表示工程結(jié)束。2.7 2.7 關(guān)鍵路徑關(guān)鍵路徑524.5 4.5 關(guān)鍵路徑關(guān)鍵路徑關(guān)鍵路徑關(guān)鍵路徑 AOV網(wǎng)絡(luò)網(wǎng)絡(luò)G=