歡迎來到網絡流（Flows in Networks）！
在本章中，我們將學習如何管理系統中的「流量」。無論是管道中的水流、互聯網上的數據，還是高速公路上的車輛，目標都是一樣的：如何在不弄垮系統的前提下，將最多的資源從起點運送到終點？
這是決策數學 2（Decision Mathematics 2）的核心部分。一旦你掌握了「標記法（labelling）」的節奏，你會發現這其實很有成就感。如果一開始看到滿滿的箭頭和數字覺得很混亂，別擔心——我們會一步步拆解它！
1. 網絡的解剖
在我們開始處理流量之前，必須先了解我們面對的是什麼。在本課程大綱中，我們只處理有向弧（directed arcs）（即顯示流動方向的箭頭）。
- 源點（Source, S）：流動的起點（就像「水龍頭」）。
- 匯點（Sink, T）：流動的終點（就像「排水口」）。
- 容量（Capacity）：一條弧所能承載的最大流量。你可以把它想像成管道的粗細。
- 可行流（Feasible Flow）：必須遵循兩條規則的流動：
1. 不超過任何弧的容量。
2. 流量守恆（Conservation of Flow）：流入頂點的流量必須等於流出的流量（源點和匯點除外）。
小複習：如果有 10 公升的水流進一個交匯點，就必須有 10 公升流出。你不能讓水在網絡中間憑空消失！
2. 割（Cuts）及其容量
割（Cut）就像是一條虛擬的線，將源點與匯點完全隔開。如果你「切斷」這些被割穿過的弧，流動就無法到達終點。
如何計算割的容量
要找到割的容量，你只需將所有從源點那一側指向匯點那一側的弧的容量加起來即可。
常見錯誤：如果一條弧是從「匯點側」往「源點側」（即反方向）穿過割線，我們必須忽略它的容量。我們只關心那些有助於流量到達匯點的部分！
重點總結：割的容量 = \(\sum (\text{所有從源點側指向匯點側的弧的容量})\)。
3. 標記程序（The Labelling Procedure）
這是本章的「重頭戲」。我們利用這個程序來增廣（augment）（增加）流量，直到找到最大可能流量為止。想像一下，你現在有一個半滿的管道系統；這個程序能幫你找到那些「縫隙」，從而塞入更多的流量。
兩個箭頭
在每一條弧上，我們使用包含兩個數字和兩個箭頭的標記：
- 前向箭頭（\(\rightarrow\)）：顯示我們還能增加多少流量。計算方式為 \(\text{容量} - \text{當前流量}\)。
- 後向箭頭（\(\leftarrow\)）：顯示我們可以「移除」或重新導向多少流量。這單純等於 \(\text{當前流量}\)。
增廣步驟
- 尋找路徑：尋找任何一條從 S 到 T 的路徑，且路徑上所有的「前向箭頭」數值都大於零。
- 確定增加量：找出該路徑上最小的前向箭頭數值。我們稱這個值為 \(x\)。
- 更新標記：
- 對於路徑上的每一條弧，從前向箭頭中減去 \(x\)。
- 對於路徑上的每一條弧，在後向箭頭上加上 \(x\)。 - 重複：持續進行上述步驟，直到沒有任何從 S 到 T 且具備「前向空間」的路徑為止。
你知道嗎？即使一條弧在某個方向看起來已經「滿了」，你偶爾也可以通過後向箭頭「推回」流量，從而開闢出一條更好的路徑！
4. 最大流最小割定理（Max-Flow Min-Cut Theorem）
這是決策數學中一個著名的規則，它指出：
網絡中的最大流（Maximum Flow）等於最小割（Minimum Cut）的容量。
如果你找到了一個流量（使用標記程序），並且發現剛好有一個割的容量值與之相等，那麼你就已經證明了你的流量就是該網絡的最大流量。
重點總結：要證明你找到了最大流，試著找出網絡中的「瓶頸」。那個瓶頸就是你的最小割。
5. 處理變化題型
有時考題會給你一個「混亂」的網絡。以下是整理它們的方法：
多個源點與匯點（3.4）
如果你有三個工廠（源點）和兩個商店（匯點），別慌！
- 創建一個超級源點（Super-Source），並畫弧線連接到原本的源點。這些新弧的容量就是工廠能產出的總容量。
- 同樣地，創建一個超級匯點（Super-Sink），並將原本的匯點連接到它。
頂點容量限制（3.4）
有時一個交匯點（頂點）只能處理一定量的流量（例如：一個抽水站一次只能處理 50 個單位）。
技巧：將該頂點一分為二！頂點 \(V\) 變成 \(V_{in}\) 和 \(V_{out}\)。用一條容量等於該頂點限制值的弧將它們連接起來。
類比：想像一家夜店。頂點就是門口。要模擬門口的容量，你必須從「門外」(\(V_{in}\)) 通過「身份查驗」（容量弧）進入「店內」(\(V_{out}\))。
6. 下限容量（3.5）
在大多數問題中，流量的下限是零。但有時一條弧必須承載一定的最低流量（即下限容量）。
在這些情況下，弧上的流量 \(f\) 必須滿足：
\(\text{下限容量} \leq f \leq \text{上限容量}\)
在檢查「可行流」時，你必須確保每一條弧都維持在其特定的邊界之內。
常見錯誤提示
- 「反向」割：在計算割的容量時，錯誤地加總了指向源點側的弧。千萬別這樣做！
- 算術錯誤：在增廣標記時，加減法非常容易出錯。進行增廣時請務必反覆檢查你的減法運算。
- 漏掉路徑：請務必仔細掃描整個網絡。有時候，包含「後向箭頭」的路徑反而是達到最大流量的唯一途徑。
最後鼓勵：決策數學的重點在於遵循算法。保持你的圖表清晰，使用鉛筆以便隨時擦掉錯誤的標記，並記住黃金法則：流入 = 流出！ 你一定做得到的！