最大流

引用自《算法导论》第26章 最大流

简介：
正如可以将道路交通图模型化为有向图来找到从一个城市到另一个城市之间的最短路径，我们也可以将一个有向图看作是一个“流网络”并使用它来回答关于物料流动方面的问题。

• 最大流
  • 流网络
  • Ford-Fulkerson 方法
  • 最大二分匹配

流网络

1. 流网络和流：
   流网络 \(G=(V,E)\) 是一个有向图，图中每条边 \((u，v)\in E\)有一个非负的容量值 \(c(u,v)\ge 0\) ，且如果边集合 \(E\) 包含一条边 \((u,v)\) 则不存在反方向的边 \((v,u)\) 。则为方便起见，定义 \(c(v,u)=0\)，而在所有结点中，我们分辨出两个特殊结点：源结点 \(s\) 和 汇点 \(t\)，于是对于每个结点 $ v\in V$ 流网络都包含一条路径 \(s-v-t\)
   流：$$|f|=\sum_{v\in V}f(s,v)-\sum_{v\in V}f(v,s) $$
   容量限制：对于所有的结点 \(u,v\in V\)，要求 \(0\le f(u,v) \le c(u,v)\)。
   流量守恒：对于所有的结点 \(u\in V-\lbrace s,t\rbrace\)，要求：$$\sum_{v\in V}f(v,u)=\sum_{v\in V}f(u,v)$$
2. 流的一个例子:
   
   a 图为一开始的容量图，箭头上的数字代表容量； b 图为取最大流时的流网络图，此处的 / 仅起到区分流和容量的作用

Ford-Fulkerson 方法

1. 残存网络&增广路径：
   
   左图即为按照 b 图绘制的残存网络，而标红的则是其一条增广路径，在这里我们不难发现右图中从 s 到 t 已经没有增广路径了，而此时的流即为最大流
   残存网络 \(G_f\) 由那些仍有空间对流量进行调整的边构成
   增广路径 \(p\) 是残存网络 \(G_f\) 中一条从源结点到汇点的简单路径

2. 基本的 Ford-Fulkerson算法：
   伪代码描述如下
   1 对于 每一条边\((u,v)\in G,E\)
   2   \((u,v).f=0\)
   3 每当 在残存网络 \(G_f\) 中存在一条从 \(s\) 到 \(t\) 的增广路径 \(p\)
   4   \(c_f(p)\)=min\(\lbrace c_f(u,v):(u,v)\) is in \(p \rbrace\)
   5   对于 每一条增广路径 \(p\) 中的边 \((u,v)\)
   6     如果 \((u,v)\in E\)
   7       \((u,v).f\)=\((u,v).f+c_f(p)\)
   8     否则\((u,v).f\)=\((u,v).f-c_f(p)\)
   对于=for 每当=while

3. Edmonds-Karp算法：
   即在寻找增广路径时使用广度优先搜索来改善算法效率

最大二分匹配

这样的一个图中，我们要将左边结点与右边结点匹配，且一个左结点只能匹配一个右节点，怎么找出最大匹配数？
将这个问题转化为最大流问题，则得到最大流为3，如图所示：

（未完待续）