109 年 國立成功大學工程科學系碩士班乙組《資料結構》

核心觀念

本題考查 Max Heap（最大堆積） 的正式定義。最大堆積必須同時滿足以下兩項條件：

1. 結構性質：完全二元樹

   除了最底層之外，每一層都必須填滿；最底層的節點必須由左至右連續排列。

2. 堆積順序性質：最大堆積性質

   每一個父節點的鍵值都不小於其子節點的鍵值。對任意節點 $v$：

   $$key(parent(v)) \geq key(v)$$

因此，根節點一定 chứa有整棵樹中的最大鍵值。

解題方法

判斷一棵二元樹是否為最大堆積時，依序檢查：

• 樹的形狀是否為完全二元樹；
• 每個父節點是否都滿足「父節點鍵值 $\geq$ 子節點鍵值」。

例如：

此樹是完全二元樹，且有：

所以它是最大堆積。

最大堆積只要求父子節點之間的大小關係，不要求左子樹與右子樹之間具有排序關係，因此它不等同於二元搜尋樹。

陣列表示法

插入順序 8、12、6、30、23、24、5、33、61、15，依次維持 max‑heap 性質，最終以 1‑索引陣列表示：

對應的二元樹結構（左子樹在左、右子樹在右）：

解題步驟

1. 先取 preorder 的第一個元素作為根節點。
   $\text{根}=D$

2. 在 inorder 中找根 $D$，將其左側作左子樹的 inorder，右側作右子樹的 inorder。

   • 左 inorder：$A\;F$（長度 $2$）
   • 右 inorder：$B\;I\;G\;H\;E\;C$（長度 $6$）

3. 依左、右 inorder 的長度，從 preorder（根之後）切分出左、右子樹的 preorder。

   • 左 preorder：$A\;F$
   • 右 preorder：$I\;B\;E\;G\;H\;C$

4. 遞迴建左子樹（preorder $A\;F$, inorder $A\;F$）

   • 根 $A$ → 左 inorder 空，右 inorder $F$ → $A$ 右子為 $F$。

5. 遞迴建右子樹（preorder $I\;B\;E\;G\;H\;C$, inorder $B\;I\;G\;H\;E\;C$）

   • 根 $I$ → 左 inorder $B$（長度 $1$），右 inorder $G\;H\;E\;C$（長度 $4$）

核心觀念

Sollin’s algorithm 又稱 Borůvka’s algorithm，用來求加權無向連通圖的最小成本生成樹（Minimum Cost Spanning Tree, MST）。

每一輪對目前的每個連通分量，選出一條連接該分量與其他分量的最小權重邊，將這些邊加入生成樹。依切割定理，對任一連通分量而言，跨越該分量切割的最小邊必屬於某棵 MST，因此可安全加入。

最終必須取得：

• 包含全部 $|V|$ 個頂點；
• 恰有 $|V|-1$ 條邊；
• 不含任何 cycle；
• 總邊權重最小。

解題方法

設目前的連通分量為 $C_1,C_2,\ldots,C_k$。

每一輪執行：

1. 對每個連通分量 $C_i$，找出權重最小的跨分量邊：
   $e_i=\arg\min\{w(u,v)\mid u\in C_i,\ v\notin C_i\}.$

2. 將所有選出的邊加入候選集合。

3. 若多個分量選到同一條邊，只加入一次。

核心觀念

• 迴圈時間複雜度分析（Loop Time Complexity Analysis）：計算程式碼中迴圈主體（Loop Body）的基本指令被執行的總次數。
• 等比級數與對數複雜度（Logarithmic Complexity）：當迴圈控制變數以等比級數（如乘以固定常數 $c > 1$）遞增時，該迴圈的迭代次數為對數階 $O(\log n)$。
• 獨立巢狀迴圈（Uncoupled Nested Loops）：若內層迴圈的邊界條件與外層迴圈變數無關，則總執行次數為「外層迴圈次數 $\times$ 內層迴圈次數」。
• 漸進標記（Asymptotic Notation）：使用 Big-$\Theta$ 標記精確描述演算法執行時間隨輸入規模 $n$ 成長的階數（Order of Growth）。

