離散數(shù)學(xué)課件：第5章 圖的基本概念3

1、15.4 最短路徑最短路徑,關(guān)鍵路徑與著色關(guān)鍵路徑與著色n帶權(quán)圖帶權(quán)圖n最短路徑與最短路徑與Dijkstra標(biāo)號(hào)法標(biāo)號(hào)法n項(xiàng)目網(wǎng)絡(luò)圖與關(guān)鍵路徑項(xiàng)目網(wǎng)絡(luò)圖與關(guān)鍵路徑n著色問(wèn)題著色問(wèn)題2最短路徑最短路徑帶權(quán)圖帶權(quán)圖G=, 其中其中w:ER. (權(quán)函數(shù)權(quán)函數(shù)) e E, w(e)稱(chēng)作稱(chēng)作e的的權(quán)權(quán). e=(vi,vj), 記記w(e)=wij . 若若vi,vj不不相鄰相鄰, 記記wij = . 通路通路L的的權(quán)權(quán): L的所有邊的權(quán)之和的所有邊的權(quán)之和, 記作記作w(L).u和和v之間的之間的最短路徑最短路徑: u和和v之間權(quán)最小的通路之間權(quán)最小的通路.例例 L1=v0v1v3v5, w(L1)=1

2、0, L2=v0v1v4v5, w(L2)=12, L3=v0v2v4v5, w(L3)=11.3標(biāo)號(hào)法標(biāo)號(hào)法(E.W.Dijkstra, 1959)設(shè)帶權(quán)圖設(shè)帶權(quán)圖G=, 其中其中 e E, w(e) 0.設(shè)設(shè)V=v1,v2,vn, 求求v1到其余各頂點(diǎn)的最短路徑到其余各頂點(diǎn)的最短路徑1.（初始步）初始步）令令 l10, p1 , lj+ , pj , j=2,3,n, P=v1, T=V-v1, k1, t1. / 表示空表示空 2.（更新長(zhǎng)度）（更新長(zhǎng)度）對(duì)對(duì)所有所有的的vj T且且(vk,vj) E 令令lminlj, lk+wkj, 若若l=lk+wkj, 則令則令ljl, pjvk

3、.3. 求求li=minlj| vj Tt.（當(dāng)前最短）（當(dāng)前最短） 令令PP vi, TT-vi, ki.4. 令令tt+1, 若若tn, 則轉(zhuǎn)則轉(zhuǎn)2.4Dijkstra標(biāo)號(hào)法實(shí)例標(biāo)號(hào)法實(shí)例例例 求求v0到到v5的最短路徑的最短路徑 t v0 v1 v2 v3 v4 v5 1 (0, ) (+ , ) (+ , ) (+ , ) (+ , ) (+ , ) 2 (1,v0) (4,v0) (+ , ) (+ , ) (+ , ) 3 (3,v1) (8,v1) (6,v1) (+ , ) 4 (8,v1) (4,v2) (+ , ) 5 (7,v4) (10,v4) 6 (9,v3)v0到到

4、v5的最短路徑的最短路徑: v0v1v2v4v3v5 , d(v0,v5)=9*5項(xiàng)目網(wǎng)絡(luò)圖項(xiàng)目網(wǎng)絡(luò)圖項(xiàng)目網(wǎng)絡(luò)圖項(xiàng)目網(wǎng)絡(luò)圖（AOE-網(wǎng)）網(wǎng)）:帶權(quán)有向帶權(quán)有向無(wú)環(huán)無(wú)環(huán)圖圖，表示表示項(xiàng)目項(xiàng)目活動(dòng)之間活動(dòng)之間前后順序一致前后順序一致. 邊表示活動(dòng)邊表示活動(dòng), 邊權(quán)是活動(dòng)邊權(quán)是活動(dòng)的完成時(shí)間的完成時(shí)間,頂點(diǎn)表頂點(diǎn)表示示事事件件(即即項(xiàng)目的開(kāi)始和結(jié)束、項(xiàng)目的開(kāi)始和結(jié)束、活動(dòng)的開(kāi)始和結(jié)束活動(dòng)的開(kāi)始和結(jié)束).要求要求: (1) 有一個(gè)始點(diǎn)有一個(gè)始點(diǎn)(入度為入度為0)和一個(gè)終點(diǎn)和一個(gè)終點(diǎn)(出度為出度為0). (2) 任兩點(diǎn)間只有一邊任兩點(diǎn)間只有一邊. (3) 沒(méi)有回路沒(méi)有回路. (4) 每邊始點(diǎn)的編號(hào)每邊始

