離散數(shù)學-耿素云PPT(第5版)5.4

15.4

最短路徑,關(guān)鍵路徑與著色帶權(quán)圖最短路徑與Dijkstra標號法項目網(wǎng)絡圖與關(guān)鍵路徑著色問題2最短路徑帶權(quán)圖G=<V,E,w>,其中w:ER.

e

E,w(e)稱作e的權(quán).e=(vi,vj),記w(e)=wij.若vi,vj不相鄰,記wij=.通路L的權(quán):L的所有邊的權(quán)之和,記作w(L).u和v之間的最短路徑:u和v之間權(quán)最小的通路.例

L1=v0v1v3v5,w(L1)=10,L2=v0v1v4v5,w(L2)=12,L3=v0v2v4v5,w(L3)=11.3標號法(E.W.Dijkstra,1959)設帶權(quán)圖G=<V,E,w>,其中

e

E,w(e)0.設V={v1,v2,,vn},求v1到其余各頂點的最短路徑1.令l1

0,p1

,lj

+

,pj

,j=2,3,

,n,P={v1},T=V-{v1},k

1,t

1./

表示空2.對所有的vj

T且(vk,vj)

E

令l

min{lj,lk+wkj},

若l=lk+wkj,則令lj

l,pj

vk.3.求li=min{lj|vj

Tt}.

令P

P

{vi},T

T-{vi},k

i.4.令t

t+1,

若t<n,則轉(zhuǎn)2.4Dijkstra標號法實例例

求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到v5的最短路徑:v0v1v2v4v3v5,d(v0,v5)=95項目網(wǎng)絡圖項目網(wǎng)絡圖:表示項目的活動之間前后順序一致的帶權(quán)有向圖.邊表示活動,邊的權(quán)是活動的完成時間,頂點表示事項(項目的開始和結(jié)束、活動的開始和結(jié)束).要求:(1)有一個始點(入度為0)和一個終點(出度為0).(2)任意兩點之間只能有一條邊.(3)沒有回路.

(4)每一條邊始點的編號小于終點的編號.A引入虛活動ABBCC例6

活動ABCDEFGHIJKL緊前活動

AAA,BA,BA,BC,HD,FE,IG,K時間(天)12343442461141235678ABCDEFGHIJKL1234344246117關(guān)鍵路徑關(guān)鍵路徑:項目網(wǎng)絡圖中從始點到終點的最長路徑關(guān)鍵活動:關(guān)鍵路徑上的活動設D=<V,E,W>,V={1,2,,n},1是始點,n是終點.(1)事項i的最早完成時間ES(vi):i最早可能開始的時間,即從始點到i的最長路徑的長度.

ES(1)=0ES(i)=max{ES(j)+wji|<j,i>

E},i=2,3,,n(2)事項i的最晚完成時間LF(i):在不影響項目工期的條件下,事項i最晚必須完成的時間.LF(n)=ES(n)LF(i)=min{LF(j)-wij|<i,j>

E},i=n-1,n-2,,18關(guān)鍵路徑(續(xù))(3)活動<i,j>的最早開始時間ES(i,j):<i,j>最早可能開始時間.(4)活動<i,j>的最早完成時間EF(i,j):<i,j>最早可能完成時間.(5)活動<i,j>的最晚開始時間ES(i,j):在不影響項目工期的條件下,<i,j>最晚必須開始的時間.(6)活動<i,j>的最晚完成時間ES(i,j):在不影響項目工期的條件下,<i,j>最晚必須完成的時間.(7)活動<i,j>的緩沖時間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,

LF(i,j)=LF(j),LS(i,j)=LF(j)-wij,9事項的最早開始時間

TE(1)=0TE(2)=max{0+1}=1TE(3)=max{0+2,1+0}=2TE(4)=max{0+3,2+2}=4TE(5)=max{1+3,4+4}=8TE(6)=max{2+4,8+1}=9TE(7)=max{1+4,2+4}=6TE(8)=max{9+1,6+6}=12例(續(xù))10事項的最晚完成時間

TL(8)=12TL(7)=min{12-6}=6TL(6)=min{12-1}=11TL(5)=min{11-1}=10TL(4)=min{10-4}=6TL(3)=min{6-2,11-4,6-4}=2TL(2)=min{2-0,10-3,6-4}=2TL(1)=min{2-1,2-2,6-3}=0例(續(xù))11總工期:12天關(guān)鍵路徑:v1v3v7v8關(guān)鍵活動:B,F,J例(續(xù))著色定義

設無向圖G無環(huán),對G的每個頂點涂一種顏色，使相鄰的頂點涂不同的顏色，稱為圖G的一種點著色,簡稱著色．若能用k種顏色給G的頂點著色，則稱G是k-可著色的．圖的著色問題:用盡可能少的顏色給圖著色.12例121222111111222322221111311122234例例2131122221112123213321232314應用有n項工作,每項工作需要一天的時間完成.有些工作由于需要相同的人員或設備不能同時進行,問至少需要幾天才能完成所有的工作?計算機有k個寄存器,現(xiàn)正在編譯一個程序,要給每一個變量分配一個寄存器.如果兩個變量要在同一時刻使用,則不能把它們分配給同一個寄存器.如何給變量分配寄存器?無線交換設備的波長分配.有n臺設備和k個發(fā)射波長,要給每一臺設備分配一個波長.如果兩臺設備靠得太近,則不能給它們分配相同的波長,以防止干擾.如何分配波長?14例例3學生會下設6個委員會,第一委員會={張,李,王},第二委員會={李,趙,劉},第三委員會={