解題方法

本題包含兩層巢狀迴圈，且兩層迴圈之變數獨立，可分別分析外層與內層的執行次數：

1. 外層迴圈分析（k 迴圈）

• 初始值：$k = 1$
• 更新方式：每次迭代將 $k$ 乘以 $3$（即 $k = k \times 3$）
• 終止條件：$k > n$
• 變數變化軌跡：$k$ 的數值依序為 $3^0, 3^1, 3^2, \dots, 3^m$。
• 設外層迴圈共執行了 $m + 1$ 次，當迴圈在第 $m$ 次迭代結束時，需滿足 $3^m \le n$。兩邊取對數可得：
  $m \le \log_3 n$
  因此，外層迴圈之迭代次數為 $\lfloor \log_3 n \rfloor + 1 = \Theta(\log_3 n) = \Theta(\log n)$ 次。

2. 內層迴圈分析（j 迴圈）

• 初始值：$j = 1$
• 更新方式：每次迭代 $j$ 加 $1$（即 $j = j + 1$）
• 終止條件：$j > n$
• 對於外層迴圈的每一次執行，內層迴圈皆固定從 $j = 1$ 執行到 $j = n$，迭代次數為 $n$ 次，即 $\Theta(n)$。

3. 總時間複雜度推導

基本敘述 sum++ 執行的總次數 $T(n)$ 可表示為雙重求和式：

核心觀念

本題旨在評量程式碼之**時間複雜度分析（Time Complexity Analysis）與等比級數求和（Geometric Series Summation）**能力。

分析巢狀迴圈（Nested Loops）的時間複雜度時，重點在於釐清內外迴圈變數之間的相依性。若內層迴圈的執行次數依賴於外層迴圈變數，則不能直接將兩層的複雜度相乘，必須將總執行次數表示為對迴圈變數求和的數學式（Sigma notation），再以漸近記號（Asymptotics, 如大 $\mathcal{O}$ 或大 $\Theta$）表示。

解題方法

1. 分析外層與內層迴圈的執行次數：

   • 外層迴圈：變數 $k$ 從 $1$ 開始，每次迭代乘以 $2$（即 $k = 1, 2, 4, 8, \dots, 2^i$），直到 $k > n$ 停止。
     假設外層迴圈共執行 $m+1$ 次迭代（$i = 0, 1, 2, \dots, m$），則 $k = 2^i$，其中 $m = \lfloor \log_2 n \rfloor$，滿足 $2^m \le n < 2^{m+1}$。
   • 內層迴圈：在給定外層變數 $k$ 的情況下，變數 $j$ 從 $1$ 遞增至 $k$，因此內層迴圈的基本指令 sum++ 會精確執行 $k$ 次。

2. 建立總執行次數之數學表達式：
   整體基本操作 sum++ 的總執行次數 $T(n)$ 為各次外層迴圈對應內層執行次數的累加：
   $T(n) = \sum_{i=0}^{m} 2^i = 1 + 2 + 4 + 8 + \dots + 2^m$

3. 利用等比級數公式求和並推導複雜度：
   根據等比級數求和公式 $S = \frac{a(r^N - 1)}{r - 1}$，其中首項 $a=1$，公比 $r=2$，項數 $N = m+1$：
   $T(n) = \frac{1 \cdot (2^{m+1} - 1)}{2 - 1} = 2^{m+1} - 1$

   因為 $2^m \le n < 2^{m+1}$，故可知 $2^{m+1} = 2 \cdot 2^m \le 2n$。
   將此範圍帶入 $T(n)$：
   $n < T(n) \le 2n - 1$

核心觀念

本題考查巢狀迴圈（Nested Loops）的時間複雜度分析與迴圈迭代次數的數學推導。
主要觀念包含：

