最大流和最小割

最大流（Maximum Flow）和最小割（Minimum Cut）是網路流問題中的兩個密切相關的概念。最大流問題關注的是在一個有向圖中找到從一個源點到匯點的最大流量，而最小割問題則關注的是找到一個能夠將圖分割成兩個部分的最小割集。

最大流問題可以表述為：給定一個有向圖G=(V, E)，其中V是頂點集，E是邊集。圖中有源點s和匯點t。每條邊(u, v)∈E有一個非負容量c(u, v)，表示從u到v的最大流量。最大流問題是要找到一個從源點s到匯點t的流量分配，使得流過的總流量最大，同時滿足每條邊的流量不超出其容量。

最小割問題可以表述為：給定一個有向圖G=(V, E)，其中V是頂點集，E是邊集。圖中有源點s和匯點t。最小割問題是要找到一個邊集S⊆E，使得刪掉S中的邊後，s和t被分割成兩個不相連的子圖，且S的容量（即邊集S中所有邊的容量之和）最小。

最大流和最小割之間的關係可以通過網路流的對偶性來表述。簡單來說，一個圖的最大流等於其最小割的容量。這個對偶性可以通過網路流的增廣路算法（Augmenting Path Algorithm）來證明。增廣路算法是解決最大流問題的一種有效方法，它通過找到一條從源點到匯點的增廣路（即一條路徑，使得每條邊的流量都沒有達到其容量），並沿著這條路徑增加流量，直到無法再找到增廣路為止。

最小割問題在實際套用中也有廣泛的套用，例如在圖像分割、社區檢測、機器學習和數據挖掘等領域。最小割問題的一個特例是二分圖最小割問題，它可以在多項式時間內通過匈牙利算法解決。