最大流

最大流引子•生活中的实例：通讯网络、城市管道网络、交通网络等等，建设者都希望某种流量能够达到最大.•给定有向网络N=(V,A,c,s,t)，在所有的可行流中找一个流量最大的.•可行流x：同时满足流量限制和守恒方程.•流量限制：•守恒方程：•目标：ijijcx0tvftsvsvfxxiiiVvjiVvijjj，，，,0jjtjsjxxf**max•最大流问题的线性规划模型：•因此可以用单纯形法或其他线性规划方法求解，最大流问题是多项式时间可解的.Avvcxtsvxxtvfxxsvfxxtsfjiijijivjivijivjivijivjivijjjjjjj),(,0,,0,,..max•增广路•设P是N中从s到t的无向路，若其中某一条弧的方向也是从s到t的，则称它为前向弧，否则称为反向弧.•进一步设是N上的一个可行流，如果对P的每个前向弧有，每个反向弧有，则称路P是关于流的增广路.),(jivv)(ijxx),(jivvijijcx),(jivv0ijx)(ijxxst1v2v4v3v1,31,22,32,22,20,11,11,2st1v2v4v3v2,32,22,32,22,20,10,12,2•一个弧割若满足，则称为割，其容量定义为.•定理1.对任意的可行流和任意的割，有•由守恒方程有),(SSSvVvjiVvijijjxxf)(StSs,),(tsSvSvijijcSSC),(SvSvjiSvijSvSvjiSvijijjijjxxxx)()(SvSvjiSvijijjxx)(SvSvijijxSvSvijijc).,(SSC)(ijxx),(ts).,(SSCf•定理2.（增广路定理）一个可行流是最大流的充要条件是不存在增广路.•定理3.（最大流最小割定理）任何带发点s和收点t的容量网络中最大流的流值等于（s，t）-割的最小容量.•定理4.（整流定理）如果所有弧容量是整数，则最大流的流值为整数.•1957年Ford和Fulkerson最先给出了求解最大流问题的算法.•Ford-Fulkerson算法思想：从任一可行流（比如说0流）出发，找一条s到t的增广路，并在这条增广路上增加流值，于是得到新的可行流，如此反复，直到不存在s到t的增广路为止.•关键如何找s到t的增广路——标号法.•标号过程中，一个顶点总处于下述三种状态之一：•已标号且已检查（即该顶点已有一个标号且所有相邻点该标的都已标号）；•已标号但未检查过；•未标号.•一个顶点的标号为.•如果顶点被标号且存在一条弧使则给未标号的标上，其中•如果顶点被标号且存在一条弧使则给未标号的标上，其中),(ijvv))(,(ij,jijicxjv))(,(ijiviv}.),(min{)(jijixcji),(jivv))(,(ij,0ijxjviv}.),(min{)(ijxjiFord-Fulkerson算法1.令是任一整数可行流，给s一个永久标号.2.2.1如果所有标号顶点都已检查过，转4.2.2找一个已标号但未检查的顶点，并做如下检查：对每条弧，如果且未标号，则给一个标号；对每条弧，如果且未标号，则给一个标号.2.3如果t已被标号，转3，否则转2.1.),()(ijxxijijcx),(jivvivjvjv)})(,min{)(,(ixcjiijij),(ijvv0jixjvjv)})(,min{)(,(ixjijiFord-Fulkerson算法3.根据得到的增广路上各顶点标号来增加流量，抹去s外所有顶点标号，转2.4.此时当前流是最大流，且把所有标号点集记为，则就是最小割.),(SSS•求解下图所示网络的最大流.3v1v2v4v5v6v4622134753v1v2v4v5v6v4,43,62,22,20,12,34,43,75,5)3,1(),()2,3()1,5()1,2()1,5(4,43,62,22,20,12,34,43,75,5)2,1(),()1,3(4,44,61,22,21,12,34,44,75,5求下图所示的最大流•Ford-Fulkerson算法的时间复杂性为：每找一条增广路最多需要进行2m次检查；每条增广路最小增量为1.•Edmonds-Karp算法：Ford-Fulkerson算法基础上，每次修改可行流时在弧数最少的增广路上进行.•标号过程中，增加先标号先检查的原则.)(mfOMMMMMMMM11)()(52nOnmO•整数假设•实数包含有理数和无理数.•有理数就是分数，扩大若干倍可以变成整数.•而对于无理数，Ford和Fulkerson[1962]证明了算法会收敛到一个不是最大流的流值.•现实中流量是不会出现无理数的.