1. 等比級數遞增與對數複雜度：當迴圈控制變數以乘法（如 k *= 5）方式遞增時，其執行次數與對數 $\log$ 成正比。
2. 獨立巢狀迴圈（Independent Nested Loops）：當內層迴圈的執行次數與外層迴圈變數無關時，總執行次數即為「外層執行次數」與「內層執行次數」之乘積。
3. 漸近符號（Asymptotic Notation）：使用 Big-$\Theta$ 或 Big-$O$ 表示當輸入規模 $n$ 趨近於無窮大時的執行時間成長率。

解題方法

本題採用由外至內分別求算執行次數後相乘的切入點。

1. 外層迴圈分析

• 程式碼：for(k=1; k<=n*n; k *= 5)
• 迭代規律：變數 $k$ 的初始值為 $1$，每次疊代乘以 $5$。故 $k$ 的數值序列為 $5^0, 5^1, 5^2, \dots, 5^m$。
• 終止條件：迴圈持續執行的條件為 $k \le n^2$，即：
  $5^m \le n^2$
• 求算疊代次數 $m$：兩邊取以 $5$ 為底的對數 $\log_5$：
  $m \le \log_5(n^2) = 2 \log_5 n$
• 故外層迴圈的總疊代次數為 $m + 1 = \lfloor 2 \log_5 n \rfloor + 1$ 次。
• 在漸近記號下，常數倍數與對數底數均可省略，外層時間複雜度為：
  $T_{\text{outer}}(n) = \Theta(\log n)$

2. 內層迴圈分析

• 程式碼：for(j=1; j<=n; j++)
• 迭代規律：變數 $j$ 從 $1$ 遞增至 $n$，每次加 $1$。
• 獨立性：內層迴圈的終止條件 j<=n 固定與外層變數 $k$ 無關。
• 故每一次外層迴圈執行時，內層迴圈皆固定執行 $n$ 次，內層時間複雜度為：
  $T_{\text{inner}}(n) = \Theta(n)$

3. 總時間複雜度推導

最內層基本指令 sum++ 的總執行次數 $T(n)$ 為外層與內層執行次數之總和：

核心觀念

本題考察**快速排序法（Quick Sort）**的運作機制與追蹤（Trace）能力。

1. 分治法（Divide and Conquer）：
   快速排序採用分治策略，每輪（Phase / Pass）選擇一個元素作為樞紐碼（Pivot），將陣列分割（Partition）為兩個子陣列：

   • 左子陣列：所有元素皆小於或等於 Pivot。
   • 右子陣列：所有元素皆大於或等於 Pivot。
     分割完成後，Pivot 便會被放置在最終排序後的正確位置，後續再對左右子陣列遞迴執行相同的操作。

2. 國內研究所考試標準 Partition 演算法（Horowitz 經典版本）：
   在國內資訊與工程研究所考試中，資料結構預設採用 Ellis Horowitz 所著《Fundamentals of Data Structures in C》之經典實現：

   • Pivot 選擇：預設選取當前子陣列的第一個元素（$Pivot = F[low]$）。
   • 雙指標掃描：
     • 指標 $i$ 從左端（$low$）向右掃描，尋找第一個 $\ge Pivot$ 的元素。
     • 指標 $j$ 從右端（$high+1$）向左掃描，尋找第一個 $\le Pivot$ 的元素。
   • 交換條件：當 $i < j$ 時，將 $F[i]$ 與 $F[j]$ 交換，並繼續掃描；當 $i \ge j$ 時停止掃描。
   • Pivot 歸位：將 $Pivot$（即 $F[low]$）與 $F[j]$ 交換。此時 $j$ 即為 Pivot 的最終正確索引位置。

3. 複雜度分析：

   • 時間複雜度：平均為 $\mathcal{O}(n \log n)$，最差情況（已排序或逆序陣列）為 $\mathcal{O}(n^2)$。
   • 空間複雜度：主要來自遞迴呼叫堆疊，平均為 $\mathcal{O}(\log n)$，最差為 $\mathcal{O}(n)$。
   • 穩定性：不穩定排序（Unstable Sort）。

