《最大流问题》PPT课件.ppt

《《最大流问题》PPT课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、图与网络分析（二）最大流问题吴海佳勤务指挥系部队管理教研室最大流问题是一类应用极为广泛的问题，例如在交通运输网络中有人流、车流、货物流，供水网络中有水流，金融系统中有现金流，通信系统中有信息流，管道运输中的石油流，等等。20世纪50年代福特(Ford)、富克逊(Fulkerson)建立的“网络流理论”，是网络应用的重要组成部分。容量网络：容量：设一个赋权有向图D=（V,E）,在V中指定一个发点vs和一个收点vt,其它的点叫做中间点。对于D中的每一条弧（vi,vj）∈E,都有一个非负数cij（即每条弧的最大可能负载），叫

2、做弧的容量。容量网络：对所有的弧都给出了容量的有向网络，记做D=（V，E，C）。一、基本概念容量网络案例有一个管道网络，使用这个网络可以把石油从采地运送到其他一些点，这个网络的一部分如下图所示。由于管道的直径的变化，它的各段管道（vi,vj）的容量cij也是不一样的。cij的单位为万加仑/小时。如果使用这个网络系统从采地v1向某地v7运送石油，问每小时最多能运送多少加仑石油？一、基本概念63522241263v1v2v7v4v3v6v5一、基本概念流与可行流：弧上的流：网络中加在弧上的负载量，是指定义在弧集合E上的一个

3、函数，记为f(vi,vj)=fij。图上的流：加在网络中各条弧上的一组负载量（即定义在弧集上的一个函数），记为f={f(vi,vj)}={fij}。零流：网络上所有弧上的流均为0，则称相应的图上的流为零流。一、基本概念流与可行流：可行流：在容量网络上，满足容量限制条件和平衡条件的流为可行流：容量限制条件：对每条弧(Vi,Vj),有0≤fij≤Cij平衡条件：对中间点Vi,有∑fij=∑fki对发、收点Vs，Vt有∑fsj=∑fkt=v(f)v(f)为这个可行流的流量，即发点的净输出量或收点的净输入量。所谓最大流问题就是

4、在容量网络中，寻找流量最大的可行流。一、基本概念各种弧：对于可行流f={fij}，我们把网络中使fij=cij的弧称为饱和弧，使fij0的弧称为非零流弧一、基本概念容量网络、流量网络和残余网络的关系：容量网络=流量网络+残余网络63522241263v1v2v7v4v3v6v5容量网络一、基本概念63522241263v1v2v7v4v3v6v5容量网络43502021263v1v2v7v4v3v6v520022220000v1v2v7v4v3v6v5残

5、余网络流量网络43502021263v1v2v7v4v3v6v5一、基本概念增广路：从残余网络中找到一条从起点到终点的链路，该链路就是增广路；增广路的最大流量取决于组成该链路的各弧的最小容量。43502021263v1v2v7v4v3v6v5残余网络增广路222二、最大流问题寻找最大流的思路：定理：可行流f是最大流，当且仅当不存在从起点到终点的关于f的可增广链。1v1v2v4v31111二、最大流问题寻找最大流的思路：初始时，流量网络的流量为0，残余网络=容量网络；不断从残余网络中寻找增广路，将增广路的最大流量赋予流量

6、网络；直至残余网络中找不到增广路，流量网络的流量最大1v1v2v4v31111二、最大流问题寻找最大流的思路：初始时，流量网络的流量为0，残余网络=容量网络；不断从残余网络中寻找增广路，将增广路的最大流量赋予流量网络；直至残余网络中找不到增广路，流量网络的流量最大1v1v2v4v31111找到v1->v2->v3->v4这条增广路，最大流量为1；二、最大流问题寻找最大流的思路：初始时，流量网络的流量为0，残余网络=容量网络；不断从残余网络中寻找增广路，将增广路的最大流量赋予流量网络；直至残余网络中找不到增广路，流量网络

7、的流量最大0v1v2v4v30101找到v1->v2->v3->v4这条增广路，最大流量为1；将该增广路最大流量赋予流量网络，得到新的残余网络；二、最大流问题寻找最大流的思路：初始时，流量网络的流量为0，残余网络=容量网络；不断从残余网络中寻找增广路，将增广路的最大流量赋予流量网络；直至残余网络中找不到增广路，流量网络的流量最大0v1v2v4v30101找到v1->v2->v3->v4这条增广路，最大流量为1；将该增广路最大流量赋予流量网络，得到新的残余网络；残余网络中找不到增广路了。二、最大流问题问题出在哪里？0v1

8、v2v4v30101找到v1->v2->v3->v4这条增广路，最大流量为1；将该增广路最大流量赋予流量网络，得到新的残余网络；残余网络中找不到增广路了。0v1v2v4v31000在从v1->v2时，下一步有两种选择，需要回溯穷举所有路径，算法效率将很低。二、最大流问题反向容量方法通过标记反向容量，给算法留有后悔的余地；1v1v2