AOE網

在現代化管理中，人們常用有向圖來描述和分析一項工程的計畫和實施過程，一個工程常被分為多個小的子工程，這些子工程被稱為活動（Activity)，在帶權有向圖中若以頂點表示事件，有向邊表示活動，邊上的權值表示該活動持續的時間，這樣的圖簡稱為AOE網。

基本介紹

• 中文名：AOE網
• 外文名：Activity On Edge Network
• 形式：圖
• 目的：描述和分析工程的計畫和過程

概念

有向無環圖

一個無環的有向圖稱作有向無環圖(directed acyclic graph)，簡稱DAG圖。假設以有向圖表示一個工程的施工圖或程式的數據流圖，則圖中不允許出現迴路，如果出現迴路，說明了某項活動以它自己為先決條件，顯然是荒謬的，工程將無法進行。

拓撲排序

拓撲排序是一種對非線性結構的有向圖進行線性化的重要手段。在給定的有向圖G中，若頂點序列Vi1，Vi2，Vi3，....,Vin，。滿足下列條件：若在有向圖G中從頂點Vi，到頂點Vj有一條路徑，則在序列中頂點Vi必在頂點Vj之前，便稱這個序列為一個拓撲序列。求一個有向圖拓撲序列的過程稱為拓撲排序。
拓撲排序的方法如下：
(1)從圖中選擇一個人度為O的頂點並輸出；
(2)從圖中刪掉該頂點及其所有以該頂點為弧尾的弧。
反覆執行這兩個步驟，直到所有的頂點都被輸出，輸出的序列就是這個無環有向圖的拓撲序列。

如果在帶權有向圖中，用頂點表示事件，用有向邊表示活動，邊上的權值表示活動的開銷，則此帶權有向圖稱為邊活動網(activity on edge network)，簡稱AOE網。AOE網是一個有向無環圖。AOE網是用來描述由許多交叉活動組成的複雜計畫和工程的方法，比如某工程的AOE網。

在工程中用邊表示活動，邊上的權表示完成這項活動所需要的時間，頂點表示某項活動的開始，頂點1稱為源點（或起點），表示整個工程開始，頂點2稱為匯點（或終點），表示整個工程的結束。用AOE網來估算工程的最短工期（完成整個工程至少需要多少時間）以及哪些活動是影響工程進展的關鍵。

AOE網

幾個術語

路徑長度：路徑上各活動持續時間的總和（即路徑上所有權之和）。
完成工程的最短時間：從工程開始點（源點）到完成點（匯點）的最長路徑稱為完成工程的最短時間。

關鍵路徑：路徑長度最長的路徑稱為關鍵路徑。

性質

（1）只有在某頂點所代表的事件發生後，從該頂點出發的各有向邊所代表的活動才能開始。

（2）只有在進入某點的各有向邊所代表的活動都已結束，該頂點所代表的時事件才能發生。

關鍵路徑（臨界路徑）：在AOE網路中從源點到匯點（結束頂點）的最長路徑。關鍵路徑上的活動為關鍵活動。