108 年 國立成功大學資訊工程系碩士班《程式設計》

這部分考驗對圖論基本概念、演算法時間複雜度、資料結構的理解。

(1) False。
* 核心觀念：DFS 的時間複雜度與圖的表示法（鄰接矩陣 vs 鄰接串列）和圖的邊數 (e) 及頂點數 (v) 有關。
* 詳解：
* 當圖使用鄰接矩陣表示時，DFS 演算法需要遍歷所有頂點，對於每個頂點，需要檢查所有可能的邊，也就是檢查該頂點與其他所有頂點之間是否存在邊。一個頂點的鄰接矩陣表示需要 $O(v)$ 的時間來尋找所有相鄰的頂點。由於有 $v$ 個頂點，總時間複雜度為 $O(v \times v) = O(v^2)$。
* 題目敘述 DFS 需要 $O(e^2)$ 時間，這是錯誤的。DFS 的時間複雜度，不論圖的表示法為何，通常與 $v$ 和 $e$ 有關。對於鄰接矩陣，是 $O(v^2)$；對於鄰接串列，是 $O(v+e)$。
* 【答案】False

(2) False。
* 核心觀念：最小生成樹 (MST) 的邊不一定構成最短路徑。
* 詳解：
* 最小生成樹 (MST) 的目標是連接所有頂點，且總權重最小。它保證了連通性，但並不保證路徑上的邊權總和最小。
* 最短路徑演算法（如 Dijkstra 或 Bellman-Ford）尋找的是兩個特定頂點之間權重總和最小的路徑。
* 舉例：假設有一個圖 G，頂點為 A, B, C。邊為 (A,B) 權重 1，(B,C) 權重 1，(A,C) 權重 10。
* MST 可能會選擇邊 (A,B) 和 (B,C)，總權重為 2。

核心觀念

AOE（Activity on Edge）網路中：

• 頂點代表事件。
• 邊代表活動，邊上的數字為活動工期。
• $E(v)$：事件 $v$ 的最早發生時間。
• $L(v)$：事件 $v$ 的最晚發生時間。
• 對活動 $a_i=(u,v)$，其：

$$e(i)=E(u)$$ $$l(i)=L(v)-d_i$$

其中 $d_i$ 為活動 $a_i$ 的工期。

若 $e(i)=l(i)$，表示活動沒有延遲餘裕，為關鍵活動。

---

解題方法

由圖可得各活動如下：

活動	起點 → 終點	工期
$a_1$	$V_0\to V_1$	9
$a_2$	$V_0\to V_2$	4
$a_3$	$V_0\to V_3$	7
$a_4$	$V_1\to V_4$	2
$a_5$	$V_2\to V_4$	2
$a_6$	$V_3\to V_5$	4
$a_7$	$V_4\to V_6$	5
$a_8$	$V_4\to V_7$	7
$a_9$	$V_5\to V_7$	7
$a_{10}$	$V_6\to V_8$	1
$a_{11}$	$V_7\to V_8$	1
$a_{12}$	$V_5\to V_8$	3

1. 計算事件最早時間 $E(v)$

由起點向終點進行正向計算：

$$E(V_0)=0$$ $$E(V_1)=0+9=9$$ $$E(V_2)=0+4=4$$ $$E(V_3)=0+7=7$$ $$E(V_4)=\max(9+2,\;4+2)=11$$ $$E(V_5)=7+4=11$$ $$E(V_6)=11+5=16$$ $$E(V_7)=\max(11+7,\;11+7)=18$$ $$E(V_8)=\max(16+1,\;18+1,\;11+3)=19$$

因此專案最短完成時間為 $19$。

2. 計算事件最晚時間 $L(v)$

由終點向起點進行反向計算，令：

$$L(V_8)=E(V_8)=19$$

接著：

$$L(V_6)=19-1=18$$ $$L(V_7)=19-1=18$$ $$L(V_5)=\min(18-7,\;19-3)=11$$ $$L(V_4)=\min(18-5,\;18-7)=11$$ $$L(V_1)=11-2=9$$ $$L(V_2)=11-2=9$$ $$L(V_3)=11-4=7$$ $$L(V_0)=\min(9-9,\;9-4,\;7-7)=0$$

---

(1) 各活動的 $e(i)$ 與 $l(i)$

$$e(i)=E(\text{活動起點})$$ $$l(i)=L(\text{活動終點})-\text{活動工期}$$

核心觀念

依原卷圖，資料是由左至右排列的 8 個已排序 runs，每個 run 有 3 筆資料：

