由割集的定义不难看出,无论拿掉那个割集,发点vs到收点vt便不再相通,所以任何一个可行流都会经过割集,且不会超过任一割集的容量。最小割如同瓶颈一般,即使是最大流也无法超过最小割,网络的最大流与最小割容量满足下面的定理(证明略)。
设f为网络G=(V,E,C)的任一可行流,流量为v(f),
由定理一可知,最大流的流量v(f)和某一割集K的容量相等,而且最大流的流量本身也不带任一割集的容量,因此割集一定是最小的割集。
任一网络G中,从vs到vt的最大流的流量等于分离vs、vt的最小割的容量(最小的割集的容量)。
一条从起点vs到终点vt的链μ,规定从vs到vt的方向为链μ的方向,链上与μ方向一致的边叫前向弧(边),记作μ-;与μ方向相反的边称为后向弧(边),记作μ 。
f是一个可行流,fij表示由i点指向j点的流量,如果满足前向弧的流量非负且小于容量,或后向弧的流量大于0且不超过容量:
则称μ为从vs到vt的关于f的可增广链。
可增广链的实际意义是:沿着这条从vs到vt输送的流,仍有潜力可挖,只要前向弧的流量增加或后向弧的流量减少,就可以将截集的流量提高。调整后的流,在各点仍满足平衡条件及容量限制条件,仍为可行流。
从另一个角度来说,可以提高流量的可行流也不是最大流,因此可行流f是最大流的充要条件是不存在从vs到vt的可增广链。