第10章 图
解 (1)利用公式TE(vi)?max{TE(vj)??ij}求得各结点的最早完成时间为：
vj?Pree(vi)TE(v1)＝0
TE(v2)＝max{0＋3}＝3 TE(v3)＝max{3＋0，0＋2}＝3 TE(v4)＝max{0＋4，3＋2}＝5 TE(v5)＝max{3＋4，3＋4}＝7 TE(v6)＝max{3＋4，7＋0}＝7 TE(v7)＝max{5＋5，7＋3}＝10 TE(v8)＝max{7＋3，10＋1}＝11 TE(v9)＝max{7＋6，11＋1}＝13
(2)利用公式TL(vi)?minvj?Succ(vi){TL(vj)??ij}求得各结点的最晚完成时间为：
TL(v9)＝13
TL(v8)＝min{13－1}＝12 TL(v7)＝min{12－1}＝11 TL(v6)＝min{12－3}＝9 TL(v5)＝min{13－6，9－0}＝7 TL(v4)＝min{11－5}＝6
TL(v3)＝min{9－4，6－2，7－4}＝3 TL(v2)＝min{7－4，3－0}＝3 TL(v1)＝min{3－3，3－2，6－4}＝0
(3)利用公式TL(vi)－TE(vi)求得各结点的缓冲时间为：
TS(v1)＝TS(v2)＝TS(v3)＝TS(v5)＝TS(v9)＝0 TS(v4)＝6－5＝1 TS(v6)＝9－7＝2 TS(v7)＝11－10＝1 TS(v8)＝12－11＝1
21
第10章 图
于是，所求关键路径为v1v2v5v9，v1v2v3v5v9。
22