Run	資料
$R_1$	$5,13,22$
$R_2$	$8,18,30$
$R_3$	$23,27,38$
$R_4$	$1,15,19$
$R_5$	$4,10,24$
$R_6$	$3,20,32$
$R_7$	$16,17,35$
$R_8$	$11,21,25$

進行遞增合併時，每個 run 的目前最前端元素放在樹的葉節點。Winner tree 的每個內部節點儲存兩個子樹中的較小值，根節點即為下一筆輸出的資料。

輸出根節點後，從相同 run 取出下一筆資料，沿著該葉節點到根節點的路徑更新。

---

解題方法

(1) Winner tree

初始各 run 的前端資料為

$$(5,8,23,1,4,3,16,11).$$

第一層比較：

$$\min(5,8)=5,\qquad \min(23,1)=1,$$ $$\min(4,3)=3,\qquad \min(16,11)=11.$$

第二層比較：

$$\min(5,1)=1,\qquad \min(3,11)=3.$$

根節點比較：

$$\min(1,3)=1.$$

Winner tree 如下：

                              1 (R4)
                         /              \
                     1 (R4)             3 (R6)
                   /       \           /       \
                5 (R1)    1 (R4)    3 (R6)    11 (R8)
                /   \      /   \      /   \       /   \
             5(R1) 8(R2) 23(R3) 1(R4) 4(R5) 3(R6) 16(R7) 11(R8)

因此第一筆輸出為 $1$，來源是 $R_4$。

---

(2) 輸出一筆後的 Winner tree

輸出 $R_4$ 的 $1$ 後，$R_4$ 的下一筆資料為 $15$，因此葉節點更新為

$$(5,8,23,15,4,3,16,11).$$

只需更新 $R_4$ 到根節點的路徑：

$$\min(23,15)=15,$$ $$\min(5,15)=5,$$ $$\min(3,11)=3.$$

更新後的 Winner tree 為：

                              3 (R6)
                         /              \
                     5 (R1)             3 (R6)
                   /       \           /       \
                5 (R1)   15 (R4)    3 (R6)    11 (R8)
                /   \      /   \      /   \       /   \
             5(R1) 8(R2) 23(R3) 15(R4) 4(R5) 3(R6) 16(R7) 11(R8)

所以第二筆輸出為 $3$，來源是 $R_6$。

---

(3) Loser tree

Loser tree 的內部節點儲存每場比較的敗者，最上方另記錄整棵樹的總勝者。

根據第 (2) 題的資料進行比較：

這題考驗對 NP-completeness 證明方法的理解。證明一個問題是 NP-complete 通常需要兩部分：

1. 證明問題屬於 NP (Non-deterministic Polynomial time)：

   • 這意味著，如果給定一個問題的「解的候選」，我們可以在多項式時間內驗證這個候選解是否是正確的。
   • 驗證過程通常是：對於一個給定的解（例如，一個圖的子集、一個解的路徑等），檢查它是否滿足問題的所有約束條件，並判斷其是否為一個「可行解」。如果問題還要求優化（例如，最小化或最大化某個值），則還需檢查該解是否達到或超過了某個目標值。

2. 證明問題是 NP-hard (NP-困難)：

   • 這意味著，任何一個已知的 NP-complete 問題都可以在多項式時間內歸約 (reduce) 到我們正在考慮的問題。
   • 歸約的含義是：我們有一個已知的 NP-complete 問題 $P_1$，以及一個我們想要證明是 NP-hard 的問題 $P_2$。如果我們能將 $P_1$ 的任何一個實例轉換成 $P_2$ 的一個實例，並且這個轉換過程可以在多項式時間內完成，同時原問題 $P_1$ 的解能夠對應到轉換後問題 $P_2$ 的解，那麼 $P_2$ 就是 NP-hard。
   • 通常，歸約是通過構造一個從 $P_1$ 到 $P_2$ 的多項式時間轉換函數來完成的。這個函數將 $P_1$ 的輸入轉換成 $P_2$ 的輸入，使得 $P_1$ 有解若且唯若 $P_2$ 有解（或 $P_1$ 的優化解對應到 $P_2$ 的優化解）。
   • 常見的已知 NP-complete 問題包括：SAT (Satisfiability), 3-SAT, Vertex Cover, Hamiltonian Path/Cycle, Clique, Subset Sum 等。通常會選擇其中一個來進行歸約。

核心觀念

本題要求判斷無向圖 $G=(V,E)$ 是否含有 cycle，且時間複雜度必須為 $O(|V|)$，不能依賴 $|E|$。

