By Zhang, Cheng

更新日期:

文章目录
  1. 1. 算法（8） 最大流和最小割
    1. 1.1. 网络流
      1. 1.1.1. 最大流
      2. 1.1.2. 另一种表示形式
      3. 1.1.3. 再来仔细看看这个算法
      4. 1.1.4. 最优化证明
      5. 1.1.5. 效率
    2. 1.2. 线性规划中的最小最大关系

算法（8） 最大流和最小割

网络流

现在我们有一个布满管道的网络。这个管道网络是用来传输石油的。我们的目标是尽可能多地将石油从源点s输送到汇点t。网络中管道有最大容量，且管道中不能保留石油。

上面的两个图是网络流的例子，其中图(a)是这个流网络的容量图，表示各个管道之间最大可容纳的石油量；图(b)是网络流的其中一个流量图，流量图有多个，表示某一个时刻下网络的流量情况。

最大流

我们可以对上面的问题进行线性化的描述，设fe表示在网络中的管道e上的流量变量，这个变量满足下面的两个条件：

  1. 对所有的管道，fe在[0,ce]，其中ce表示管道e上的容量；
  2. 对于所有除了源点s和汇点t，流入的流量和流出的流量应该相等。

接着我们举个例子，对具体的网络流图进行线性规范的构建：

对于这个网络流，总共有11个管道，每个管道一个变量。目标函数是max fsa + fsb + fsc。将由源点流出的流量求最大值，即源点流出的a、b、c三个点的流量。总共有27个限制条件，11个流量非负，11个流量小于容量，5个节点的入度流量和等于出度流量和（fsa+fba=fad, fsb=fba+fbd, fsc+fdc=fce, fad+fbd=fdc+fde+fdt, fce+fde=fet）

另一种表示形式

首先引入一条从汇点t到源点s的虚构边，这条边的容量有无穷大。这样整个流就会是个循环。这时候我们的目标函数可以是fts，求从t到s的最大流。这个改变的好处就是在s和t点上也可以做到流的守恒。

我们之前的限制是除了源点和汇点，现在对任何点都符合流入流量等于流出流量。

这个表达形式为什么和上面的线性规划可以等价呢？因为网络流图中的流量是一个循环了，所以只可能是fwi <= fiz，取等号的时候才能满足条件。至于为什么>=不行，老师上课说他只记得不行，但是想不起反例是什么了。那我们就姑且先记住<=不行吧。

再来仔细看看这个算法

在单纯形法中，整个过程的行为从零开始，反复寻找最适合的从s到t的路径，然后尽可能多地增加路径上的边长。

针对这样的图，如果我们运气好，选到的是sa-at和sb-bt，那么正好得到最终的结果，最大流是2。但是如果我们运气不好，选到是sa-ab-bt的路径不是把其他所有的路径都堵住了吗？还好在单纯形法中，允许取消现有的流，也就是给你一个后悔的机会：因为刚刚可能选错了，现在允许你回过去再来找找。形象点的话，我们可以将问题放到三维空间中，允许回边就好比只是这个阶段的最优值，还有更优的结果等着我们。

算法的过程描述起来有点抽象，我直接举个例子吧：

还是用上面的网络图，下面的图是一个容量图

下面的图片都是左边表示流量图，右边是剩余图。

我们先看图(a)，找到一条从s到t的路径，s-a-d-c-e-t。在这条路径上寻找容量最小的边，也就是说这条路径能够允许通过的最大流量就是1（决定木桶盛多少水是那块最短的木板）。将这个流量1放到流量图中，就得到了图(b)的流量图（左图）。

接着做这样的操作：在图(a)右图中路径的每条边上添加一条反向边，边的权值为刚刚的流量1。而之前的路径分别减去这个流量1。比如s-a这条边，之前是3。现在减去流量1,还可以流2。a-s添加了一条权值为1的边。

对刚刚路径上的每条边进行这样的操作，就得到了图(b)的右图。接着继续寻找一条从s到t的路径：s-a-d-e-t，容量最小的边是1。

将上面找到的权值加到流量图中，得到图(c)的左图。继续进行添加反向边，减去最小容量的操作，得到图(c)右图的剩余图。继续寻找一条从s到t的路径：s-c-e-t，容量最小的边是3。将权值为3的边添加到流量图中，得到图(d)的左图。以此类推，直到没有从s到t的路径，网络图的最大流就找到了。

最优化证明

下面是一个图的割，(s,t)割表示将图中的节点分割成不相交的两组L和R，其中s属于L而t属于R。割的容量就是那些被切割边的权值和。很容易就可以想到流的容量是不大于割的容量的，不然管道不就爆了吗？

那么现在就有个问题，是否最大流的容量等于最小割的容量？也就是我们常说的最大流-最小割。

接下来我们来证明一下这个定理：首先我们已经得到一个结论，就是任何流的容量是不大于割的容量的。那么我们只需要证明存在一个最大流是等于割的容量的，那么就可以证明任何最大流的容量都是等于最小割的容量的。其实我们上面计算最大流的过程已经算是一种证明了。当剩余图中没有从s到t的路径，也就是当前状态为最大流状态，那么构造这样的割使得s能到的点作为一个集合S，t能到的点作为另一个集合T。这样那些割上的边都是满流边，而这些满流边的容量恰好是割的容量。所以最大流的容量等于最小割的容量。

效率

上面的算法每个迭代下需要O(E)来寻找一条从s到t的路径，寻找的方法可以是深搜也可以是广搜。那么需要多少次迭代呢？我们可以这样想，最初网络中的所有边用一个整数容量且小于等于一个整数值C。那么在每次迭代中，流也是整数且以整数数量来增加，所以也就是说最大流最多是C*E的，迭代的次数也就是这么多。

如果选择路径的方式聪明一点的话，或者具体点用广度优先搜索（找到最少边的路径）的话，迭代的次数至少是O(V*E)次，与管道的容量无关了。这个算法就称作Edmonds-Karp算法。那么整个算法的复杂度就是O(V*E*E)。

接着我们来证明这点：

线性规划中的最小最大关系

文章目录
  1. 1. 算法（8） 最大流和最小割
    1. 1.1. 网络流
      1. 1.1.1. 最大流
      2. 1.1.2. 另一种表示形式
      3. 1.1.3. 再来仔细看看这个算法
      4. 1.1.4. 最优化证明
      5. 1.1.5. 效率
    2. 1.2. 线性规划中的最小最大关系