解題方法

給定初始序列 $F = (12, 25, 19, 2, 25, 3, 29, 8, 17, 81, 6)$，長度 $n = 11$。
採用以第一個元素為 Pivot 的 Horowitz 經典 Partition 演算法，按遞迴順序（先處理左半部、再處理右半部）逐步執行並寫出每一輪（Phase）結束時的全陣列狀態：

Phase 1：對全陣列 $F[1..11]$ 進行 Partition

• 當前子陣列：$(12, 25, 19, 2, 25, 3, 29, 8, 17, 81, 6)$
• Pivot：$12$
• 執行步驟：
  1. $i$ 由左向右找 $> 12$ 的元素（停在 $25$，$i=2$）；$j$ 由右向左找 $< 12$ 的元素（停在 $6$，$j=11$）。因 $i < j$，交換 $F[2]$ 與 $F[11]$ $\implies (12, \mathbf{6}, 19, 2, 25, 3, 29, 8, 17, 81, \mathbf{25})$。
  2. $i$ 繼續右移停在 $19$（$i=3$）；$j$ 繼續左移停在 $8$（$j=8$）。因 $i < j$，交換 $F[3]$ 與 $F[8]$ $\implies (12, 6, \mathbf{8}, 2, 25, 3, 29, \mathbf{19}, 17, 81, 25)$。
  3. $i$ 繼續右移停在 $25$（$i=5$）；$j$ 繼續左移停在 $3$（$j=6$）。因 $i < j$，交換 $F[5]$ 與 $F[6]$ $\implies (12, 6, 8, 2, \mathbf{3}, \mathbf{25}, 29, 19, 17, 81, 25)$。
  4. $i$ 繼續右移停在 $29$（$i=7$）；$j$ 繼續左移停在 $3$（$j=5$）。此時 $i > j$，掃描結束。
  5. 交換 Pivot $F[1]$（$12$）與 $F[5]$（$3$）。
• Phase 1 結束陣列狀態：$(3, 6, 8, 2, \mathbf{12}, 25, 29, 19, 17, 81, 25)$（Pivot $12$ 已在正確位置 $F[5]$）

Phase 2：對左子陣列 $F[1..4]$ 進行 Partition

• 當前子陣列：$(3, 6, 8, 2)$
• Pivot：$3$
• 執行步驟：
  1. $i$ 停在 $6$（$i=2$）；$j$ 停在 $2$（$j=4$）。因 $i < j$，交換 $F[2]$ 與 $F[4]$ $\implies (3, \mathbf{2}, 8, \mathbf{6})$。
  2. $i$ 右移停在 $8$（$i=3$）；$j$ 左移停在 $2$（$j=2$）。此時 $i > j$，掃描結束。
  3. 交換 Pivot $F[1]$（$3$）與 $F[2]$（$2$）。
• Phase 2 結束陣列狀態：$(\mathbf{2}, \mathbf{3}, 8, 6, \mathbf{12}, 25, 29, 19, 17, 81, 25)$（Pivot $3$ 已在正確位置 $F[2]$）

Phase 3：對子陣列 $F[3..4]$ 進行 Partition

• 當前子陣列：$(8, 6)$
• Pivot：$8$
• 執行步驟：
  1. $i$ 停在超出範圍的索引 $5$（$i=5$）；$j$ 停在 $6$（$j=4$）。此時 $i > j$，掃描結束。
  2. 交換 Pivot $F[3]$（$8$）與 $F[4]$（$6$）。
• Phase 3 結束陣列狀態：$(2, 3, \mathbf{6}, \mathbf{8}, \mathbf{12}, 25, 29, 19, 17, 81, 25)$（Pivot $8$ 已在正確位置 $F[4]$）

Phase 4：對右子陣列 $F[6..11]$ 進行 Partition

