歡迎來到網絡世界！

你好！歡迎來到進階數學（Further Mathematics）中最實用且直觀的章節之一：網絡 (Networks)。本章屬於運算建模 (Modelling with Algorithms) 的一部分。你將學習如何將現實生活中的問題——例如尋找回家的最快路線或管理管道中的水流——轉化為圖表，並透過邏輯步驟（即演算法）來解決。

如果起初覺得有點抽象，別擔心。你可以將網絡想像成一張地圖，我們剔除了不必要的細節，只專注於連接 (connections) 和成本 (costs)。讓我們開始吧！

1. 圖論的語言

在我們解決問題之前，必須先學會當中的「語言」。在數學中，「圖」(graph) 並不是指帶有 x 軸的圖表，而是一組點與線的集合。

關鍵術語

  • 節點 (Node 或 Vertex)： 圖表中的「點」。它們通常代表地點（如城市或電腦伺服器）。
  • 弧 (Arc 或 Edge)： 連接節點的「線」。它們代表節點之間的路徑。
  • 節點的階 (Order 或 Degree)： 連接到該特定節點的弧的數量。
  • 樹 (Tree)： 一個沒有迴路 (cycles) 的連通圖。可以想像成家譜——沒有任何路徑會繞成一個圓圈！
  • 有向圖 (Digraph)： 「Directed Graph」的簡稱。在這種圖中，弧具有方向箭頭，表示你只能沿特定方向移動。

圖的特殊類型

  • 簡單圖 (Simple Graph)： 沒有環（連接節點到自身的弧），且同一對節點之間沒有多條弧。
  • 完全圖 (Complete Graph)： 每一個節點都與其他所有節點相連。
  • 連通圖 (Connected Graph)： 你可以沿著弧從任何一個節點到達其他任何節點。
  • 二分圖 (Bipartite Graph)： 節點被分成兩組，弧只連接不同組中的節點。類比：想像一張「工人」清單和一張「工作」清單。你只會在工人與工作之間連線，絕不會在兩個工人之間連線。

關聯矩陣 (Incidence Matrix)

有時候，繪製圖表會很混亂。關聯矩陣是一個表格，顯示哪些節點由哪些弧連接。這是讓電腦在沒有圖形的情況下「看見」圖表的一種方式。

重點小結： 節點是「在哪裡」，弧是「怎麼走」，而樹是一種沒有圓圈的簡單路徑。

2. 權重與網絡

在現實世界中，並非所有路徑都是平等的。有些道路較長，有些管道較寬。

網絡 (Network) 其實就是一個每個弧都被賦予權重 (weight)（一個數值）的圖。這些權重可以代表距離、時間、成本或容量。

你知道嗎？ 每當你要求導航尋找「最快路線」時，你的 GPS 就在使用權重網絡。而權重就是每條道路的預估行車時間！

3. 最小連接問題

想像你正在鋪設光纖電纜以連接五個村莊。你希望每個人都能連接起來，但電纜很昂貴，所以你想要總長度最小。這就是最小生成樹 (Minimum Spanning Tree, MST)。

克魯斯克爾演算法 (Kruskal’s Algorithm，即「貪婪」策略)

Kruskal’s 演算法很簡單：永遠選擇當下最便宜的選項！

  1. 將網絡中所有的弧按權重從小到大排序。
  2. 選擇權重最小的弧並將其添加到樹中。
  3. 選擇下一個最小的弧。關鍵規則： 如果選定的弧會構成迴路 (cycle)（封閉迴圈），則不能選擇它。
  4. 重複上述步驟，直到所有節點都已連通。

普林演算法 (Prim’s Algorithm，即「擴張」策略)

Prim’s 演算法像植物生長根系一樣，每次增加一個節點來構建樹。

  1. 從任何一個節點開始（通常題目會指定）。
  2. 查看所有與你已到達的節點相連的弧。
  3. 選擇連接到一個新節點且權重最小的弧。
  4. 重複此步驟，直到每個節點都包含在樹中。

