最小割最大流

最小割最大流問題是圖論中的一個經典問題，它是一個NP-完全問題，通常用於描述資源分配或網路流問題。問題的名稱來源於「最小割」和「最大流」這兩個概念。

最小割（Minimum Cut）是指在一個有向圖中，找到一個割的最小容量，這個割將圖的頂點集分為兩個不相交的子集，使得沒有邊連線這兩個子集。

最大流（Maximum Flow）是指在一個有向圖中，找到一條從源點到匯點的最大流量路徑。這裡的流量是指在邊上有權重的條件下，能夠通過的最大權重和。

最小割最大流問題的表述如下：給定一個有向圖G=(V, E)，其中V是頂點集，E是邊集。圖中有源點s和匯點t。每條邊(u, v)∈E有一個非負權重c(u, v)，表示這條邊的容量。要求找到一個割(S, T)，使得S∪T=V，S∩T=∅，且S包含源點s，T包含匯點t，同時找到一個從s到t的最大流。

最小割最大流問題的對偶性在於，最小割的容量等於最大流的流量。這個性質可以通過網路流的對偶理論來證明。簡單來說，最小割的容量是割開圖後，被割開的邊的總容量，而最大流是通過增廣路不斷增加流量得到的，增廣路的反方向就是割開圖的邊。因此，最小割的容量和最大流的流量是等價的。

在實際套用中，最小割最大流問題可以用 Ford-Fulkerson 算法或 Edmonds-Karp 算法等來求解，這些算法可以通過反覆找到增廣路來逐步增加流，直到無法再增加為止。此時得到的流就是最大流，而對應的割可以通過反悔操作來找到。