网络流入门.doc

放假以来把网络流看来几篇，今天终于有点感觉，网上很多资料，我认为网络流最难理解的是加反向边，这个东西纠结了很久，网上搜到一个blog才领悟到一句真理：“反向边的作用就是给程序一个可以后悔的机会”，详细请看下面的文章，由于自己对网络流还是vegetables bird，所以只好转一下人家写的好文章。 另外，这里得出的，计算增广路流量的公式非常重要：cf（p） = min { cf（u，v）：（u，v）在 p 上}，因为最大流算法的核心基本也就是寻找增广路了。 最大流最小割定理：一个流是最大流，当且仅当它的残留网络不包含增广路径。 ??? 流网络的割（S，T）将V划分为 S 和 T = V – S两部分，使得 s ∈ S，t ∈ T。如果 f 是一个流，则穿过割 （S，T）的净流被定义为 f (S，T）。割（S，T）的容量为 c（S，T）。一个网络的最小割就是网络中所有割中最小容量的割。 ???? 上图中，流网络的割（S = {s，v1，v2}，T = {v3，v4，t}），S中的顶点是黑色，T中的顶点是白色。穿越（S，T）的净流量为：f（v1，v3） + f（v2，v3） + f（v2，v4） = 12 + （-4） + 11 = 19；容量为：c（v1，v3） + c（v2，v4） = 12 + 14 = 26。可以看出，割的净流由双向的网络流组成。而割的容量仅由 S 到 T 的边计算而得。 ???? 还有一个很有重要的知识：反向边。如图（a），1是源点，4是汇点。很明显如果第一次迭代找到的增广路是1→2→4和1→3→4，则最大流是2，但是如果第一次迭代找到的增广路是1→2→3→4，那么流量只有1，如图（b）是残留网络，这时候，反向边就起作用了，由于反向边的原因，第二次迭代的时候，又找到一条增广路1→2→3→4。这样下来，总的流量还是2。还是Starvae师兄的解释： ??????当我们第二次的增广路走 3→2 这条反向边的时候，就相当于把 2→3 这条正向边已经是用了的流量给“退”了回去，不走 2→3 这条路，而改走从 2 点出发的其他的路也就是 2→4。（有人问如果这里没有 2→4 怎么办，这时假如没有 2→4 这条路的话，最终这条增广路也不会存在，因为他根本不能走到汇点）同时本来在 3→4 上的流量由 1→3→4 这条路来“接管”。而最终 2→3 这条路正向流量1，反向流量1，等于没有流量。反向边的作用就是给程序一个可以后悔的机会。—— 一语中的啊。（这句话我加的^^） 二、Ford-Fulkerson算法? ???? Ford-Fulkerson算法在实际中并不常用，但是它提供了一种思想：先找到一条从源点到汇点的增广路径，这条路径的容量是其中容量最小的边的容量。然后，通过不断找增广路，一步步扩大流量，当找不到增广路时，就得到最大流了（最大流最小割定理）。可以看看Ford-Fulkerson算法的伪代码， FORD-FULKERSON(G, s, t) 1? for each edge (u, v) ∈ E[G] 2?????? do f[u, v] ← 0 3????????? f[v, u] ← 0 4? while there exists a path p from s to t in the residual network Gf 5????? do cf(p) ← min {cf(u, v) : (u, v) is in p} 6???????? for each edge (u, v) in p 7???????????? do f[u, v] ← f[u, v] + cf(p) 8??????????????? f[v, u] ← -f[u, v] ???? 从伪代码可以看出，Ford-Fulkerson的核心过程就是：第4~8行的 while 循环反复找出 Gf?中的增广路径 p，并把沿 p 的流 f 加上其残留容量cf（p）。当不再有增广路径时，流 f 就是一个最大流。完整图示： ?? （f）最后在 while 循环测试的残留网络，它没有增光路径，所以（e）中显示的流就是最大流。 三、压入重标记push_relabel算法O(VE) Push-relabel用到一个很有趣的概念一Preflow(前置流)他允许流进的量比流出的量还要多，有水来就先流进来，流不出去再说。 Push-relabel算法的流程如下：?? 1 )我们先假定一个高度函数 h ( u ) ，他代表u点的高度，只有 h ( u )比较高的点才能够将水流到h ( u )比较低的点；?? 2 ) 在程序一开始的时候，让source node的高度是n ( node数) ， ?其它点的高度都是 0 ，这样sourc