關鍵定理是：

無 cycle 的無向圖是一片森林；若有 $|V|$ 個頂點，森林最多只有 $|V|-1$ 條邊。

因此：

• 若 $|E|\ge |V|$，圖必定含有 cycle。
• 若 $|E|<|V|$，則 $|E|=O(|V|)$，此時使用 DFS 或 BFS 檢查 cycle，總時間仍為 $O(|V|)$。

這是本題能達成「與 $|E|$ 無關的 $O(|V|)$」的核心。

---

解題方法

先檢查邊數：

1. 若 $|E|\ge |V|$，直接回傳「含有 cycle」。
2. 若 $|E|<|V|$，對圖執行 DFS。
   • DFS 遇到尚未拜訪的頂點，代表開始一個新的 connected component。
   • 在無向圖中，若目前頂點 $u$ 的鄰點 $v$ 已經拜訪過，且 $v$ 不是 $u$ 的 parent，則發現 cycle。

可用以下偽程式碼：

HasCycle(G):
    n ← |V|
    m ← |E|

    if m ≥ n:
        return true

    for each vertex v ∈ V:
        visited[v] ← false
        parent[v] ← NIL

    for each vertex s ∈ V:
        if visited[s] = false:
            if DFS(s, NIL) = true:
                return true

    return false


DFS(u, p):
    visited[u] ← true

    for each neighbor v of u:
        if visited[v] = false:
            parent[v] ← u
            if DFS(v, u) = true:
                return true
        else if v ≠ p:
            return true

    return false

---

正確性說明

若 $|E|\ge |V|$：

這部分考驗對演算法設計、圖論、動態規劃等核心概念的理解，要求判斷幾個敘述的真偽並給予解釋。

(a) 0-1 knapsack problem can be solved by greedy strategy.
* 核心觀念：0-1 背包問題的貪婪策略。
* 詳解：0-1 背包問題是指，給定一個背包容量和一系列物品，每個物品有重量和價值，要求在不超過背包容量的前提下，選擇物品使得總價值最大。每個物品只能選擇一次（0 或 1）。
* 常見的貪婪策略有：
1. 選擇價值最高的物品。
2. 選擇重量最輕的物品。
3. 選擇單位重量價值最高的物品。
* 這些貪婪策略都無法保證找到 0-1 背包問題的最優解。例如，對於單位重量價值最高的策略，可能因為重量太大而無法放入背包，或者選擇了總價值不如其他組合的物品。
* 0-1 背包問題是一個典型的動態規劃問題，其最優解通常通過建構一個表格來求解，時間複雜度為 $O(nW)$，其中 $n$ 是物品數量，$W$ 是背包容量。
* 反例：背包容量 $W=10$。物品 A：重量=10, 價值=100；物品 B：重量=6, 價值=70；物品 C：重量=6, 價值=70。
* 單位重量價值：A=10, B=11.67, C=11.67。
* 貪婪策略（單位重量價值最高）會選擇 B 和 C (總價值 140)，但這超過了容量。如果只能選一個，則 B 或 C。
* 如果選擇 A，價值為 100。
* 如果我們不按貪婪策略，而是考慮所有組合，發現選擇 B 和 C 是不可能的。如果選擇 A，價值 100。如果選擇 B，價值 70。如果選擇 C，價值 70。
* 再換個例子：背包容量 W=50。物品1：(重量=10, 價值=60)，物品2：(重量=20, 價值=100)，物品3：(重量=30, 價值=120)。
* 單位重量價值：物品1 = 6, 物品2 = 5, 物品3 = 4。
* 貪婪策略會先選物品1 (重量10, 價值60)。剩餘容量40。
* 再選物品2 (重量20, 價值100)。剩餘容量20。
* 無法再選物品3。總價值 = 60 + 100 = 160。
* 然而，選擇物品2 (重量20, 價值100) 和物品3 (重量30, 價值120) 是可行的，總重量 50，總價值 220。這是更優的解。
* 結論：False。

