Networks

歡迎來到網絡的世界！

你好！在本章中，我們將探索網絡 (Networks)，這是演算法建模 (Modelling with Algorithms) 單元的核心部分。你可能每天都在使用網絡卻不自知——每當你使用 GPS 尋找回家的最快路徑，或是快遞公司規劃如何將包裹送到你手中時，他們所使用的正是我們即將學習的演算法。如果一開始覺得這些概念有點抽象也不用擔心，我們會把它們拆解成簡單的步驟，並與日常生活聯繫起來！

1. 圖論與網絡的語言

在我們解決問題之前，必須先學會當中的「語言」。圖 (Graph) 只是一組點和線的集合。當我們為這些線加上「權重」（例如距離或成本）時，它就成了網絡 (Network)。

你需要知道的關鍵術語：

• 節點 (Node 或 Vertex)： 圖上的點，通常代表一個位置（例如城市）。
• 弧 (Arc 或 Edge)： 連接兩個節點的線，代表路徑或連結。
• 權重 (Weight)： 分配給弧的數值，代表成本、時間或距離。
• 節點的階 (Order 或 Degree)： 連接到該節點的弧的數量。
• 簡單圖 (Simple Graph)： 沒有環（即沒有連接節點自身的弧），且兩個節點之間沒有多條弧的圖。
• 連通圖 (Connected Graph)： 可以通過弧從任何一個節點到達另一個節點。
• 二分圖 (Bipartite Graph)： 一種圖，其節點被分為兩個集合，且弧只連接不同集合中的節點（可以想像成「工人」和「工作」）。
• 有向圖 (Digraph)： 「Directed Graph」的簡稱——弧帶有箭頭，表示你只能單向行進。

記憶小貼士：用「社交媒體」作類比

想像節點是人，弧是「友誼」。在簡單圖中，你們要麼是朋友，要麼不是。在有向圖中，這就像 Instagram 上的「追蹤」功能——你可能會追蹤某人（箭頭指向他們），但他們不一定會追蹤你！

快速回顧： 關聯矩陣 (Incidence Matrix) 只是一張顯示哪些節點相連的表格。如果節點 A 和節點 B 被一條權重為 5 的弧連接，你就在 A 行和 B 列的交點處填入 '5'。

重點總結： 圖是骨架；網絡是附加了數據（權重）的骨架。

2. 最短連接問題 (MST)

想像你要鋪設光纖電纜連接五個村莊。你希望每個人都能連上網絡，但電纜很昂貴，所以你希望電纜的總長度盡可能短。這就是最小生成樹 (Minimum Spanning Tree, MST) 問題。

Kruskal 演算法（圖形化操作）

這是一種「邊優先」的方法。你不需要在意從哪裡開始！
第一步： 將所有弧按長度從短到長排序。
第二步： 選擇最短的弧。
第三步： 選擇下一條最短的弧。注意： 如果選擇某條弧會產生迴路 (Cycle)（封閉的環），則跳過它！
第四步： 重複上述步驟，直到所有節點都連接起來。

Prim 演算法（圖形或列表操作）

這是一種「節點優先」的方法。它像樹一樣從起點開始生長。
第一步： 選擇任何一個起始節點。
第二步： 查看所有連接到你已經「獲取」的節點的弧。選擇其中連接到一個新節點的最短弧。
第三步： 重複步驟，直到所有節點都被納入你的樹中。

你知道嗎？ Kruskal 和 Prim 演算法的複雜度均為二次方 \(O(n^2)\)。這意味著如果你將邊的數量增加一倍，電腦求解所需的時間大約會增加為原來的四倍！

重點總結： Kruskal = 隨處挑選最短的邊。Prim = 從起點向外生長。只需記住：絕不產生迴路！

3. 最短路徑：Dijkstra 演算法

這是「Google Maps」背後的演算法。它能找出從一個特定的起始節點到網絡中所有其他節點的最短距離。

步驟拆解：

1. 將起始節點標記為距離 0，並將其設為「永久 (permanent)」。
2. 更新所有連接到剛變為永久節點的節點的「工作值 (working values)」。
3. 查看整個網絡中所有工作值。選擇具有最小工作值的節點，將其變為下一個永久節點。
4. 重複此過程，直到你的目的地節點變為永久。

常見錯誤： 學生往往只查看當前節點連接的節點。你必須查看整個網絡，找到下一個最小值，才能將其設為永久！

重點總結： Dijkstra 是貪婪的——它總是選擇下一個最近的「未訪問」節點。它在頂點數量上同樣具有二次方複雜度。

4. 關鍵路徑分析 (CPA)

這用於項目管理，例如建造房屋。有些工作必須等其他工作完成後才能開始。我們使用弧上作業 (Activity-on-Arc) 圖，其中弧是作業，節點是「事件」（時間點）。

兩個運算過程：

• 前向傳遞 (Forward Pass)： 計算最早開始時間 (Earliest Event Time, EET)。當多條路徑匯合到一個節點時，取最大值。（想像：「在牆壁和鷹架都完成之前，我無法開始蓋屋頂」）。
• 後向傳遞 (Backward Pass)： 計算最晚結束時間 (Latest Event Time, LET)。當向後推算時，取最小值。（想像：「我必須在星期二之前開始這項工作，否則整個項目都會延誤」）。

理解浮動時間 (Float)：

浮動時間是活動的「緩衝空間」。如果一個活動在關鍵路徑 (Critical Path) 上，它的浮動時間就是零。如果它延誤了，整個項目都會延誤！
\(Total Float = LET_{end} - EET_{start} - Duration\)

重點總結： 關鍵路徑是網絡中最長的路徑。它決定了完成項目所需的最短時間。

5. 網絡流 (Network Flows)

這模擬了如水管中的水流或道路上的車流。你有一個源點 (Source, S) 作為起點，以及一個匯點 (Sink, T) 作為終點。

流量規則：

1. 容量 (Capacity)： 通過弧的流量不能超過其容量。
2. 守恆 (Conservation)： 對於每個節點（S 和 T 除外），流入量 = 流出量。

最大流最小割定理 (Max-Flow Min-Cut Theorem)：

割 (Cut) 是一條將源點與匯點完全分開的線。割的容量是其穿過的所有弧的容量之和（僅計算從 S 側指向 T 側的弧）。
重要規則： 網絡中的最大流量等於最小割 (Minimum Cut) 的容量。

類比： 想像一系列水管。輸送到你家的水量受限於「瓶頸」——即整個系統中最細的那段水管。那個瓶頸就是你的最小割！

重點總結： 要找到最大流量，請尋找「瓶頸」（最小割）。流入接點的總量必須始終等於流出量。

6. 線性規劃建模 (LP)

雖然我們可以手動解決這些問題，但電腦會使用線性規劃 (Linear Programming) 來處理大型網絡。你為每一條弧定義變數（例如，令 \(x_{AB}\) 為從 A 到 B 的流量）。
• 對於最短路徑： 你最小化（距離 \(\times\) 變數）的總和。
• 對於最大流： 在滿足容量限制的前提下，最大化從源點流出的總流量。

重點總結： 複雜的網絡問題可以轉換為方程式，讓軟體（如 Excel Solver）瞬間求解！

最後的鼓勵

網絡剛開始看起來可能只是一堆方塊和線條，但它們本質上就是邏輯謎題。練習畫出這些圖表——當你的圖形整潔清晰時，要看出「最小割」或「關鍵路徑」會容易得多！你可以做到的！