最大割

設 是一個（不一定簡單）無向邊加權圖，具有非負權重。圖 的一個割 是 的任何非平凡子集，割的權重是跨越割的邊的權重之和。那麼，最大割被定義為圖 的具有最大權重的割。確定圖的最大割是一個 NP 難問題。