最大流最小割

最大流最小割問題是圖論中的一個經典問題，它是一個NP-完全問題，通常用於最佳化資源分配和網路流量管理。這個問題可以描述為：給定一個帶權有向圖G=(V, E)和一個源點s和一個匯點t，以及每個邊的容量u(e)，找到一條從s到t的最大流。

最小割問題可以表述為：找到一個割(S, T)，其中S和T是V的兩個子集，滿足s∈S，t∈T，使得割的容量最小。這裡的割的容量是所有屬於(S, T)的邊的容量之和。

最大流最小割定理表明，最大流問題和最小割問題是等價的，即最大流的流量等於最小割的容量。這個定理可以通過網路流的對偶性來證明。

在實際套用中，最大流最小割問題可以用 Ford-Fulkerson 算法或 Edmonds-Karp 算法等算法來解決。這些算法可以在多項式時間內找到最大流，但是它們的運行時間通常很高。因此，對於大規模的問題，通常需要使用更高效的啟發式算法或近似算法。