第四节最大流问题优秀课件.ppt
第四节最大流问题第1页，本讲稿共28页第2页，本讲稿共28页定义20 设有向连通图 的每条边上有非负数称 为边容量，仅有一个r入次为0的点 称为发点（源），一个出次为0的点 称为收点（汇），其余点为中间点，这样的网络G称为容量网络，常记做 。对任一G中的边 有流量，称集合 为G的一个流。称满足下列条件的流 为可行流：（1）容量限制条件：对G中每条边，有（2）平衡条件：对中间点 ，有（即中间点 的物资的输入量与输出量相等）对收、发点 有（即从 点发出的物资总量等于 点输入量）W为网络流的总流量。第3页，本讲稿共28页可行流总是存在的，例如 就是一个流量为0的可行流。所谓最大流问题就是在容量网络中，寻找流量最大的可行流。一个流 ，当 则称流 对边 是饱和的，否则称 对 不饱和。最大流问题实际是个线性规划问题，但是利用它与图的紧密关系，能更为直观简便地求解。定义21 容量网络 为发、收点，若有边集 为E的子集，将G分为两个子图 其顶点集合分别记 分别属于 ，满足：不连通；为 的真子集，而 仍连通，则称 为G的割集，记 。第4页，本讲稿共28页割集 中所有始点在S，终点在 的边的容量之和，称为 的割集容量，记为 。如图5-41中，边集 和边集 都是G的割集，它们割集容量分别为9和11。容量网络G的割集有多个，其中割集容量最小者称为网络G的最小割集容量（简称最小割）。二、最大流-最小割 定理由割集的定义不难看出，在容量网络中割集是由 到 的必经之路，无论拿掉哪个割集，到 便不再相通，所以任何一个可行流的流量不会超过任一割集的容量，也即网络的最大流与最小割容量（最小割）满足下面定理。第5页，本讲稿共28页定理10 设f为网络G=(V,E,C)的任一可行流，流量为 是分离 的任一割集，则有 由此可知，若能找到一个可行流 一个割集 ，使得 的流量 ，则 一定是最大流，而 就是所有割集中容量最小的一个。下面证明最大流-最小割定理，定理的证明实际上就是给出了寻找最大流的方法。定理11（最大流-最小割定理）任一网络G中，从 到 的最大流的流量等于分高 的最小割的容量。第6页，本讲稿共28页证明 设 是一个最大流，流量为W，用下面的方法定义点集 令 若点 且 则令 若点 且 则令 在这种定义下，一定不属于 ，若否，则得到一条从 到 的链 ，规定 到 为链 的方向，链上与 方向一致的边叫前向边，与 方向相反的边称为后向边，即 如图5-42中 为前向边 为后向边。根据 的定义，中的前向边 上必有 ，后向边上必有第7页，本讲稿共28页第8页，本讲稿共28页 令 当 为前向边 当 为后向边 取 ，显然 。我们把 修改为 ：为 上前向边 为 后向边 其余不难验证 仍为可行流（即满足容量限制条件与平衡条件），但是 的总流量等于 的流加 ，这与 为最大流矛盾，所以 不属于 。第9页，本讲稿共28页令 ，则 。于是得到一个割集 ，对割集中的边 显然有但流量W又满足所以最大流的流量等于最小割的容量，定理得到证明。定义22 容量网络G，若 为网络中从 到 的一条链，给 定向为从 到 ,上的边凡与 同向称为前向边，凡与 反向称为后向边，其集合分别用和 表示，f是一个可行流，如果满足第10页，本讲稿共28页 则称 为从 到 的（关于f的）可增广链。推论 可行流f是最大流的充要条件是不存在从 到 的（关于f的）可增广链。可增广链的实际意义是：沿着这条链从 到 输送流，还有潜力可挖，只需按照定理证明中的调整方法，就可以把流量提高，调整后的流，在各点仍满足平衡条件及容量限制条件，即仍为可行流。这样就得到了一个寻求最大流的方法：从一个可行流开始，寻求关于这个可行流的可增广链，若存在，则可以经过调整，得到一个新的可行流，其流量比原来的可行流要大，重复这个过程，直到不存在关于该流的可增广链时就得到了最大流。第11页，本讲稿共28页 三、求最大流的标号算法设已有一个可行流f，标号的方法可分为两步：第 1步是标号过程，通过标号来寻找可增广链；第2 步是调整过程，沿可增广链调整f以增加流量。1.标号过程（1）给发点以标号（2）选择一个已标号的顶点 ，对于 的所有 未标号的邻接点 按下列规则处理：a)若边 ，且 则令 ，并给以标号 。b)若边 ，且 时，令 并给以标号第12页，本讲稿共28页（3）重复（2）直到收点 被标号或不再有顶点可标号时为止。如若 得到标号，说明存在一条可增广链，转（第2步）调整过程。若 未获得标号，标号过程已无法进行时，说明f已是最大流。2.调整过程 若 是可增广链上的前向边（1）令 若 是可增广链上的后向边 若 不存在可增广链上（2）去掉所有标号，回到第1步，对可行流 重新标号。第13页，本讲稿共28页例5.17 图5-43表明一个网络及初始可行流，每条边上的有序数表示 ，求这个网络的最大流。先给 标以 。检查 的邻接点 发现点 满足 且 令 ，给 以标号 。同理给 点以标号 。检查 点的尚未标号的邻接点 发现 满足 且 令 给 以标号 。第14页，本讲稿共28页第15页，本讲稿共28页检查与 点邻接的未标号点有 ，发现 点满足 且 ，令 则给 点以标号 。点未标号，与 邻接，边 且 所以令 给 以标 号 。类似前面的步骤，可由 得到标号 。由于 已得到标号，说明存在增广链，所以标号过程结束，见图5-44。第16页，本讲稿共28页第17页，本讲稿共28页转入调整过程，令 为调整量，从 点开始，由逆增广链方向按标号 找到点，令 。再由 点标号 找到前一个点 ，并令 。按 点标号找到点 。由于标号为 为反向边，令由 点的标号在找到 ，令 。由 点找到 ，令调整过程结束，调整中的可增广链见图5-44，调整后的可行流见图5-45。第18页，本讲稿共28页第19页，本讲稿共28页重新开始标号过程，寻找可增广链，当标到 点为 以后，与 点邻接的 点都不满足标号条件，所以标号无法再继续，而 点并为得到标号，如图5-45。这时 ，即为最大流的流量，算法结束。用标号法在得到最大流的同时，可得到一个最小割。即图5-45中虚线所示。标号点集合为s，即未标号点集合为此时割集第20页，本讲稿共28页割集容量 ，与最大流的流量相等。由此也可以体会到最小割的意义，网络从发点到收点的各通路中，由容量决定其通过能力，最小割则是这此路中的咽喉部分，或者叫瓶口，其容易最小，它决定了整个网络 的最大通过能力。要提高整个网络的运输能力，必须首先改造这个咽喉部份的通过能力。求最大流的标号算法还可用于解决多发点多收点网络的最大刘问题，设容量网络G有若干发 ；若干个收点 可以添加两个新点 ，用容量为 的有向边分别连结 得到新的网络 ，为只有一个发点 一个收点 的网络，求解 的最大流问题即可得到G的解。第21页，本讲稿共28页课堂练习1求下面网络最大流，边上数为vsv4v1v5v2vtv3(4,3)(10,4)(3,2)(1,1)(4,2)(3,2)(5,3)(4,3)(3,2)(7,6)(2,2)(8,3)第22页，本讲稿共28页最大匹配问题：考虑工作分配问题。有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的子集，使得集中任何两条边没有公共端点，最好的方案就是要使此边集的边数尽可能多，这就是匹配问题。第23页，本讲稿共28页定义定义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给出的,称为匈牙利算法：基本思想：寻找非饱和点-寻找可扩路-作对称差第24页，本讲稿共28页第25页，本讲稿共28页求二部图G中的最大匹配？X1Y1Y2Y3Y4X2X3X4第26页，本讲稿共28页 M x S B N(s)Px2y2,x3y3x1x1y2y2饱和点y2x2x1,x2y2y1,y2,y4y1非饱和点x1y2x2y1x1y2,x2,y1,x3y3x4x4y2,y3y2饱和y2x1x4,x1y2y2,y3y3饱和y3x3x4,x1,x3y2,y3y2,y3N(s)=B结束第27页，本讲稿共28页最大匹配就是：X1Y1Y2Y3Y4X2X3X4第28页，本讲稿共28页