5、點(diǎn)的編號(hào)小于小于終點(diǎn)的編號(hào)終點(diǎn)的編號(hào).A引入虛活動(dòng)引入虛活動(dòng)ABBCCX待研究的問(wèn)題是：待研究的問(wèn)題是：（1）項(xiàng)目完成至少要多少時(shí)間）項(xiàng)目完成至少要多少時(shí)間（2）影響項(xiàng)目進(jìn)度的關(guān)鍵活動(dòng)是哪些）影響項(xiàng)目進(jìn)度的關(guān)鍵活動(dòng)是哪些例子：6 活動(dòng)活動(dòng) A B C D E F G H I J K L -緊前活動(dòng)緊前活動(dòng) A A A,B A,B A,B C,H D,F E,I G,K J,L時(shí)間時(shí)間(天天) 1 2 3 4 3 4 4 2 4 6 1 1對(duì)應(yīng)頂點(diǎn)對(duì)應(yīng)頂點(diǎn) 41235678ABCDEFGHIJKL1234344246117關(guān)鍵路徑關(guān)鍵路徑關(guān)鍵路徑關(guān)鍵路徑: 項(xiàng)目網(wǎng)絡(luò)圖中從項(xiàng)目網(wǎng)絡(luò)圖中從始點(diǎn)到終點(diǎn)

6、的最長(zhǎng)路徑始點(diǎn)到終點(diǎn)的最長(zhǎng)路徑關(guān)鍵活動(dòng)關(guān)鍵活動(dòng): 關(guān)鍵路徑上的活動(dòng)關(guān)鍵路徑上的活動(dòng)設(shè)設(shè)D=, V=1,2,n, 1是始點(diǎn)是始點(diǎn), n是終點(diǎn)是終點(diǎn).(1)事件事件i 的最早發(fā)生時(shí)間的最早發(fā)生時(shí)間ES(vi): i最早能夠發(fā)生的時(shí)間最早能夠發(fā)生的時(shí)間,即從始點(diǎn)到即從始點(diǎn)到i的最長(zhǎng)路徑的長(zhǎng)度的最長(zhǎng)路徑的長(zhǎng)度. ES(1)=0 ES(i)=maxES(j)+wji| E, i=2,3,n(2)事件事件i的最晚發(fā)生時(shí)間的最晚發(fā)生時(shí)間LF(i): 在不影響項(xiàng)目工期的條在不影響項(xiàng)目工期的條件下件下, ,事事件件i最晚必須完成的時(shí)間最晚必須完成的時(shí)間. . LF(n)=ES(n) （終結(jié)事件的最早和最晚是一樣

7、的）（終結(jié)事件的最早和最晚是一樣的）LF(i)=minLF(j)-wij| E, i=n-1,n-2,18關(guān)鍵路徑關(guān)鍵路徑(續(xù)續(xù))(3) 活動(dòng)活動(dòng)的最早開(kāi)始時(shí)間的最早開(kāi)始時(shí)間ES(i,j): 可可以以開(kāi)始開(kāi)始的的最早時(shí)間最早時(shí)間.(4) 活動(dòng)活動(dòng)的最早完成時(shí)間的最早完成時(shí)間EF(i,j):完成完成的的最早可能時(shí)間最早可能時(shí)間.(5) 活動(dòng)活動(dòng)的最晚開(kāi)始時(shí)的最晚開(kāi)始時(shí)限限LS(i,j): 在不影響項(xiàng)目工期的條在不影響項(xiàng)目工期的條件下件下, 必須開(kāi)始的最晚時(shí)間必須開(kāi)始的最晚時(shí)間.(6) 活動(dòng)活動(dòng)的最晚完成時(shí)的最晚完成時(shí)限限LF(i,j): 在不影響項(xiàng)目工期的條在不影響項(xiàng)目工期的條件下件下, 必須完

