最小割

设 是一个（不一定是 简单 的）无向 边加权图，权重为非负。图 的一个 割 是 的任何非平凡 子集，割的权重是跨越 割 的边的权重之和。最小割然后被定义为图 的最小权重的 割。这个问题是 多项式时间 可解的，可以通过一系列 网络流 问题或使用 Stoer 和 Wagner (1994) 的算法解决。