第五章圖(五)

1、第八講 圖（下）浙江大學(xué) 陳 越6.7 拓?fù)渑判蚶河嬎銠C(jī)專業(yè)排課課程號C1課程名稱程序設(shè)計基礎(chǔ)預(yù)修課程無C2C3離散數(shù)學(xué)數(shù)據(jù)結(jié)構(gòu)無C1, C2C1C3C7C12C4微積分（一）無C2C5C6C7C8C9微積分（二）線性代數(shù)算法分析與設(shè)計邏輯與計算機(jī)設(shè)計基礎(chǔ)計算機(jī)組成C4C5C3無C8C8C4C13C9C5C10C11C6C14C15C10C11操作系統(tǒng)編譯原理C7, C9C7, C9C12C13C14C15數(shù)據(jù)庫計算理論計算機(jī)網(wǎng)絡(luò)數(shù)值分析C7C2C10C6AOV (Activity On Vertex)網(wǎng)絡(luò)算法課程號課程名稱預(yù)修課程C1C2程序設(shè)計基礎(chǔ)離散數(shù)學(xué)無無C1C3C7C12C3數(shù)據(jù)結(jié)

2、構(gòu)C1, C2C2C4C5C6微積分（一）微積分（二）線性代數(shù)無C4C5C8C13C9C10C11C14C7算法分析與設(shè)計C3C8邏輯與計算機(jī)設(shè)計基礎(chǔ)無C4C5C6C15C9計算機(jī)組成C8C10C11C12C13操作系統(tǒng)編譯原理數(shù)據(jù)庫計算理論C7, C9C7, C9C7C2C1C3C7C2C13C6C8C9C4C5C14C15計算機(jī)網(wǎng)絡(luò)數(shù)值分析C10C6C11 C12 C10 C15C141.AOV網(wǎng)絡(luò) (Activity On Vertices) 可以用有向圖表示一個工程。在這種有向圖中，用頂點表示活動，用有向邊表示活動Vi 必須先于活動Vj 進(jìn)行。這種有向圖叫做頂點表示活動的AOV網(wǎng)絡(luò) (

3、Activity On Vertices)。 注：在AOV網(wǎng)絡(luò)中不能出現(xiàn)有向回路, 即有向環(huán)。如果出現(xiàn)了有向環(huán)，則意味著某項活動應(yīng)以自己作為先決條件。因此，對給定的AOV網(wǎng)絡(luò)，必須先判斷它是否存在有向環(huán)。檢測有向環(huán)的方法構(gòu)造AOV的拓?fù)湫蛄小?.拓?fù)渑判驑?gòu)造AOV網(wǎng)絡(luò)全部頂點的拓?fù)溆行蛐蛄械倪\算就叫做拓?fù)渑判颉Ｈ绻ㄟ^拓?fù)渑判蚰軐OV網(wǎng)絡(luò)的所有頂點都排入一個拓?fù)溆行虻男蛄兄? 則該網(wǎng)絡(luò)中必定不會出現(xiàn)有向環(huán)。例如, 對學(xué)生選課工程圖進(jìn)行拓?fù)渑判? 得到的拓?fù)溆行蛐蛄袨?C1 , C2 , C3 , C4 , C5 , C6 , C8 , C9 , C7或 C1 , C8 , C9 , C2 ,

4、 C5 , C3 , C4 , C7 , C6C8C3C5C4C9C6C7C1C23.進(jìn)行拓?fù)渑判虻姆椒?輸入AOV網(wǎng)絡(luò)。令 n 為頂點個數(shù)。 在AOV網(wǎng)絡(luò)中選一個沒有直接前驅(qū)的頂點, 并輸出之; 從圖中刪去該頂點, 同時刪去所有它發(fā)出的有向邊; 重復(fù)以上 、步, 直到n 全部頂點均已輸出，拓?fù)溆行蛐蛄行纬桑負(fù)渑判蛲瓿?；或n 圖中還有未輸出的頂點, 但已跳出處理循環(huán)。說明圖中還剩下一些頂點, 它們都有直接前驅(qū)。這時網(wǎng)絡(luò)中必存在有向環(huán)。nnnV拓?fù)渑判蛲負(fù)湫颍喝绻麍D中從V到W有一條有向路徑，則V一定排在W之前。滿足此條件的頂點序列稱為一個拓?fù)湫颢@得一個拓?fù)湫虻倪^程就是拓?fù)渑判駻OV如果有合理的

5、拓?fù)湫?，則必定是有向無環(huán)如果有合理的拓?fù)湫?，則必定是有向無環(huán)圖（Directed Acyclic Graph, DAG）V必須在必須在V開始開始之前結(jié)束 可以用一個隊列來實現(xiàn)這個特定存儲，開始時將所有入度為0的頂點插入隊列，當(dāng)隊列不為空時，取出一個頂點V并輸出，然后將與V相鄰的頂點入度減1.當(dāng)產(chǎn)生新的入度為0的頂點時，將其插入隊列。重復(fù)這一過程直到隊列為空時算法終止。所要尋找的拓?fù)渑判蚣礊楦黜旤c從隊列取出的序列。V1V2V4V5V3V6V7V8V1V4頂點1、4入隊V2V4V5V3V6V7V8V1V4頂點1出隊，頂點2入隊V2V2V5V3V6V7V8V1V4頂點4出隊，頂點5入隊V2V5V5V