8、成的最晚時(shí)間必須完成的最晚時(shí)間.(7) 活動(dòng)活動(dòng)的的機(jī)動(dòng)機(jī)動(dòng)時(shí)間時(shí)間SL(i,j): SL(i,j)= LS(i,j)-ES(i,j)=LF(i,j)-EF(i,j)顯然顯然, ES(i,j)= ES(i), EF(i,j)= ES(i)+wij, LS(i,j)=LF(j)-wij, LF(i,j)=LF(j), 9先求事件最早先求事件最早可發(fā)生時(shí)間可發(fā)生時(shí)間 ES(1)=0 (開(kāi)始事件開(kāi)始事件) ES(2)=max0+1=1 ES(3)=max0+2,1+0=2 ES(4)=max0+3,2+2=4 ES(5)=max1+3,4+4=8 ES(6)=max2+4,8+1=9 ES(7)=m

9、ax1+4,2+4=6 ES(8)=max9+1,6+6=12例例(續(xù)續(xù))41235678ABCDEFGHIJKL12343442461110再求事件最晚再求事件最晚發(fā)生時(shí)間發(fā)生時(shí)間 LF(8) = ES (8) = 12(結(jié)束事件結(jié)束事件) LF(7)=min12-6=6 LF (6)=min12-1=11 LF(5)=min11-1=10 LF(4)=min10-4=6 LF(3)=min6-2,11-4,6-4=2 LF(2)=min2-0,10-3,6-4=2 LF(1)=min2-1,2-2,6-3=0例例(續(xù)續(xù))41235678ABCDEFGHIJKL12343442461111總

10、工期總工期:12天天 關(guān)鍵路徑關(guān)鍵路徑: v1v3v7v8 關(guān)鍵活動(dòng)關(guān)鍵活動(dòng): B,F,J事件事件 1 2 3 4 5 6 7 8 ES 0 1 2 4 8 9 6 12 LF 0 2 2 6 10 11 6 12活動(dòng)活動(dòng) A B C D E F G H I J K L 1-2 1-3 1-4 2-7 2-5 3-7 3-6 3-4 4-5 7-8 5-6 6-8 ES 0 0 0 1 1 2 2 2 4 6 8 9 EF 1 2 3 5 4 6 6 4 8 12 9 10 LS 1 0 3 2 7 2 7 4 6 6 10 11 LF 2 2 6 6 10 6 11 6 10 12 11 1

11、2 SL 1 0 3 1 6 0 5 2 2 0 2 241235678ABCDEFGHIJKL123434424611著色著色定義定義 設(shè)無(wú)向圖設(shè)無(wú)向圖G無(wú)環(huán)無(wú)環(huán), 對(duì)對(duì)G的每個(gè)頂點(diǎn)涂一種顏色，的每個(gè)頂點(diǎn)涂一種顏色，使相鄰的頂點(diǎn)涂不同的顏色使相鄰的頂點(diǎn)涂不同的顏色，稱(chēng)為圖，稱(chēng)為圖G的一種的一種點(diǎn)點(diǎn)著著色色,簡(jiǎn)稱(chēng)簡(jiǎn)稱(chēng)著色著色若能若能僅僅用用k種顏色給種顏色給G著色，則著色，則稱(chēng)稱(chēng)G是是k-可著色可著色的的圖的著色問(wèn)題圖的著色問(wèn)題: 用盡可能少的顏色給圖著色用盡可能少的顏色給圖著色.12例例121222111111222322221111311122234例例例例2131122221112123

12、21332 12 3231 4圖著色的應(yīng)用圖著色的應(yīng)用n有有n項(xiàng)工作項(xiàng)工作, 每項(xiàng)工作需要一天的時(shí)間完成每項(xiàng)工作需要一天的時(shí)間完成. 有些工有些工作由于需要相同的人員或設(shè)備不能同時(shí)進(jìn)行作由于需要相同的人員或設(shè)備不能同時(shí)進(jìn)行, 問(wèn)至問(wèn)至少需要幾天才能完成所有的工作少需要幾天才能完成所有的工作? n計(jì)算機(jī)有計(jì)算機(jī)有k個(gè)寄存器個(gè)寄存器, 現(xiàn)正在編譯一個(gè)程序現(xiàn)正在編譯一個(gè)程序, 要給每要給每一個(gè)變量分配一個(gè)寄存器一個(gè)變量分配一個(gè)寄存器. 如果兩個(gè)變量要在同一如果兩個(gè)變量要在同一時(shí)刻使用時(shí)刻使用, 則不能把它們分配給同一個(gè)寄存器則不能把它們分配給同一個(gè)寄存器.如如何給變量分配寄存器何給變量分配寄存器?

