第三部分：路徑規劃（續）¶
< 上一題：備援網路建設 | 返回目錄 | 下一題：部署順序規劃 >
場景：這條路最多能傳多少流量？¶
市場部說：「我們要在台北和法蘭克福之間傳輸大量資料，整個網路**最多能支撐多少頻寬**？」
不是問「走哪條路最快」，而是問「把所有可能的路都用上，總共能傳多少？」
「從 A 到 B，最多能流多少？」——這是 最大流（Maximum Flow） 問題。
第 7 題：頻寬容量分析 - Max Flow¶
(a) 流量網路定義¶
3 分 ・ 大二
你需要知道：什麼是流量網路？什麼是合法的流？
題目：
-
定義**流量網路（Flow Network）**
-
什麼是**合法流（Valid Flow）**？需要滿足什麼條件？
-
定義**最大流（Maximum Flow）**
解答
1. 流量網路：
有向圖 \(G = (V, E)\)，加上： - 源點（Source） \(s\)：流量的起點 - 匯點（Sink） \(t\)：流量的終點 - 容量（Capacity） \(c(u,v)\)：邊 \((u,v)\) 能承載的最大流量
2. 合法流：
函數 \(f: E \to \mathbb{R}^+\) 滿足：
- 容量限制：\(0 \leq f(u,v) \leq c(u,v)\)（不超過容量）
- 流量守恆：對於 \(v \neq s, t\)：
（流入 = 流出，中間節點不「儲存」流量）
3. 最大流：
最大化 \(|f|\) 的流就是**最大流**。
(b) Ford-Fulkerson 方法¶
4 分 ・ 大三
你需要知道：如何找最大流？
題目：
-
什麼是**剩餘圖（Residual Graph）和**增廣路徑（Augmenting Path）？
-
說明 Ford-Fulkerson 方法的步驟
-
為什麼需要「反向邊」？
解答
1. 剩餘圖與增廣路徑：
剩餘容量： $\(c_f(u,v) = c(u,v) - f(u,v)\)$
剩餘圖 \(G_f\)： - 正向邊：\(c_f(u,v) > 0\) 時存在 - 反向邊：\(f(u,v) > 0\) 時，加入 \((v,u)\)，容量為 \(f(u,v)\)
增廣路徑：剩餘圖中從 \(s\) 到 \(t\) 的路徑。
2. Ford-Fulkerson 方法：
def ford_fulkerson(graph, s, t):
# 初始化流為 0
flow = defaultdict(lambda: defaultdict(int))
max_flow = 0
while True:
# 在剩餘圖中找增廣路徑（BFS 或 DFS）
path, bottleneck = find_augmenting_path(graph, flow, s, t)
if path is None:
break
# 沿路徑增廣
max_flow += bottleneck
for i in range(len(path) - 1):
u, v = path[i], path[i+1]
flow[u][v] += bottleneck
flow[v][u] -= bottleneck # 反向邊
return max_flow
3. 為什麼需要反向邊？
反向邊代表「撤銷」之前的流量分配。
例：
s → a → t（容量 1）
s → b → t（容量 1）
a → b（容量 1）
如果先走 s→a→b→t（流量 1），
沒有反向邊的話，s→a→t 就被堵住了。
有反向邊 b→a（容量 1），
可以再走 s→b→a→t... 等等，這不對。
正確例子：
s → a → b → t（各容量 1）
s → b（容量 1）
先走 s→a→b→t（流量 1）
反向邊 b→a 出現
再走 s→b，但 b→t 滿了，透過 b→a→??? 不通
實際上反向邊讓我們能「重新分配」流量。
直覺：反向邊讓演算法可以「後悔」之前的決定，重新分配流量以達到全局最優。
© Max-Flow Min-Cut 定理¶
4 分 ・ 碩一
你需要知道：最大流等於什麼？
題目：
-
定義 \(s\)-\(t\) 切割（Cut）**及其**容量
-
陳述並解釋 Max-Flow Min-Cut 定理
解答
1. \(s\)-\(t\) 切割：
把頂點分成 \(S\) 和 \(T = V - S\)，其中 \(s \in S\), \(t \in T\)。
切割容量：
（從 \(S\) 到 \(T\) 的邊容量總和）
2. Max-Flow Min-Cut 定理：
最大流 = 最小切割容量
意義：
- 上界：任何流都不能超過任何切割的容量（因為流必須「穿過」切割）
- 可達性：Ford-Fulkerson 找到的流恰好等於某個切割的容量
找最小割：當演算法結束時，從 \(s\) 在剩餘圖中可達的頂點集合就是 \(S\)。
應用：網路可靠性
最小割 = 要斷開 \(s\) 和 \(t\)，至少要切斷多少容量的邊
這告訴你網路的「瓶頸」在哪裡。
如果最小割很小，表示網路脆弱，少數幾條邊失效就會癱瘓。
(d) Edmonds-Karp 演算法¶
3 分 ・ 碩一
你需要知道：如何保證 Ford-Fulkerson 的效率？
題目：
-
Ford-Fulkerson 用 DFS 找增廣路徑有什麼問題？
-
Edmonds-Karp 如何改進？時間複雜度是多少？
解答
1. DFS 的問題：
如果容量是無理數（或很大的整數），DFS 可能找到「很差」的增廣路徑，導致： - 每次只增廣很少的流量 - 迭代次數可能非常多（甚至不終止）
2. Edmonds-Karp 改進：
用 BFS 找增廣路徑（最短路徑，邊數最少）。
def find_augmenting_path_bfs(graph, flow, s, t):
parent = {s: None}
queue = deque([s])
while queue:
u = queue.popleft()
for v in graph[u]:
residual = graph[u][v] - flow[u][v]
if v not in parent and residual > 0:
parent[v] = u
if v == t:
# 回溯找路徑和瓶頸
path = []
curr = t
bottleneck = float('inf')
while curr != s:
prev = parent[curr]
path.append(curr)
bottleneck = min(bottleneck, graph[prev][curr] - flow[prev][curr])
curr = prev
path.append(s)
return path[::-1], bottleneck
queue.append(v)
return None, 0
時間複雜度：
- 每次 BFS：\(O(E)\)
- 最多 \(O(VE)\) 次增廣
- 總時間：\(O(VE^2)\)
為什麼最多 \(O(VE)\) 次？
BFS 保證每次找到的路徑是最短的。可以證明：增廣路徑的長度（邊數）是單調不減的，且每條邊最多成為「瓶頸」\(O(V)\) 次。
進階挑戰：二分圖最大匹配¶
3 分 ・ 碩一
你需要知道：Max Flow 有什麼經典應用？
題目：
說明如何用最大流解決**二分圖最大匹配（Bipartite Matching）**問題。
解答
問題：給定二分圖 \(G = (U, V, E)\)，找最大數量的「配對」，使得每個頂點最多被配對一次。
建模成 Max Flow：
- 添加源點 \(s\)，連接所有 \(U\) 中的頂點，容量 1
- 添加匯點 \(t\)，所有 \(V\) 中的頂點連接 \(t\)，容量 1
- 原本的邊 \((u, v)\)（\(u \in U\), \(v \in V\)）保持，容量 1
最大流 = 最大匹配數
每個匹配對應一單位流量。
第 7 題小結：你的頻寬分析工具箱¶
「整個網路最多能傳多少？」
│
├─► (a) 問題定義？→ Max Flow
│ → 源、匯、容量、流量守恆
│
├─► (b) 怎麼找？→ Ford-Fulkerson
│ → 剩餘圖 + 增廣路徑
│ → 反向邊允許「後悔」
│
├─► (c) 流和割的關係？→ Max-Flow = Min-Cut
│ → 最大流等於最小割容量
│ → 找出網路瓶頸
│
└─► (d) 效率？→ Edmonds-Karp
→ BFS 找最短增廣路徑
→ O(VE²)
| 概念 | 重點 |
|---|---|
| 流量網路 | 有向圖 + 源 + 匯 + 容量 |
| 合法流 | 容量限制 + 流量守恆 |
| Ford-Fulkerson | 增廣路徑法 |
| Max-Flow Min-Cut | 最大流 = 最小割 |
| Edmonds-Karp | BFS，\(O(VE^2)\) |