第四节 最大流问题.ppt

上传人:tireattitude366 文档编号:380255 上传时间:2018-10-09 格式:PPT 页数:28 大小:762KB
下载 相关 举报
第四节 最大流问题.ppt_第1页
第1页 / 共28页
第四节 最大流问题.ppt_第2页
第2页 / 共28页
第四节 最大流问题.ppt_第3页
第3页 / 共28页
第四节 最大流问题.ppt_第4页
第4页 / 共28页
第四节 最大流问题.ppt_第5页
第5页 / 共28页
亲,该文档总共28页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述

1、第四节 最大流问题,最大流问题是一类应用极为广泛的问题,例如在交通运输网络中有人流、车流、货物流,供水网络中有水流,金融系统中有现金流,通讯系统中有信息流,等等。50年代福特(Ford)、富克逊(Fulkerson)建立的“网络流理论”,是网络应用的重要组成部分。一、最大流有关概念 如果我们把图5-41年做输油管道网, 为起点, 为终点, 为中转站,边上的数表示该管道的最大输油能力,问应该如何安排各管道输油量,才能使从 到 的总输油量最大? 管道网络中每边的最大通过能力即容量是有限的,实际流量也不一定等于容量,上述问题就是要讨论如何充分利用装置的能力,以取得最好效果(流量最大),这类问题通常称

2、为最大流问题。,定义20 设有向连通图 的每条边上有非负数称 为边容量,仅有一个r入次为0的点 称为发点(源),一个出次为0的点 称为收点(汇),其余点为中间点,这样的网络G称为容量网络,常记做 。 对任一G中的边 有流量,称集合 为G的一个流。称满足下列条件的流 为可行流:(1)容量限制条件:对G中每条边, 有(2)平衡条件:对中间点 ,有(即中间点 的物资的输入量与输出量相等) 对收、发点 有(即从 点发出的物资总量等于 点输入量)W为网络流的总流量。,可行流总是存在的,例如 就是一个流量为0的可行流。所谓最大流问题就是在容量网络中,寻找流量最大的可行流。 一个流 ,当 则称流 对边 是饱

3、和的,否则称 对 不饱和。最大流问题实际是个线性规划问题,但是利用它与图的紧密关系,能更为直观简便地求解。 定义21 容量网络 为发、收点,若有边集 为E的子集,将G分为两个子图 其顶点集合分别记 分别属于 ,满足: 不连通; 为 的真子集,而 仍连通,则称 为G的割集,记 。,割集 中所有始点在S,终点在 的边的容量之和,称为 的割集容量,记为 。如图5-41中,边集和边集 都是G的割集,它们割集容量分别为9和11。容量网络G的割集有多个,其中割集容量最小者称为网络G的最小割集容量(简称最小割)。二、最大流-最小割 定理 由割集的定义不难看出,在容量网络中割集是由 到 的必经之路,无论拿掉哪

4、个割集, 到 便不再相通,所以任何一个可行流的流量不会超过任一割集的容量,也即网络的最大流与最小割容量(最小割)满足下面定理。,定理10 设f为网络G=(V,E,C)的任一可行流,流量为 是分离 的任一割集,则有 由此可知,若能找到一个可行流 一个割集 ,使得 的流量 ,则 一定是最大流,而 就是所有割集中容量最小的一个。下面证明最大流-最小割定理,定理的证明实际上就是给出了寻找最大流的方法。 定理11(最大流-最小割定理)任一网络G中,从 到 的最大流的流量等于分高 的最小割的容量。,证明 设 是一个最大流,流量为W,用下面的方法定义点集 令 若点 且 则令 若点 且 则令 在这种定义下,

5、一定不属于 ,若否, 则得到一条从 到 的链 ,规定 到 为链 的方向,链上与 方向一致的边叫前向边,与 方向相反的边称为后向边,即 如图5-42中 为前向边 为后向边。 根据 的定义, 中的前向边 上必有,后向边上必有,令 当 为前向边 当 为后向边取 ,显然 。 我们把 修改为 :为 上前向边 为 后向边 其余 不难验证 仍为可行流(即满足容量限制条件与平衡条件),但是 的总流量等于 的流加 ,这与 为最大流矛盾,所以 不属于 。,令 ,则 。 于是得到一个割集 ,对割集中的边 显然有但流量W又满足所以最大流的流量等于最小割的容量,定理得到证明。 定义22 容量网络G,若 为网络中从 到

6、的一条链,给 定向为从 到 , 上的边凡与 同向称为前向边,凡与 反向称为后向边,其集合分别用和 表示,f是一个可行流,如果满足,则称 为从 到 的(关于f的)可增广链。 推论 可行流f是最大流的充要条件是不存在从 到 的(关于f的)可增广链。 可增广链的实际意义是:沿着这条链从 到 输送流,还有潜力可挖,只需按照定理证明中的调整方法,就可以把流量提高,调整后的流,在各点仍满足平衡条件及容量限制条件,即仍为可行流。这样就得到了一个寻求最大流的方法:从一个可行流开始,寻求关于这个可行流的可增广链,若存在,则可以经过调整,得到一个新的可行流,其流量比原来的可行流要大,重复这个过程,直到不存在关于该

