算法9-3：最大流跟最小切割的理论

算法9-3：最大流和最小切割的理论

本章节介绍最大流问题和最小切割问题的关系。其实这两个问题是等价的。

现在把一个网络分成A和B两个部分，我们定义A到B的净流量交叉(Net flow across)就是从A到B的最大流量减去从B到A的最大流量。

接下来介绍流量值定理（Flow-value lemma）。令f为网络中任何一个流，令(A,B)为网络的任何一种切割方法，那么(A,B)的净流量交叉就等同于f的流量值。下图展示了流量值定理。

通俗的解释一下吧。首先将网络切割两个部分A和B，那么AB之间的流量就是从A到B的总流量减去从B到A的总流量。

最小切割问题中的最小流量指的是上述流量值定理中的流量。

最小切割问题可以转换成最大流问题。也就是说可以从最大流图中计算最小切割。计算步骤是这样的。首先从原点S出发，将容量已满的正向路径和容量为空的反向路径看成障碍，从原点出发，将所有能到达的顶点进行遍历。最后这些能到达的顶点就是最小切割。