• 當前子陣列：$(25, 29, 19, 17, 81, 25)$
• Pivot：$25$
• 執行步驟：
  1. $i$ 停在 $29$（$i=7$）；

核心觀念

本題考查**插入排序法（Insertion Sort）在決策樹模型（Decision Tree Model）**下的執行過程與結構建立。

1. 比較排序法與決策樹（Decision Tree for Comparison Sort）：
   • 決策樹是用於描述基於比較（Comparison-based）排序演算法所有可能執行路徑的二元樹（Binary Tree）。
   • 內部節點（Internal Nodes）：代表演算法執行過程中元素之間的比較，格式記作 $a_i : a_j$（代表比較 $a_i$ 與 $a_j$，亦即判定條件 $a_i \le a_j$）。
   • 分支（Branches）：代表比較的結果。左分支代表「是（$\le$）」，右分支代表「否（$>$）」。
   • 葉節點（Leaf Nodes）：代表輸入序列經排序後的最終排列結果（Permutation）。長度為 $n$ 的序列共有 $n!$ 種可能的排列，故決策樹必包含 $n!$ 個葉節點。
2. 題目假設：
   因題幹提及「based on the list of (a)」，按研究所考試常規，假設 (a) 小題之輸入序列長度為 $n=3$，設輸入序列為 $A = \langle a_1, a_2, a_3 \rangle$。

解題方法

插入排序法（Insertion Sort）的運作邏輯為：由左至右依序處理元素，將當前未排序元素插入至左側已排序好的子序列適當位置。對長度 $n=3$ 的序列 $A = \langle a_1, a_2, a_3 \rangle$ 構建決策樹的推導步驟如下：

1. 第一階段：將 $a_2$ 插入已排序子序列 $\langle a_1 \rangle$

   • 根節點比較：比較 $a_1 : a_2$（判定 $a_1 \le a_2$ 是否成立）。
     • 左分支（$a_1 \le a_2$）：子序列為 $\langle a_1, a_2 \rangle$。
     • 右分支（$a_1 > a_2$）：子序列為 $\langle a_2, a_1 \rangle$。

2. 第二階段：將 $a_3$ 插入已排序子序列

   • 當前子序列為 $\langle a_1, a_2 \rangle$ 時（根節點左分支）：

     • 比較 $a_2 : a_3$（判定 $a_2 \le a_3$）：
       • 是（$a_2 \le a_3$）：$a_3 \ge a_2$，直接置於尾端，輸出葉節點 $\langle a_1, a_2, a_3 \rangle$。
       • 否（$a_2 > a_3$）：$a_3 < a_2$，需繼續向左比較 $a_1 : a_3$（判定 $a_1 \le a_3$）：
         • 是（$a_1 \le a_3$）：$a_1 \le a_3 < a_2$，輸出葉節點 $\langle a_1, a_3, a_2 \rangle$。
         • 否（$a_1 > a_3$）：$a_3 < a_1 \le a_2$，輸出葉節點 $\langle a_3, a_1, a_2 \rangle$。

   • 當前子序列為 $\langle a_2, a_1 \rangle$ 時（根節點右分支）：

     • 比較 $a_1 : a_3$（判定 $a_1 \le a_3$）：
       • 是（$a_1 \le a_3$）：$a_3 \ge a_1$，直接置於尾端，輸出葉節點 $\langle a_2, a_1, a_3 \rangle$。
       • 否（$a_1 > a_3$）：$a_3 < a_1$，需繼續向左比較 $a_2 : a_3$（判定 $a_2 \le a_3$）：
         • 是（$a_2 \le a_3$）：$a_2 \le a_3 < a_1$，輸出葉節點 $\langle a_2, a_3, a_1 \rangle$。
         • 否（$a_2 > a_3$）：$a_3 < a_2 < a_1$，輸出葉節點 $\langle a_3, a_2, a_1 \rangle$。

選項分析

本題為非選擇題（計算與繪圖題）。針對決策樹中各內部比較節點與對應的分支邏輯進行完整剖析：