7、流的可增广链时就得到了最大流。,三、求最大流的标号算法 设已有一个可行流f,标号的方法可分为两步:第1步是标号过程,通过标号来寻找可增广链;第2步是调整过程,沿可增广链调整f以增加流量。1.标号过程(1)给发点以标号(2)选择一个已标号的顶点 ,对于 的所有未标号的邻接点 按下列规则处理:a) 若边 ,且 则令 ,并给以标号 。b) 若边 ,且 时,令 并给以标号,(3)重复(2)直到收点 被标号或不再有顶点可标号时为止。 如若 得到标号,说明存在一条可增广链,转(第2步)调整过程。若 未获得标号,标号过程已无法进行时,说明f已是最大流。2. 调整过程若 是可增广链上的前向边(1)令 若 是可

8、增广链上的后向边 若 不存在可增广链上(2)去掉所有标号,回到第1步,对可行流 重新标号。,例5.17 图5-43表明一个网络及初始可行流,每条边上的有序数表示 ,求这个网络的最大流。 先给 标以 。 检查 的邻接点 发现点 满足且 令 ,给 以标号 。同理给 点以标号 。 检查 点的尚未标号的邻接点 发现 满足 且 令 给 以标号 。,检查与 点邻接的未标号点有 ,发现 点满足 且 ,令则给 点以标号 。点未标号,与 邻接,边 且所以令 给 以标号 。类似前面的步骤,可由 得到标号 。 由于 已得到标号,说明存在增广链,所以标号过程结束,见图5-44。,转入调整过程,令 为调整量,从 点开始

9、,由逆增广链方向按标号 找到点,令 。 再由 点标号 找到前一个点 ,并令 。按 点标号找到点 。 由于标号为 为反向边,令 由 点的标号在找到 ,令 。 由 点找到 ,令 调整过程结束,调整中的可增广链见图5-44,调整后的可行流见图5-45。,重新开始标号过程,寻找可增广链,当标到 点为 以后,与 点邻接的点都不满足标号条件,所以标号无法再继续,而 点并为得到标号,如图5-45。 这时 ,即为最大流的流量,算法结束。 用标号法在得到最大流的同时,可得到一个最小割。即图5-45中虚线所示。 标号点集合为s,即 未标号点集合为 此时割集,割集容量 ,与最大流的流量相等。 由此也可以体会到最小割

10、的意义,网络从发点到收点的各通路中,由容量决定其通过能力,最小割则是这此路中的咽喉部分,或者叫瓶口,其容易最小,它决定了整个网络 的最大通过能力。要提高整个网络的运输能力,必须首先改造这个咽喉部份的通过能力。求最大流的标号算法还可用于解决多发点多收点网络的最大刘问题,设容量网络G有若干发 ;若干个收点 可以添加两个新点 ,用容量为 的有向边分别连结 得到新的网络 , 为只有一个发点 一个收点 的网络,求解 的最大流问题即可得到G的解。,课堂练习1 求下面网络最大流,边上数为,vs,v4,v1,v5,v2,vt,v3,(4,3),(10,4),(3,2),(1,1),(4,2),(3,2),(5

11、,3),(4,3),(3,2),(7,6),(2,2),(8,3),最大匹配问题:考虑工作分配问题。有n个工人,m件工作,每个工人能力不同,各能胜任其中某几项工作。假设每件工作只需要一人做,每人只做一件工作,怎样分配才能尽量的工作有人做,更多的人有工作? 这个问题可以用图的语言描述,如图5-47。其中x1,x2,xn表示工人,y1,y2,ym表示工作,边(xi,yj)表示第i个人能胜任第j项工作,这样就得到了一个二部图G,用点集X表示x1,x2,xn,点集Y表示y1,y2,ym ,二部图G=(X,Y,E)。上述的工作分配问题就是要在图G中找一个边集E的子集,使得集中任何两条边没有公共端点,最好

12、的方案就是要使此边集的边数尽可能多,这就是匹配问题。,定义23 二部图 G=(X,Y,E) ,M是边集E的子集,若M中的任意两条边都没有公共端点,则称M为图G的一个匹配(也称对集)。 M中任意一条边的端点v称为(关于M的)饱和点,G中其他定点称为非饱和点。 若不存在另一条匹配 ,则称M为最大匹配。 设M是G的一个匹配,P是G的一条道路,若P中的边是M与E(G)-M中的边交替出现的,则称P为M交错路;若起点和终点都是M非饱和点,则称P为M可扩路。如何寻找二部图中的最大匹配问题?最早是由匈牙利数学家Egervary给出的,称为匈牙利算法: 基本思想:寻找非饱和点-寻找可扩路-作对称差,求二部图G中的最大匹配?,X1,Y1,Y2,Y3,Y4,X2,X3,X4,最大匹配就是:,X1,Y1,Y2,Y3,Y4,X2,X3,X4,

展开阅读全文
相关资源
猜你喜欢
相关搜索

当前位置:首页 > 教学课件 > 大学教育

copyright@ 2008-2019 麦多课文库(www.mydoc123.com)网站版权所有
备案/许可证编号:苏ICP备17064731号-1