最大流PPT课件.pptx

最大流1.引子生活中的实例：通讯网络、城市管道网络、交通网络等等，建设者都希望某种流量能够达到最大.给定有向网络N=(V,A,c,s,t)，在所有的可行流中找一个流量最大的.2.可行流x：同时满足流量限制和守恒方程.流量限制：守恒方程：目标：3.最大流问题的线性规划模型：因此可以用单纯形法或其他线性规划方法求解，最大流问题是多项式时间可解的.4.增广路设P是N中从s到t的无向路，若其中某一条弧 的方向也是从s到t的，则称它为前向弧，否则称为反向弧.进一步设 是N上的一个可行流，如果对P的每个前向弧 有 ，每个反向弧 有 ，则称路P是关于流 的增广路.5.6.一个弧割 若满足 ，则称为 割，其容量定义为 .定理1.对任意的可行流 和任意的 割，有 由守恒方程有7.定理2.（增广路定理）一个可行流是最大流的充要条件是不存在增广路.定理3.（最大流最小割定理）任何带发点s和收点t的容量网络中最大流的流值等于（s，t）-割的最小容量.定理4.（整流定理）如果所有弧容量是整数，则最大流的流值为整数.8.1957年Ford和Fulkerson最先给出了求解最大流问题的算法.Ford-Fulkerson算法思想：从任一可行流（比如说0流）出发，找一条s到t的增广路，并在这条增广路上增加流值，于是得到新的可行流，如此反复，直到不存在s到t的增广路为止.关键如何找s到t的增广路标号法.9.标号过程中，一个顶点总处于下述三种状态之一：已标号且已检查（即该顶点已有一个标号且所有相邻点该标的都已标号）；已标号但未检查过；未标号.10.一个顶点 的标号为 .如果顶点 被标号且存在一条弧 使 则给未标号的 标上 ，其中如果顶点 被标号且存在一条弧 使 则给未标号的 标上 ，其中11.Ford-Fulkerson算法1.令 是任一整数可行流，给s一个永久标号 .2.2.1 如果所有标号顶点都已检查过，转4.2.2 找一个已标号但未检查的顶点 ，并做如下检查：对每条弧 ，如果 且 未标号，则给 一个标号 ；对每条弧 ，如果 且 未标号，则给 一个标号 .2.3 如果t已被标号，转3，否则转2.1.12.Ford-Fulkerson算法3.根据得到的增广路上各顶点标号来增加流量，抹去s外所有顶点标号，转2.4.此时当前流是最大流，且把所有标号点集记为，则 就是最小割.13.求解下图所示网络的最大流.14.求下图所示的最大流15.Ford-Fulkerson算法的时间复杂性为 ：每找一条增广路最多需要进行2m次检查；每条增广路最小增量为1.Edmonds-Karp算法 ：Ford-Fulkerson算法基础上，每次修改可行流时在弧数最少的增广路上进行.标号过程中，增加先标号先检查的原则.16.整数假设实数包含有理数和无理数.有理数就是分数，扩大若干倍可以变成整数.而对于无理数，Ford和Fulkerson1962证明了算法会收敛到一个不是最大流的流值.现实中流量是不会出现无理数的.17.