最小割

設 是一個（不一定是 簡單 的）無向 邊加權圖，權重為非負。圖 的一個 割 是 的任何非平凡 子集，割的權重是跨越 割 的邊的權重之和。最小割然後被定義為圖 的最小權重的 割。這個問題是 多項式時間 可解的，可以透過一系列 網路流 問題或使用 Stoer 和 Wagner (1994) 的演算法解決。