網絡流簡介
歡迎來到網絡流 (Network Flows) 的世界！這一章的核心在於如何最有效率地將「物資」從一個地方傳送到另一個地方——無論是水管中的水、互聯網上的數據，還是道路上的車流。如果你曾經好奇城市是如何管理交通，或者 Netflix 是如何同時向數百萬人串流播放電影而不令系統崩潰的，那你其實已經在思考網絡流的問題了。
如果起初覺得這些概念有點抽象，請別擔心！我們會將其拆解為簡單的步驟，並運用大量的比喻來幫助你想像其中的運作機制。學完這一章，你就會成為找出任何系統中「瓶頸 (bottlenecks)」的專家！
1. 基本概念：節點、弧與容量
在開始分析流動之前，我們需要先認識地圖上的各個組成部分。在離散數學中，我們將這張地圖稱為網絡 (network)（或有向圖）。
節點 (Nodes，或稱頂點 Vertices)： 這些是圖中的圓圈或點，可以想像成路口或城市。
弧 (Arcs，或稱邊 Edges)： 這是連接節點的線。在這一章中，它們總是有箭頭的，因此稱為有向弧 (directed arcs)。可以想像成單行道。
源點 (Source, S)： 流動的起點。可以想像成「水塔」或「工廠」。
匯點 (Sink, T)： 流動的終點。可以想像成「住家」或「客戶」。
容量 (Capacity)： 每一條弧都有一個上限，代表該路徑能通過的「物資」最大量。我們通常會在弧的旁邊標註這個數值。
黃金法則：流守恆定律 (Conservation of Flow)
對於除源點和匯點外的每一個節點，進入該節點的總流量必須等於離開該節點的總流量。你不可能讓水在管道系統的中途憑空消失！
快速重溫：關鍵術語
源點 (S)： 起點。
匯點 (T)： 終點。
容量： 弧的流量上限。
流量 (Flow)： 當前通過該弧的實際數量（流量 \( \le \) 容量）。
2. 理解割集 (Cuts)
想像你想通過「切斷」某些管道來完全阻斷從源點到匯點的流動。割集 (cut) 是一條線，它將節點劃分為兩個集合：一個集合包含源點，另一個包含匯點。
割集的值 (Value of a Cut)：
割集的值等於所有從「源點側」指向「匯點側」的弧的容量之和。
重要提示： 如果某條弧是「反向」的（即從匯點側指向源點側），我們在計算割集值時會忽略它的容量。我們只關心那些試圖穿過「缺口」前往終點的流量。
你知道嗎？
任何割集的值總是大於或等於實際流量的值。如果你找到一個值為 50 的割集，你就能肯定流量絕對不可能高於 50。
3. 最大流最小割定理 (Maximum Flow-Minimum Cut Theorem)
這是本章最重要的定理。它指出在任何網絡中：
\( \text{最大流} = \text{最小割的值} \)
比喻：鏈條與最弱的一環
將網絡想像成一連串的鏈條。整個系統所能承受的最大重量取決於其最弱的一環。「最小割」就是數學上找出整個網絡中最終瓶頸的方法。
關鍵重點
如果你被要求證明某個流量是最大流，只需找到一個割集，其值等於該流量。如果兩者相等，你就成功找到了極限！
4. 超級源點與超級匯點
有時候題目會出現多個工廠（源點）或多個客戶（匯點）。這看起來很複雜，但有一個巧妙的解決方案：使用超級源點 (Supersources) 和超級匯點 (Supersinks)。
1. 創建一個單一的「超級」節點。
2. 使用無限容量（或等於總供應量/需求量的容量）的弧，將它連接到所有原始的源點（或匯點）。
3. 現在，你可以將此問題視為一個只有單一起點和單一終點的標準網絡來處理。
5. 增廣路徑 (Augmenting Flows)：如何達到最大值
為了找到最大流，我們使用一個稱為增廣 (augmenting) 的過程。這意味著「增加流量」。
逐步指南：
1. 從零流量開始。
2. 尋找一條從 S 到 T 的路徑，且該路徑上每一條弧都有剩餘容量。
3. 找出該路徑上的瓶頸（剩餘容量最小的弧）。我們稱此值為 \( x \)。
4. 將該路徑上每一條弧的流量增加 \( x \)。
5. 重複此過程，直到從 S 到 T 再也沒有具備剩餘容量的路徑為止。
常見錯誤： 千萬別忘了更新過程中的剩餘容量！如果一根管子的容量是 10，你通過了 4 個單位，那麼它以後就只剩下 6 個單位的容量可用。
6. 進階限制：上限與下限容量
在現實世界中，情況會複雜一些。
上限容量 (Upper Capacities)： 這是我們一直使用的——即最大限制。
下限容量 (Lower Capacities)： 有時候某條弧必須運載至少一定數量的流量。例如，發電廠可能需要向變電站輸送最低限度的電力以維持運作。
要解決這類問題，我們需要檢查是否存在一個同時滿足最低需求和最大限制的「可行流 (feasible flow)」。如果你覺得這很棘手，可以把它想像成在開始尋找額外空間之前，先將管子「預載」上所需的最低流量。
7. 節點容量
如果路口本身就是瓶頸怎麼辦？想像一個火車站，即使連接它的軌道能容納 1,000 名乘客，但車站本身每小時只能處理 500 名乘客。
技巧：節點分裂 (Node Splitting)
為了模擬具有容量限制的節點，我們將節點「分裂」為兩個由單一弧連接的節點。
1. 將節點 A 變為 A-in 和 A-out。
2. 所有進入 A 的弧現在改為進入 A-in。
3. 所有離開 A 的弧現在改為從 A-out 離開。
4. 創建一條從 A-in 到 A-out 的新弧，並將其容量設為該節點的容量限制。
現在，節點的限制就變成了另一條弧的容量，我們可以使用標準方法來求解了！
快速重溫：常見陷阱
- 方向很重要： 在計算割集時，只統計從源點側指向匯點側的弧容量。
- 瓶頸： 路徑的總流量受限於該路徑上最弱的弧，而不是所有弧的總和。
- 守恆： 最終檢查時，務必確認所有節點都符合「流入量 = 流出量」。
章節總結
網絡流是解決優化問題的強大工具。你已經學會了如何使用有向弧來呈現系統，如何透過割集識別瓶頸，以及如何使用最大流最小割定理來證明你找到了最佳解。無論你是處理超級源點還是受限的節點容量，核心原則始終如一：持續增加流量，直到達到極限為止！