最小割 在图论中去掉其中所有边能使一张网络流图不再连通即分成两个子图的边集称为图的割英語cut一张图上最小的割称为最小割英語minimum cut或mincut与最小割相关的问题称最小割问题英語minimum cut problem或mincut problem其变体包括带边权有向图包含源点与汇点简称有源汇以及将原网络分为多于两个子图等问题其中带边权的最小割问题允许有负权边可通过对所有边权取相反数简单地转化为最大流问题求解