最大割

设 是一个（不一定简单）无向边加权图，具有非负权重。图 的一个割 是 的任何非平凡子集，割的权重是跨越割的边的权重之和。那么，最大割被定义为图 的具有最大权重的割。确定图的最大割是一个 NP 难问题。