1. 根節點 $a_1 : a_2$ 分析：
   • 判定 $a_1 \le a_2$ 是否成立。若成立則維持 $\langle a_1, a_2 \rangle$ 順序走左分支；若不成立則形成 $\langle a_2, a_1 \rangle$ 順序走右分支。

核心觀念

本題考查**快速排序（Quick Sort）與插入排序（Insertion Sort）在最佳情況（Best Case）**下的時間複雜度（Time Complexity）推導與比較，並檢驗考生對演算法內部運作機制與遞迴關係式的理解。

核心定義與定理：

1. 插入排序（Insertion Sort）：屬於適應性排序（Adaptive Sort）。設資料筆數為 $n$。當輸入資料已經呈現**完全遞增排序（Already Sorted）**時為最佳情況，內層迴圈只需比較一次即可結束。
2. 快速排序（Quick Sort）：採用分治法（Divide and Conquer）。當每次分割所選取的基準值（Pivot）均能**精確將數列對半分割（Balanced Partition）**時達到最佳情況。
3. 主定理（Master Theorem）：用於求解分治遞迴式 $T(n) = aT(n/b) + f(n)$ 之漸進複雜度。

解題方法

1. 插入排序（Insertion Sort）之最佳情況

• 觸發條件：輸入陣列已是遞增排序狀態（如 $[1, 2, 3, \dots, n]$）。
• 關鍵推導：
  在處理第 $i$ 個元素（$i = 2, 3, \dots, n$）時，只需與前一個元素（第 $i-1$ 個）進行 1 次比較，即可確定其位置並結束內層迴圈，且無需進行任何元素搬移。
  總比較次數為：
  $\sum_{i=2}^{n} 1 = n - 1 = O(n)$
• 最佳時間複雜度：$O(n)$

2. 快速排序（Quick Sort）之最佳情況

• 觸發條件：每次 Partition（分割）操作選取的 Pivot 都恰好是該區間的中位數（Median），使分割出來的兩個子數列規模儘可能相等（均為 $\approx n/2$）。
• 關鍵推導：
  長度為 $n$ 的數列在 Partition 時需進行 $c \cdot n$ 次比較與處理，之後遞迴處理兩個規模為 $n/2$ 的子問題。其時間複雜度遞迴式為：
  $T(n) = 2T\left(\frac{n}{2}\right) + c \cdot n$
  根據主定理（Master Theorem），其中 $a = 2$, $b = 2$, $f(n) = c \cdot n$：

核心觀念

本題考最大流問題。每條有向邊的流量不得超過容量，除起點 $s$ 與終點 $t$ 外，各節點都須滿足流入量等於流出量。最大流－最小割定理指出：最大流值等於最小割的容量。

解題方法

取三條由 $s$ 通往 $t$ 的路徑，分別送流：

• 上方路徑：$s \to$ 左上節點 $\to$ 右上節點 $\to t$，送 $10$ 單位。沿途容量為 $11、10、17$，因此可送 $10$。
• 下方路徑：$s \to$ 左下節點 $\to$ 右下節點 $\to t$，送 $8$ 單位。沿途容量為 $8、18、9$，因此可送 $8$。

本題要求根據 AOE (Activity on Edge) 網路圖，計算每個活動的早期開始時間 (Early Start Time, ES)。

AOE 網路圖的節點代表事件 (events)，邊代表活動 (activities)。活動的持續時間標示在邊上。
早期開始時間 (ES) 的計算：

• 對於起點事件 (source event)，其 ES 為 0。
• 對於其他任何事件 $v$，其 ES 是所有指向 $v$ 的活動的「最早完成時間」的最大值。
• 事件 $v$ 的最早完成時間 (Earliest Finish Time, EF) = ES(v) + duration(activity leading to v)。
• 換句話說，事件 $v$ 的 ES 等於所有從 $v$ 出發的活動的最早開始時間 (ES) 加上該活動持續時間 (duration) 的最大值。
  $ES(v) = \max \{ EF(u) \}$ 對於所有指向 $v$ 的活動 $(u, v)$。
  其中 $EF(u) = ES(u) + duration(u, v)$.
  所以 $ES(v) = \max \{ ES(u) + duration(u, v) \}$。

