網路最大流計算機

網路最大流計算機

這款網路最大流計算機可以計算任何帶容量的有向網路中，從選定的源點 s 到選定的匯點 t 的最大流。它底層運行帶有廣度優先增廣路徑的 Ford-Fulkerson 方法（即 Edmonds-Karp 演算法），並記錄找到的每一條路徑，讓您可以逐次迭代地重播整個決策過程。結果頁面還會顯示最小割 — 證明您的流量值確實是最優的瓶頸分區。

什麼是最大流問題？

流量網路是一個有向圖 G = (V, E)，連同一個容量函數 c: E → ℝ_≥0。其中區分了兩個頂點：源點 s（流量發源地）和匯點 t（流量消耗地）。流量 f 是分配在邊上的值 f(u, v) ≥ 0，且遵循：

最大流問題旨在尋找能使 |f| 最大化的流量 f。直觀來說：如果邊是具有給定容量的水管，您每秒可以從 s 運送多少公升的水到 t？

演算法原理 — 配合 BFS 的 Ford-Fulkerson

演算法在處理當前流量的同時維護一個剩餘圖。對於每條具有容量 c 和當前流量 f 的邊 (u, v)，剩餘圖包含：

• 一條前向剩餘邊 (u, v)，容量為 c − f（還能推送多少流量），以及
• 一條反向剩餘邊 (v, u)，容量為 f（可以抵消多少已承諾的流量）。

在每次迭代中，它會在剩餘圖上執行從 s 到 t 的廣度優先搜尋 (BFS)。如果找到路徑，則路徑上的最小邊容量（即瓶頸）會加到路徑上每條前向邊的流量中，並從每條反向邊的流量中減去。這被稱為增廣路徑。當 BFS 再次執行卻無法到達 t 時，當前流量即為最優解。

使用 BFS（而非任意路徑搜尋策略）將 Ford-Fulkerson 轉變為 Edmonds-Karp 演算法，其保證運行時間為 O(V · E²)。它還保證在邊容量為無理數時也能終止，而普通的 Ford-Fulkerson 則無法保證。

最大流最小割定理

割 (Cut) 是將頂點劃分為兩個集合 (S, T) 的分區，其中 s ∈ S 且 t ∈ T。其容量是從 S 到 T 的邊容量之和：

最大流最小割定理 (Ford & Fulkerson, 1956) 指出：

此工具會自動尋找最小割。在 Edmonds-Karp 終止後，它會在剩餘圖上從 s 執行最後一次 BFS；所到達的頂點形成 S，其餘頂點形成 T，且原始圖中所有橫跨 S → T 的邊都是飽和的。它們的容量之和恰好等於最大流值 — 在核心結果中顯示為「最小割容量 ✓ 確認最優性」。

專為學習設計的功能

• 逐步動畫演示： 使用播放、暫停和步進控制重播每個增廣路徑。查看 BFS 選擇了哪條路徑、哪條邊是瓶頸，以及累計流量是如何增長的。
• 三個同步矩陣： 在容量矩陣 C、最終流量矩陣 f 和剩餘流量矩陣 C − f 之間切換 — 這三張圖共同描述了任何流的特性。
• 最小割分區視圖： S 側和 T 側的頂點以標籤形式列出，並以紅色突出顯示橫跨其中的飽和邊。
• 逐邊流量表： 對於每條邊：容量、流量、剩餘量、利用率進度條和飽和狀態標籤。
• 分層左至右佈局： 圖表繪製是根據與源點的 BFS 距離計算的，因此流量在視覺上呈現從左向右「流動」的狀態 — 就像教科書上的畫法一樣。

輸入格式

1. 帶容量的邊列表

每行輸入一條邊。箭頭形式最易讀，但以下幾種替代方案也適用：

同樣接受：A, B, 10 · A B 10 · A -> B , 10。相同頂點對之間的多條邊將會被加總。

2. 容量矩陣

每行輸入一個橫列，數值以空格或逗號分隔。項目 C[i][j] 是從頂點 i 到頂點 j 的邊容量。使用 0 代表「無邊」。矩陣必須是正方形，且對角線必須為 0（不允許自環）。

在矩陣標籤欄位中輸入對應的頂點標籤（以逗號或空格分隔）。如果省略，標籤預設為 S, A, B, …, T。

最大流的應用

範例解析