13、n無(wú)線(xiàn)交換設(shè)備的波長(zhǎng)分配無(wú)線(xiàn)交換設(shè)備的波長(zhǎng)分配. 有有n臺(tái)設(shè)備和臺(tái)設(shè)備和k個(gè)發(fā)射波個(gè)發(fā)射波長(zhǎng)長(zhǎng), 要給每一臺(tái)設(shè)備分配一個(gè)波長(zhǎng)要給每一臺(tái)設(shè)備分配一個(gè)波長(zhǎng). 如果兩臺(tái)設(shè)備如果兩臺(tái)設(shè)備靠得太近靠得太近, 則不能給它們分配相同的波長(zhǎng)則不能給它們分配相同的波長(zhǎng), 以防止以防止干擾干擾. 如何分配波長(zhǎng)如何分配波長(zhǎng)?14例例例例3 學(xué)生會(huì)下設(shè)學(xué)生會(huì)下設(shè)6個(gè)委員會(huì)個(gè)委員會(huì), 第一委員會(huì)第一委員會(huì)=張張, 李李, 王王, 第二委第二委員會(huì)員會(huì)=李李, 趙趙, 劉劉, 第三委員會(huì)第三委員會(huì)=張張, 劉劉, 王王, 第四委員會(huì)第四委員會(huì)=趙趙, 劉劉, 孫孫, 第五委員會(huì)第五委員會(huì)=張張, 王王, 第六委員會(huì)第六委

14、員會(huì)=李李, 劉劉, 王王. 每個(gè)每個(gè)月每個(gè)委員會(huì)都要開(kāi)一次會(huì)月每個(gè)委員會(huì)都要開(kāi)一次會(huì), 為了確保每個(gè)人都能參加他所為了確保每個(gè)人都能參加他所在的委員會(huì)會(huì)議在的委員會(huì)會(huì)議, 這這6個(gè)會(huì)議至少要安排在幾個(gè)不同時(shí)間段個(gè)會(huì)議至少要安排在幾個(gè)不同時(shí)間段?15v6v5v4v3v2v1123412至少要至少要4個(gè)時(shí)段個(gè)時(shí)段(4-著色著色）第第1時(shí)段時(shí)段:一一,四四第第2時(shí)段時(shí)段:二二,五五第第3時(shí)段時(shí)段:三三第第4時(shí)段時(shí)段:六六課后習(xí)題課后習(xí)題 5.20 講解（講解（作圖作圖）16 活動(dòng)活動(dòng) A B C D E F G H I J K L M 緊前活動(dòng)緊前活動(dòng) A A,B A,B A,B C,G D,E,

15、F D,E D,E H,J I,L 時(shí)間時(shí)間(天天) 3 2 4 4 4 4 2 5 3 3 6 1 1對(duì)應(yīng)頂點(diǎn)對(duì)應(yīng)頂點(diǎn)-(K,M)41237658ABCDEFGHIJKL3244445236319M1(2)課后習(xí)題課后習(xí)題 5.20 講解講解 （計(jì)算求解計(jì)算求解）1741237658ABCDEFGHIJKL3244445236319M10,3,3,5,7,7,10,11,7119126330(0)(1)(0)(0)(2)(1)(1)(2)(1)(0)(1)(1)(1)按增序觀察頂?shù)陌丛鲂蛴^察頂?shù)娜肴脒?，邊?計(jì)算計(jì)算:始點(diǎn)始點(diǎn)ES+邊權(quán)，取邊權(quán)，取最大最大者者(2)按降序觀察頂?shù)陌唇敌蛴^察頂?shù)某龀鲞?，邊?計(jì)算計(jì)算:終點(diǎn)終點(diǎn)LS-邊權(quán)，取邊權(quán)，取最