記憶小撇步：Prim’s 從 Point（點）開始；Kruskal’s 從弧的 Kosts（成本/權重）開始。

重點小結： 兩種演算法都會給你相同的最小總權重。Kruskal’s 會檢視整個弧列表；Prim’s 則是從起始節點向外擴張。

4. 戴克斯特拉演算法 (Dijkstra’s Algorithm，最短路徑)

這用於尋找從特定起點到終點的最短路徑。與 MST 不同，我們只在乎距離起點有多遠。

邏輯步驟：

  1. 設定起始節點的距離為 0，所有其他節點的距離為「無限大」。
  2. 從當前節點出發，更新到所有相鄰節點的距離。（新距離 = 到當前節點的距離 + 弧的權重）。
  3. 如果新計算的距離比舊的短，就記下來！
  4. 一旦檢查完所有鄰居，將當前節點標記為「已訪問」。以後不再回到該節點。
  5. 選擇未訪問且具有最小暫時距離的節點，將其設為新的當前節點。
  6. 重複此過程，直到到達終點。

常見錯誤： 學生經常選擇權重最小的那個弧。請記住，Dijkstra’s 關注的是從起點開始的總距離，而不僅僅是下一步的距離！

5. 演算法複雜度

在進階數學 (MEI) 中，我們關心電腦處理問題的「難度」，這稱為複雜度 (Complexity)。

  • Kruskal’s 與 Prim’s： 具有二次複雜度 (quadratic complexity)，記作 \(O(n^2)\)，其中 \(n\) 是邊的數量。
  • Dijkstra’s： 同樣具有二次複雜度 \(O(n^2)\)，但它是關於頂點 (vertices) 數量的函數。

什麼是 \(O(n^2)\)？ 如果網絡規模翻倍 (\(2n\))，解決問題所需的時間大約會變成原來的四倍 (\(2^2 = 4\))。

6. 網絡流 (Network Flows)

現在，想像弧是管道，權重是容量 (capacities)（流過其中的水或數據的最大總量）。

源頭與匯點

  • 源點 (Source, S)： 流動開始的地方。
  • 匯點 (Sink, T)： 流動結束的地方。
  • 規則： 對於其他任何節點，流入量必須等於流出量。（中間不會有東西卡住！）

截集與容量

截集 (Cut) 是一條能將源點與匯點完全分開的線。截集的容量是所有從 S 側流向 T 側的弧的容量總和。

注意： 如果一條弧從 T 側流回 S 側，我們在計算截集值時會忽略它的容量（即視為 0）。

最大流/最小截集定理 (Max Flow / Min Cut Theorem)

這是網絡中的「黃金法則」：網絡中的最大可能流量等於最小截集的容量。

如果你找到一個流量為 20 的流，且同時找到一個容量為 20 的截集，你就證明了 20 就是絕對的最大流量！

重點小結： 最大流量受到系統中「瓶頸」（即最小截集）的限制。

7. 使用科技解決網絡問題

在現實世界中，網絡擁有成千上萬個節點。我們透過將其轉化為線性規劃 (Linear Programming, LP) 問題來解決。

對於最短路徑問題，我們通常會設立方程，其中：

  • 目標是最小化 (Minimise) 總距離。
  • 變量代表弧是否被使用（1 代表使用，0 代表不使用）。
  • 約束條件確保我們正確地進入和離開節點。

不用擔心要親手解這些複雜方程；課程大綱重點在於你能否構建 (formulate) 方程，以及解釋 (interpret) Excel 或 Simplex 解算器等軟體輸出的結果。

最後的鼓勵

網絡問題就像拼圖。一旦你掌握了 Dijkstra’s 或 Prim’s 的「節奏」，解題會變得非常有成就感。務必清楚繪製圖表、反覆檢查加法，並記住：演算法不過是數學的食譜罷了！