「教科書」快速範例編碼了一個具有源點 S 和匯點 T 的 6 節點網路。執行 Edmonds-Karp 會產生四條增廣路徑：

1. S → A → B → T，瓶頸為 4（邊 A-B 是限制因素）。累計流量：4。
2. S → A → D → T，瓶頸為 6。累計流量：10。
3. S → C → D → T，瓶頸為 4（邊 D-T 現在是限制因素，僅剩 4）。累計流量：14。
4. S → C → D → B → T，瓶頸為 5。累計流量：19。

演算法停止 — 不再存在增廣路徑。最小割為 (S = {S, C}, T = {A, B, D, T})，橫跨邊為 S → A (容量 10) 和 C → D (容量 9)，總和為 19 — 恰好等於最大流值。

如何使用此計算機

1. 使用選項卡選擇輸入格式 — 邊列表（建議）或容量矩陣。
2. 輸入您的網路。 您可以從快速範例開始並進行修改。若使用矩陣輸入，如果您想要 S, A, B, …, T 以外的名稱，請提供標籤。
3. 指定源點和匯點（或留空以自動偵測 S 和 T）。
4. 點擊計算最大流。 結果頁面會顯示最大流值、最小割分區、分層圖表視覺化、每一條增廣路徑、邊利用率表以及三個矩陣（容量、流量、剩餘流量）。
5. 播放圖表下方的動畫以重播演算法的決策過程。點擊任何增廣路徑步驟可直接跳轉至該步驟。

限制

• 頂點數量： 最多 30 個 — 以保持視覺化和矩陣的可讀性。
• 邊數量： 最多 200 條。
• 容量： 非負數，最高可達 10⁹。允許小數容量。
• 無自環： 在標準最大流公式中，自環不攜帶流量，因此會被拒絕。

常見問題

什麼是最大流問題？

給定一個有向網路，其中每條邊都有非負容量，最大流問題在探討：在滿足每條邊的流量不超過其容量，且流入每個非源點、非匯點頂點的流量必須等於流出該頂點的流量這兩個規則下，從指定的源點 s 可以向匯點 t 推送多少流量？答案稱為最大流值。

什麼是 Ford-Fulkerson 方法？

Ford-Fulkerson 是計算最大流的一種通用技術。它反覆在剩餘圖中尋找從源點到匯點的增廣路徑，沿該路徑推送盡可能多的流量（瓶頸容量），然後更新剩餘圖。當不存在增廣路徑時，程序終止。當使用廣度優先搜尋 (BFS) 進行路徑選擇時，它被稱為 Edmonds-Karp 演算法，運行時間為 O(V · E²) 級別。

流量網路的最小割是什麼？

割是將頂點劃分為兩個集合 S 和 T 的分區，使得源點在 S 中，匯點在 T 中。割的容量是從 S 到 T 的邊容量之和。最小割是容量最小的割。著名的最大流最小割定理證明，最大流值始終等於最小割容量，因此找到其中一個就等於免費得到了另一個。

什麼是剩餘圖？

剩餘圖追蹤每條邊還能推送多少流量。對於每條原始邊 (u, v)，若容量為 c 且當前流量為 f，則剩餘圖包含一條容量為 c 減 f 的前向邊 (u, v)（剩餘容量）和一條容量為 f 的反向邊 (v, u)（可取消流量）。增廣路徑使用剩餘圖的邊，允許演算法撤銷之前的決定。

為什麼工具使用 BFS 尋找增廣路徑？

選擇使用廣度優先搜尋 (Edmonds-Karp) 尋找增廣路徑可以保證無論邊容量如何，都能在多項式時間內終止。普通的 Ford-Fulkerson 若使用任意路徑尋找策略，在病態輸入下可能會循環指數級次迭代，在無理數容量下甚至可能不終止。BFS 還會產生最短的增廣路徑，更易於閱讀和推理。

飽和邊代表什麼意思？

當邊的流量等於其容量時，該邊即為飽和，這意味著無法再在其上推送更多流量。飽和邊是網路的瓶頸，且每個最小割完全由從割的 S 側到 T 側的飽和邊組成。工具會以紅色突出顯示飽和邊，讓您一眼就能看到瓶頸結構。

延伸閱讀

• 最大流問題 — 維基百科
• Ford–Fulkerson 演算法 — 維基百科
• Edmonds–Karp 演算法 — 維基百科
• 最大流最小割定理 — 維基百科