最小割意思

在圖論中，最小割（Minimum Cut）是一個網路流問題，指的是在一個帶權的有向圖中找到一個割（cut），這個割的容量是所有邊權之和的最小值。

具體來說，給定一個帶權的有向圖G=(V, E)，其中V是頂點集，E是邊集，每條邊(u, v) ∈ E有一個非負權重c(u, v)。一個割W是V的一個劃分，即V的一個子集的併集，其中每個子集都是連通的，且子集之間沒有邊相連。割W的容量是所有穿過割的邊的權重的總和，即

[ \text{capacity}(W) = \sum_{(u, v) \in E} c(u, v) \delta(u, v) ]

其中(\delta(u, v))是二元函式，當u和v屬於不同的子集時為1，否則為0。

最小割問題是要找到這樣一個割，其容量最小。最小割問題是一個NP-hard問題，但是當圖是流線型（s-t網路）時，即只有一個源點s和一個匯點t，這個問題可以用最大流算法在多項式時間內解決。這是因為最大流最小割定理指出，在一個流線型網路中，最大流和最小割的容量是相同的。

最小割問題在許多領域都有套用，如網路最佳化、資源分配、圖像分割等。在計算機科學中，最小割也被用於解決一些組合最佳化問題，如二分圖匹配、多源最短路等。