(b) In an undirected graph, we can apply the Depth-First-Search algorithm (DFS) to get tree edges and cross edges.
* 核心觀念：DFS 在圖中的邊分類（樹邊、前向邊、後向邊、橫向邊）。
* 詳解：
* 在 DFS 遍歷過程中，根據頂點的訪問狀態和它們之間的關係，邊可以被分為幾種類型：
* 樹邊 (Tree Edge)：當 DFS 從頂點 $u$ 遍歷到一個尚未訪問過的鄰居 $v$ 時，邊 $(u, v)$ 就是一條樹邊。這些邊構成了 DFS 樹。
* 後向邊 (Back Edge)：當 DFS 從頂點 $u$ 遍歷到一個鄰居 $v$，且 $v$ 已經被訪問過，並且 $v$ 是 $u$ 在 DFS 樹中的一個祖先（包括 $u$ 的父節點，但通常我們區分父節點和真正的祖先）。在無向圖中，如果 DFS 遇到一個已訪問的鄰居 $v$ 且 $v$ 不是 $u$ 的父節點，則這條邊 $(u, v)$ 形成了一個環，這條邊可以被視為一種「後向邊」。
* 前向邊 (Forward Edge)：從 DFS 樹中的一個節點 $u$ 指向其 DFS 樹中的某個後代節點 $v$ 的邊。
* 橫向邊 (Cross Edge)：連接 DFS 樹中兩個不具有祖孫關係的節點的邊。
* 在無向圖中：
* DFS 產生的邊可以分為：
* 樹邊 (Tree Edge)：當 DFS 從 $u$ 到達未訪問的 $v$ 時。
* 後向邊 (Back Edge)：當 DFS 從 $u$ 到達一個已訪問但不是 $u$ 的父節點的鄰居 $v$ 時。在無向圖中，任何一條非樹邊必然是後向邊（因為如果 $(u,v)$ 是非樹邊，且 $u$ 先於 $v$ 被訪問，則 DFS 在訪問 $u$ 時會發現 $v$ 已被訪問，形成後向邊；如果 $v$ 先於 $u$ 被訪問，則 DFS 在訪問 $v$ 時會發現 $u$ 已被訪問，形成後向邊）。
* 橫向邊 (Cross Edge) 在無向圖的 DFS 中不存在。這是因為如果存在一條連接兩個不同分支的邊 $(u, v)$，假設 $u$ 先被訪問，那麼 DFS 會從 $u$ 訪問 $v$（如果 $v$ 未訪問），形成樹邊；或者 $v$ 已經被訪問，並且 $v$ 是 $u$ 的祖先（形成後向邊），或者 $v$ 已經被完全訪問過，且 $v$ 不是 $u$ 的祖先。然而，在無向圖中，如果 $v$ 已經被訪問過（無論是 VISITING 還是 VISITED 狀態），並且 $v$ 不是 $u$ 的父節點，那麼這條邊 $(u, v)$ 就會被 DFS 在遍歷 $u$ 時發現，並將 $v$ 視為一個已訪問的節點。如果 $v$ 處於 VISITING 狀態，則為後向邊。如果 $v$ 處於 VISITED 狀態，這意味著 $v$ 所在的 DFS 樹分支已經完成，並且 DFS 在遍歷 $u$ 時發現了這條邊。在無向圖中，這種情況下 $v$ 必定是 $u$ 的祖先（如果 $v$ 比 $u$ 先訪問），或者 $v$ 已經被完全訪問過。如果 $v$ 是 $u$ 的祖先，則為後向邊。如果 $v$ 已經被完全訪問，並且 $v$ 不是 $u$ 的祖先，這在無向圖的 DFS 中是不會發生的，因為如果 $v$ 在 $u$ 的 DFS 樹之外，DFS 會在某個時候訪問到 $v$ 的連通分量，並將其標記為 VISITED。如果在 DFS 過程中，我們從 $u$ 遇到一個已訪問的 $v$ (且 $v$ 不是父節點)，那麼 $v$ 必定是 $u$ 的祖先，這就是後向邊。

這題考驗對主定理 (Master Theorem) 的應用。主定理用於分析遞迴關係式為 $T(n) = aT(n/b) + f(n)$ 形式的遞迴演算法的時間複雜度。

主定理的條件：
給定遞迴關係式 $T(n) = aT(n/b) + f(n)$，其中 $a \ge 1$, $b > 1$ 是常數，且 $f(n)$ 是一個漸進正函數。我們比較 $f(n)$ 與 $n^{\log_b a}$。有三種情況：

1. 情況 1：如果 $f(n) = O(n^{\log_b a - \epsilon})$ 對於某個常數 $\epsilon > 0$，則 $T(n) = \Theta(n^{\log_b a})$。
2. 情況 2：如果 $f(n) = \Theta(n^{\log_b a} \log^k n)$ 對於某個常數 $k \ge 0$，則 $T(n) = \Theta(n^{\log_b a} \log^{k+1} n)$。
3. 情況 3：如果 $f(n) = \Omega(n^{\log_b a + \epsilon})$ 對於某個常數 $\epsilon > 0$，並且對於足夠大的 $n$，滿足 $af(n/b) \le c f(n)$ 對於某個常數 $c < 1$（稱為規則性條件），則 $T(n) = \Theta(f(n))$。

