《运筹》教学课件图论与网络第六章（四）最大流问题.ppt

《《运筹》教学课件图论与网络第六章（四）最大流问题.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、§6.4最大流问题theMaximumFlowProblem一、最大流问题(theMaximumFlowProblem)许多系统包含了流量问题。例如，公路系统的车辆流，控制系统中的的信息流、金融系统的现金流。最大流问题就是指一个出发点最多能发送多少流量到一个接受点。最大流问题引例：如下输水网络，南水北调工程，从vs到vt送水，弧旁数字为管道容量，问应当如何输水使得流量最大？v2v451v1v6v3v5108533171136.4.1基本概念与基本定理定义1给定一个有向图D(V,A),在V中指定一个点作为发点，记为Vs；指定另外一个点作为收点，记为Vt；其余的点称为中间点。定义2对于有向图D(

2、V,A)中的每一个弧(Vi,Vj),对应有一个值c(Vi,Vj),称为弧的容量。对于赋权的有向图D(V,A,C),特称为网络,记为D(V,A,C)。6.4.1基本概念与基本定理定义3网络上的流，是指定义在弧集合A上的一个函数f={f(Vi,Vj)}。并称为f(Vi,Vj)为弧(Vi,Vj)上的流量。6.4.1基本概念与基本定理网络流的两个性质：性质1每个弧上的流量不能超过该弧的最大通过能力即容量。性质2中间点的流量为0。6.4.1基本概念与基本定理定义4满足下述条件的流成为可行流容量限制条件。对任意一弧(Vi,Vj),均有0≤f(Vi,Vj)≤c(Vi,Vj)平衡条件1.对于中间点：流入量等

3、于流出量，流量为0；2.对于发点:只有流出量,流量为可行流的流量为v(f)3.对于收点:只有流入量,流量为可行流的流量为-v(f)6.4.1基本概念与基本定理定义5容量最大的可行流成为最大流.6.4.1基本概念与基本定理v2v451v1v6v3v510853317113126.4.1基本概念与基本定理v2v454v1v6v3v510853317113513233266.4.1基本概念与基本定理增广链的形式v2v45vsvt1011526v2v45vsvt1011526126.4.1基本概念与基本定理v2v454v1v6v3v5108533171135132332685056.4.1基本概念与

4、基本定理6.4.1基本概念与基本定理1v2v41vsvtv1v335232513113201346.4.1基本概念与基本定理6.4.1基本概念与基本定理6.4.2标号法(Ford-Fulkerson算法）算法思想:首先得到一条可行流。然后在可行流的基础上,寻找增广链.如果找到,得到新的流量更大的可行流;如果找不到，说明当前的可行流就是最大流。由于可行流的流量不能无限增大，因而总可以得到最大流。6.4.2标号法(Ford-Fulkerson算法）第一步：构建一条可行流1v2v41vsvtv1v335232513113201346.4.2标号法(Ford-Fulkerson算法）第二步：寻找增广

5、链——标号过程6.4.2标号法(Ford-Fulkerson算法）第二步：寻找增广链——标号过程6.4.2标号法(Ford-Fulkerson算法）第二步：寻找增广链——标号过程(-v2,1)6.4.2标号法(Ford-Fulkerson算法）第二步：寻找增广链——标号过程1v2v41vsvtv1v33523251311320134(0,M)(vs,4)(-v1,1)(v2,1)(v4,1)6.4.2标号法(Ford-Fulkerson算法）第三步：调整过程6.4.2标号法(Ford-Fulkerson算法）1v2v41vsvtv1v33523251311320134(0,M)(-v1,1)

6、(v2,1)(v4,1)第三步：调整过程(vs,4)(-v2,1)46.4.2标号法(Ford-Fulkerson算法）1v2v41vsvtv1v3352325131132013(0,M)(-v1,1)(v2,1)(v4,1)第三步：调整过程(vs,4)(-v2,1)20446.4.2标号法(Ford-Fulkerson算法）第二步：再标号过程v2v41vsvtv1v33523251342044(0,M)(vs,3)20116.4.3最小截集的获得1vsvtv1v335232513204(0,M)(vs,3)201144v2v4算法出现的问题(-v2,2)2v2v42vsvtv1v33543

7、452322340234(0,M)(vs,4)(-v1,1)(v2,1)(v4,1)1.哪个未检查但标号的点先被检查的问题先检查调整数量最大的点323算法出现的问题(v1,6)v2v4vsvtv1v3109851923115(0,M)(vs,7)(v1,7)(v2,2)2.一个点已被标号,它的标号是否会改变如果调整数量增大就改变323算法出现的问题(v1,6)v2v4vsvtv1v3109851923118(