歡迎來到網絡流（Flows in Networks）！
你好！歡迎來到 Decision Mathematics 2 中最實用的章節之一。你有沒有想過，在熱浪襲擊時，水務公司是如何確保每個人都有足夠的水用？或者互聯網數據是如何從伺服器傳輸到你的手機而不崩潰的？這正是網絡流所探討的主題！
在本章中，我們將學習如何利用「網絡」來構建這些系統的模型，並找出能從起點移動到終點的「東西」（如水、數據、車輛）的絕對最大流量。別擔心，一開始看到滿滿的線條和數字可能會覺得頭昏腦脹——我們會一步步帶你拆解！
1. 基本概念：什麼是流網絡？
在我們開始「切割」網絡或為節點「標記」之前，先確保我們看懂這張地圖。流網絡是一個有向圖（由箭頭連接的點的集合），其中每個箭頭都有一個限額。
你需要知道的關鍵術語：
- 源點 (Source, S)：一切事物的起點（就像水庫一樣）。
- 匯點 (Sink, T)：一切事物的目的地（就像你家裡的廚房水龍頭）。
- 弧 (Arc 或 Edge)：連接各點的管道或道路。在本課程大綱中，我們只討論有向弧（單行道）。
- 容量 (Capacity)：一條弧能處理的最大流量。例如，如果一條弧的容量是 \(10\)，你就不能讓 \(11\) 個單位通過它。
- 流量 (Flow)：目前實際在弧中移動的數量。
快速回顧：把網絡想像成一套管道系統。容量是水管的寬度，而流量則是實際流過的水量。
重要規則：在每個節點（除了源點和匯點外），流入量 = 流出量。你不能讓水在管道中途憑空消失！
重點總結：網絡展示了根據兩點之間單行道的容量，有多少「東西」能從源點 (S) 移動到匯點 (T)。
2. 割（Cuts）及其容量
想像一下，如果你想阻斷所有通往匯點的流量，你會在哪裡下剪刀「割」開這個網絡？在數學中，割 (cut) 是一種將網絡分成兩個獨立部分的方法。
什麼是「割」？
割將節點劃分為兩個集合：集合 X（包含源點 \(S\)）和 集合 Y（包含匯點 \(T\)）。要成為一個有效的「割」，必須切斷所有從 \(S\) 到 \(T\) 的路徑。
計算「割」的容量
這是許多學生容易被絆倒的地方，所以要專心聽！割的容量是指從 集合 X 指向集合 Y 的所有弧的容量總和。
要避免的常見錯誤：如果一條弧是「反向」的（從集合 Y 指回集合 X），我們在計算割的值時要忽略它的容量。我們只關心那些試圖穿過「圍牆」向匯點前進的管道。
類比：想像集合 X 是「家」，集合 Y 是「商店」。如果你正在築圍欄以阻止人們進入商店，你只會關心那些讓人們前進的門，而不會去數那些只讓人們走回家的門！
你知道嗎？任何割的容量總是大於或等於任何流量的值。這將導向我們稍後要學習的一個非常著名的定理！
重點總結：割的容量 = 從源點側 (X) 跨越到匯點側 (Y) 的弧的容量總和。忽略所有反向的弧。
3. 標記程序（流量增廣）
現在進入「實作」部分！我們該如何增加網絡中的流量呢？我們會使用標記程序 (labelling procedure) 來尋找「增廣路徑 (breakthrough paths)」。
步驟詳解：如何增加流量
1. 找到初始流量：通常題目會給你一個起始流量。檢查每個節點是否滿足「流入量 = 流出量」。
2. 尋找路徑：在網絡中找出一條尚未飽和、從 \(S\) 到 \(T\) 的路徑。
3. 使用標記：在每個節點，我們使用箭頭來顯示我們可以改變多少流量：
• 前向箭頭：方向與弧的方向相同。它顯示該弧還能容納多少額外流量（容量 - 目前流量）。
• 後向箭頭：方向與弧的方向相反。它顯示我們可以從該弧移除多少流量（目前流量）。
4. 增加流量：找出所選路徑上最小的「潛力值」，並將該數量加到整條路徑的流量上。
5. 重複：持續重複此步驟，直到你無法再找到從 \(S\) 到 \(T\) 的路徑為止。
記憶小撇步：如果你很難記住箭頭的方向，記住這句口訣：「前向填滿，後向溢出 (Forward to fill, Backward to spill)。」
重點總結：我們利用標記來查看管道中還有多少「空間」。一旦無法再找到擁有剩餘「空間」的路徑，我們就達到了最大流量！
4. 最大流最小割定理 (Max-Flow Min-Cut Theorem)
這是流量問題的「黃金法則」。它是一個強大的工具，能幫助我們證明我們已經找到了最佳答案。
定理：在任何網絡中，最大流量 (Maximum Flow) 的值等於最小割 (Minimum Cut) 的容量。
如何在考試中運用：
如果考題要求你「證明你的流量是最大的」，你應該：
1. 說明你最終的流量值。
2. 在網絡中找到一個割，其容量恰好等於你的流量值。
3. 提及最大流最小割定理。如果「流量 = 割的容量」，那麼該流量必定是可能的最大值。
如果一開始覺得很難，別擔心！尋找「最小割」通常就像尋找瓶頸。查看網絡中所有管道都完全飽和（飽和狀態）的部分。那通常就是最小割隱藏的地方！
快速回顧框：
• 最大流 = 可移動的最大物品數量。
• 最小割 = 最小的「瓶頸」容量。
• 它們在最後總是相等的！
重點總結：「瓶頸」（最小割）限制了可以通過系統的「流量」（最大流量）總額。
總結檢查清單
在進入練習題之前，請確保你能：
• 識別源點 (Source) 和 匯點 (Sink)。
• 計算割的容量（記得忽略反向的弧！）。
• 使用標記法來增加路徑上的流量。
• 使用最大流最小割定理來驗證你的最終答案。
你一定做得到的！網絡流起初看起來可能像一張混亂的網，但一旦你找到了路徑和瓶頸，一切就會像完美的拼圖一樣拼湊在一起。