6、3V6V7V8V1V4頂點2出隊V2V5V3V6V7V8V1V4頂點5出隊，頂點3、6入隊V2V5V3V6V6V7V8V1V4頂點3出隊V2V5V3V6V7V8V1V4頂點6出隊，頂點7入隊V2V5V3V6V7V8V1V4頂點7出隊，頂點8入隊V2V5V3V6V7V8V1V4頂點8出隊V2V5V3V6V7V8表 拓?fù)渑判蜻^程列表頂點頂點入度變化（1：初始8：結(jié)束）12345678V100000000V210000000V332210000V400000000V511000000V611110000V722222100V822222110入隊列V1V4V2V5V3V6V7V8出隊列V1V4V2V

7、5V3V6V7V86.8 關(guān)鍵路徑計算關(guān)鍵路徑計算課本例題6.19，圖中結(jié)點內(nèi)大寫字母A-H表示活動，字母右下角帶括號的數(shù)字表示完成此活動所需的時間。分析圖中活動時間可知，完成路徑A、C、F、H上的各活動需要11個時間單位，這幾個活動中任意一個的延遲都會延長整個工期，實際上這是一條“關(guān)鍵路徑”。但活動B可以延遲3個時間單位，并不會影響整個整個工程的完成進(jìn)度，相對于關(guān)鍵路徑，包含活動B的路徑是非關(guān)鍵路徑。v 從源點到各個頂點, 以至從源點到匯點的有向路徑可能不止一條。這些路徑的長度也可能不同。 完成不同路徑的活動所需的時間雖然不同, 但只有各條路徑上所有活動都完成了, 整個工程才算完成。v 因此

8、, 完成整個工程所需的時間取決于從源點到匯點的最長路徑長度, 即在這條路徑上所有活動的持續(xù)時間之和。這條路徑長度最長的路徑就叫做關(guān)鍵路徑(Critical Path)。 為了便于分析關(guān)鍵路徑，將活動為頂點的AOV圖轉(zhuǎn)換為活動為邊的AOE圖，有向邊表示任務(wù)或活動，邊上的權(quán)表示該活動持續(xù)的時間。在AOE圖中頂點表示事件，每個事件對應(yīng)一個活動及與之相關(guān)的其他活動完成。 如果一個活動是在幾個活動完成后才能開始，則需要增加虛構(gòu)的邊和結(jié)點，來表示活動之間的這種依賴關(guān)系。 與AOV網(wǎng)相對應(yīng)的是AOE(Activity On Edge) ，是邊表示活動的有向無環(huán)圖，如圖所示。圖中頂點表示事件(Event)，每

9、個事件表示在其前的所有活動已經(jīng)完成，其后的活動可以開始；弧表示活動，弧上的權(quán)值表示相應(yīng)活動所需的時間或費用。065432178a1=3a2=10a3=9a4=13a5=12a6=7a7=8a9=6a10=11a12=5a8=4a11=2圖圖 一個一個AOE網(wǎng)網(wǎng)頂點1和10分別表示工程的開始和完成事件?；顒覦是在活動A和B都完成才能開始。A和B兩個活動的完成表示為2和3兩個事件，在兩個事件中引入虛構(gòu)結(jié)點6(灰色表示）和兩條0標(biāo)識（該活動所需時間為0）的虛構(gòu)活動邊，使得活動D是在A、B完成后才能開始。121036A/3B/2004567878109C/400E/1D/20G/2F/3k/4000H

10、/10用以下方法簡化：對出度為1的頂點，如果其出邊的權(quán)值為0，則可刪除該頂點及其出邊,該頂點的入邊直接指向后面的頂點。12934A/3B/200567810C/40E/1D/20G/2F/3k/4H/10在各頂點的上方標(biāo)出各事件最早完成的時間，在結(jié)束事件上方標(biāo)出的11個時間單位是整個工程的最早完成時間。若Earliesti表示結(jié)點i的最早完成時間，Cv,w表示邊的權(quán)值，則有：Earliest1=0Earliestw=max(Earliestv+Cv,w) E12934A/3B/200567810C/40E/1D/20G/2F/3k/4H/10032335751011還可求解每一事件i在不影響整

11、個工程完成情況下所允許最晚完成時間Latesti。計算是從結(jié)束事件開始，設(shè)結(jié)束頂點為事件n，按事件拓?fù)涞南喾创涡蛑饌€頂點結(jié)算，直到工程的初始頂點為止。Latestn=EarliestnLatestv=min(Latestw-Cv,w) E12934A/3B/200567810C/40E/1D/20G/2F/3k/4H/10055367781011各頂點的最早和最晚完成時間求出后，就可確定在不影響工程進(jìn)度的前提下，每一活動最多能耽誤的時間長短。這個時間是否為0決定了該活動是否處于關(guān)鍵路徑上。求邊上的允許耽誤的最大時間Delayv,w采用的計算公式為:Delayv,w=Latestw-Earliestv-Cv,w12934A/3B/200567810C/40E/1D/20G/2F/3k/4H/10055367781011最多能耽誤時間為0（即不允許有時間耽誤）的活動都是“關(guān)鍵活動”，由關(guān)鍵活動構(gòu)成的從頭至尾的