最大流問題定式化

最大流問題（Maximum Flow Problem）是圖論中的一個經典問題，它的目標是在一個帶有權重的有向圖中，找到一條從源點（source）到匯點（sink）的最大流量路徑。這裡的「最大流量」通常是指在路徑上所有邊的容量（capacity）總和的最大值。

最大流問題可以定義如下：

給定一個有向圖 G = (V, E)，其中 V 是頂點集，E 是邊集。在圖中，存在一個源點 s ∈ V 和一個匯點 t ∈ V。每個邊 (u, v) ∈ E 都有一個非負數的容量 c(u, v)，表示從頂點 u 到頂點 v 的流量限制。

問題是找到一組從源點 s 到匯點 t 的流量值 f(u, v)，滿足以下條件：

1. 對於每條邊 (u, v) ∈ E，流量 f(u, v) 不超過邊的容量 c(u, v)，即 f(u, v) ≤ c(u, v)。
2. 對於每個不在從 s 到 t 的路徑上的頂點 v，從 v 發出的流量等於進入 v 的流量，即 ∑{u|(u,v)∈E} f(u, v) = ∑{w|(v,w)∈E} f(v, w)。

目標是在這些條件下，找到最大的總流量，即 ∑_{(u,v)∈E} f(u, v) 的最大值。

最大流問題在許多實際應用中都很重要，例如在網絡流量優化、資源分配、機器學習、組合優化等領域。它可以用 Ford-Fulkerson 算法、Edmonds-Karp 算法、Push-Relabel 算法等來解決。