分析給定的遞迴關係式：
$T(n) = T(2n/3) + 1$

1. 確定參數：

   • $a = 1$ (遞迴調用的次數)
   • $b = 3/2$ (輸入規模的縮小因子，因為 $n/b = n/(3/2) = 2n/3$)
   • $f(n) = 1$ (除了遞迴調用之外的工作)

2. 計算 $n^{\log_b a}$：

   • $\log_b a = \log_{3/2} 1 = 0$。
   • 所以，$n^{\log_b a} = n^0 = 1$。

3. 比較 $f(n)$ 和 $n^{\log_b a}$：

   • $f(n) = 1$
   • $n^{\log_b a} = 1$
   • 我們發現 $f(n) = 1$ 和 $n^{\log_b a} = 1$ 是相同的。

4. 選擇主定理的情況：

   • 情況 1 不適用，因為 $f(n)$ 不是 $n^{\log_b a}$ 的 $O(n^{\log_b a - \epsilon})$。
   • 情況 3 不適用，因為 $f(n)$ 不是 $n^{\log_b a}$ 的 $\Omega(n^{\log_b a + \epsilon})$。
   • 情況 2 適用。我們需要檢查 $f(n)$ 是否是 $n^{\log_b a} \log^k n$ 的形式。
     • $f(n) = 1$
     • $n^{\log_b a} = 1$
     • 所以，$f(n) = 1 \times \log^0 n$。這符合情況 2 的形式，其中 $k=0$。

5. 應用情況 2 的結論：

   • 根據主定理情況 2，當 $f(n) = \Theta(n^{\log_b a} \log^k n)$ 時， $T(n) = \Theta(n^{\log_b a} \log^{k+1} n)$。
   • 在這裡，$a=1, b=3/2, \log_b a = 0$, $f(n)=1$, $k=0$。
   • 因此，$T(n) = \Theta(n^0 \log^{0+1} n) = \Theta(1 \times \log^1 n) = \Theta(\log n)$。

驗證規則性條件（情況 3 的要求，但這裡適用情況 2）：
雖然我們適用情況 2，但主定理的嚴格形式要求我們檢查情況 3 的規則性條件。

• $f(n) = 1$
• $a f(n/b) = 1 \times f(2n/3) = 1 \times 1 = 1$
• $c f(n) = c \times 1 = c$
• 我們需要檢查 $a f(n/b) \le c f(n)$，即 $1 \le c \times 1$。
• 我們可以選擇 $c=1$（或任何 $c \ge 1$）。如果 $c=1$，則 $1 \le 1$，條件滿足。
• 然而，情況 2 的規則性條件是 $af(n/b) \le c f(n)$ 對於 $c<1$。

核心觀念

廣度優先搜尋（Breadth-First Search, BFS）從起點開始，依距離分層拜訪：

• 第 $0$ 層：起點 $0$
• 第 $1$ 層：與 $0$ 相鄰的節點
• 第 $2$ 層：由第 $1$ 層首次發現的節點
• 依此類推

每個節點「第一次被發現」時，便將目前節點與它連成 spanning tree 的樹邊。題目要求較小編號優先，因此掃描鄰接節點時依編號遞增排列。

解題方法

由圖可讀得與本題相關的鄰接關係：

$$\begin{aligned} 0&:\{1,2,3\}\\ 2&:\{0,4,5,6\}\\ 3&:\{0,6\}\\ 4&:\{2,7\}\\ 5&:\{2,7\}\\ 6&:\{2,3\}\\ 7&:\{4,5\} \end{aligned}$$

依 BFS 佇列順序處理：

1. 從 $0$ 開始，依序發現 $1,2,3$，加入樹邊
   $(0,1),(0,2),(0,3)。$

2. 處理節點 $1$，沒有新的未拜訪節點。

3. 處理節點 $2$，依小編號優先發現 $4,5,6$，加入樹邊
   $(2,4),(2,5),(2,6)。$

4. 處理節點 $3$ 時，節點 $6$ 已經被節點 $2$ 發現，因此不再新增樹邊。

5. 處理節點 $4$ 時發現節點 $7$，加入樹邊
   $(4,7)。$

因此各層與父節點如下：

層級	節點	BFS 父節點
第 0 層	$0$	—
第 1 層	$1,2,3$	$0$
第 2 層	$4,5,6$	$2$
第 3 層	$7$	$4$