圖示分析：
節點：V0, V1, V2, V3, V4, V5, V6, V7, V8, V9 (start to finish)
活動 (邊) 及其持續時間：

• a0: V0 -> V1, duration=3
• a1: V0 -> V2, duration=4
• a2: V1 -> V3, duration=2
• a3: V2 -> V3, duration=4
• a4: V2 -> V4, duration=3
• a5: V3 -> V5, duration=3
• a6: V3 -> V6, duration=1
• a7: V5 -> V6, duration=7
• a8: V5 -> V7, duration=6
• a9: V4 -> V7, duration=4
• a10: V6 -> V8, duration=5
• a11: V7 -> V8, duration=4
• a12: V6 -> V9, duration=5
• a13: V8 -> V9, duration=3

計算早期開始時間 (ES)：
我們需要按照拓撲順序計算。

• 事件 V0 (Start):

  • $ES(V0) = 0$

• 事件 V1:

  • 指向 V1 的活動：a0 (V0 -> V1, duration=3)
  • $ES(V1) = ES(V0) + duration(a0) = 0 + 3 = 3$

• 事件 V2:

  • 指向 V2 的活動：a1 (V0 -> V2, duration=4)
  • $ES(V2) = ES(V0) + duration(a1) = 0 + 4 = 4$

• 事件 V3:

  • 指向 V3 的活動：a2 (V1 -> V3, duration=2), a3 (V2 -> V3, duration=4)
  • $ES(V3) = \max \{ ES(V1) + duration(a2), ES(V2) + duration(a3) \}$
  • $ES(V3) = \max \{ 3 + 2, 4 + 4 \}$
  • $ES(V3) = \max \{ 5, 8 \} = 8$

• 事件 V4:

  • 指向 V4 的活動：a4 (V2 -> V4, duration=3)
  • $ES(V4) = ES(V2) + duration(a4) = 4 + 3 = 7$

• 事件 V5:

  • 指向 V5 的活動：a5 (V3 -> V5, duration=3)
  • $ES(V5) = ES(V3) + duration(a5) = 8 + 3 = 11$

核心觀念

AOE 網路以頂點表示事件、以有向邊表示活動。設活動 $a_{ij}$ 從事件 $i$ 到事件 $j$，工期為 $t_{ij}$；事件 $j$ 的最晚發生時間為 $L(j)$，則活動的最晚開始時間為：

反向計算各事件的最晚發生時間時，終點設為專案完工時間，並使用：

解題方法

先由圖中各活動工期計算事件的最早發生時間，以取得專案完工時間。各事件最早發生時間為：

因此專案完工時間為 $25$。從終點 $V_9$ 反向計算，得到事件最晚發生時間：

例如，$V_3$ 有三條後續活動，故：

本題要求根據 AOE 網路圖，確定專案的關鍵路徑 (Critical Path)。

關鍵路徑是 AOE 網路中，從起點事件到終點事件的最長路徑。關鍵路徑上的活動稱為關鍵活動 (critical activities)。關鍵活動的持續時間對整個專案的總持續時間有直接影響，任何延遲都會導致專案延遲。

關鍵路徑的判斷依據是活動的「剩餘時間」(Slack, S)。
Slack (S) = LS - ES = LF - EF
其中：

• ES: 早期開始時間 (Early Start Time)
• LS: 最晚開始時間 (Late Start Time)
• EF: 早期完成時間 (Early Finish Time) = ES + duration
• LF: 最晚完成時間 (Late Finish Time) = LS + duration = LE (Late Event Time of the ending event)

活動的 Slack 為 0 時，該活動是關鍵活動。關鍵路徑是連接關鍵活動的一系列路徑。

根據 6(a) 和 6(b) 的計算結果：