最大流与最小费用流

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

2、常称为最大流问题。tusu1234,u u u utusu2 定义20 设有向连通图 的每条边上有非负数称 为边容量，仅有一个人次为0的点 称为发点（源），一个出次为0的点 称为收点 （汇），其余点为中间点，这样的网络G称为容量网络，常记做 。 对任一G中的边 有流量，称集合 为G的一个流。称满足下列条件的流 为可行流： （1）容量限制条件：对G中每条边， 有 （2）平衡条件：对中间点 ，有 （即中间点 的物资的输入量与输出量相等） 对收、发点 有 （即从 点发出的物资总量等于 点输入量）W为网络流的总流量。tususijtijffW,tsu uivijkijkffiv0ijijfc ijff

3、ijf,ijv v,GV E Ctvsvijc,ijv v,GV EG3 可行流总是纯在的，例如 就是一个流量为0的可行流。所谓最大流问题就是在容量网络中，寻找流量最大的可行流。 一个流 ，当 则称流 对边 是饱和的，否则称 对 不饱和。最大流问题实际是个线性规划问题，但是利用它与图的紧密关系，能更为直观简便地求解。 定义21 容量网络 为发、收点，若有边集 为E的子集，将G分为两个子图 其顶点集合分别记 分属 ，满足： 不连通； 为 的真子集，而 仍连通，则称 为G的割集，记 。,ES S E,G V EEEE,G V EE,S S,stv v, ,S S SS SS 12,G GE, ,s

4、tGV E Cv v,ijv vf,ijv vf,ijijfc ijff 0f 4 割集 中所有始点在S，终点在 的边的容量之和，称为 的割集容量，记为 。如图5-41中，边集 和边集 都是G的割集，它们割集容量分别为9和11。容量网络G的割集有多个，其中割集容量最小者称为网络G的最小割集容量（简称最小割）。 二、最大流-最小割 定理 由割集的定义不难看出，在容量网络中割集是由 到 的必经之路，无论拿掉哪个割集， 到 便不再相通，所以任何一个可行流的流量不会超过任一割集的容量，也即网络的最大流与最小割容量（最小割）满足下面定理。tvsvtvsv 134,sssv vv vv v 1132334

5、,sttv vv vv vv vv v,C S S,S SS,S S5 定理10 设f为网络G=(V,E,C)的任一可行流，流量为 是分离 的任一割集，则有 由此可知，若能找到一个可行流 一个割集 ，使得 的流量 ，则 一定是最大流，而 就是所有割集中容量最小的一个。下面证明最大流-最小割定理，定理的证明实际上就是给出了寻找最大流的方法。 定理11（最大流-最小割定理）任一网络G中，从 到 的最大流的流量等于分高 的最小割的容量。,stv vtvsv,SSf,WC SSf,SS,f,WC S S,stv v,WS S6 证明 设 是一个最大流，流量为W，用下面的方法定义点集 令 若点 且 则令

6、 若点 且 则令 在这种定义下， 一定不属于 ，若否， ,则得到一条从 到 的链 ，规定 到 为链 的方向，链上与 方向一致的边叫前向边，与 方向相反的边称为后向边，即 如图5-42中 为前向边 为后向边。 根据 的定义， 中的前向边 上必有 ，后向边上必有0ijfijijfc,ijv vS32,v v12,v vtvsvtvsvtvSStvjvS0,jif,ivSjvS,ijijfc,ivS;svSSf7 令 当 为前向边 当 为后向边 取 ，显然 。 我们把 修改为 ： 为 上前向边 为 后向边 其余 不难验证 仍为可行流（即满足容量限制条件与平衡条件），但是 的总流量等于 的流加 ，这与

7、 为最大流矛盾，所以 不属于 。Stvff1f1f,ijv v,ijv v1ijijijffff1ff0 minij,ijv v,ijv vijijijijcff8 令 ，则 。 于是得到一个割集 ，对割集中的边 显然有 但流量W又满足 所以最大流的流量等于最小割的容量，定理得到证明。 定义22 容量网络G，若 为网络中从 到 的一条链，给 定向为从 到 , 上的边凡与 同向称为前向边，凡与 反向称为后向边，其集合分别用和 表示，f是一个可行流，如果满足tvSvtvSv,ijijijJiijvSvSvSvSWffc,0,ijijijjicvSvSfvSvS,ijv v,SStvSVSS9 则称

8、 为从 到 的（关于f的）可增广链。 推论 可行流f是最大流的充要条件是不存在从 到 的（关于f的）可增广链。 可增广链的实际意义是：沿着这条链从 到 输送流，还有潜力可挖，只需按照定理证明中的调整方法，就可以把流量提高，调整后的流，在各点仍满足平衡条件及容量限制条件，即仍为可行流。这样就得到了一个寻求最大流的方法：从一个可行流开始，寻求关于这个可行流的可增广链，若存在，则可以经过调整，得到一个新的可行流，其流量比原来的可行流要大，重复这个过程，直到不存在关于该流的可增广链时就得到了最大流。tvSvtvSvtvSv0,0,ijijijijijijfcv vcfv v10 三、求最大流的标号算法

9、 设已有一个可行流f，标号的方法可分为两步：第 1步是标号过程，通过标号来寻找可增广链；第2 步是调整过程，沿可增广链调整f以增加流量。 1.标号过程 （1）给发点以标号 （2）选择一个已标号的顶点 ，对于 的所有 未标号的邻接点 按下列规则处理： a) 若边 ，且 则令 ， 并给以标号 。 b) 若边 ，且 时，令 并给以标号, ,ijvjvmin,jijjiicfijijfc,ijv vE,iivmin,jjiif0,jif,ijv vEjviviv11 （3）重复（2）直到收点 被标号或不再有顶点可标号时为止。 如若 得到标号，说明存在一条可增广链，转（第2步）调整过程。若 未获得标号，

10、标号过程已无法进行时，说明f已是最大流。 2. 调整过程 若 是可增广链上的前向边 （1）令 若 是可增广链上的后向边 若 不存在可增广链上 （2）去掉所有标号，回到第1步，对可行流 重新标号。f ,ijv v,ijv v,ijv vjiijjijifffftvtvtv12 例5.17 图5-43表明一个网络及初始可行流，每条边上的有序数表示 ，求这个网络的最大流。 先给 标以 。 检查 的邻接点 发现点 满足 且 令 ，给 以标号 。同理给 点以标号 。 检查 点的尚未标号的邻接点 发现 满足 且 令 给 以标号 。2,2v5v5min 3,22,v252503,fc25,v vE5v56,

11、v v2v,1sv3v2v2min 2,2v 2224,ssfc2,sv vE2v123,v v vsv, sv,ijijcf,1sv13 检查与 点邻接的未标号点有 ，发现 点满足 且 ，令 则给 点以标号 。 点未标号，与 邻接，边 且 所以令 给 以标 号 。 类似前面的步骤，可由 得到标号 。 由于 已得到标号，说明存在增广链，所以标号过程结束，见图5-44。tv4,2v4vtv1,2v4v4min 3,22,v141425,fc14,v vE1v4v5,2v1v1min 3,22,v1530f15,v vE1v1,tv v5v14 转入调整过程，令 为调整量，从 点开始，由逆增广链方

12、向按标号 找到点，令 。 再由 点标号 找到前一个点 ，并令 。按 点标号找到点 。 由于标号为 为反向边，令 由 点的标号在找到 ，令 。 由 点找到 ，令 调整过程结束，调整中的可增广链见图5-44，调整后的可行流见图5-45。222ssff sv2v25252ff 2v5v15152ff 551,vv v5v1v14142ff 1v1,2v4v442ttff 4v4,2vtv2vt15 重新开始标号过程，寻找可增广链，当标到 点为 以后，与 点邻接的 点都不满足标号条件，所以标号无法再继续，而 点并为得到标号，如图5-45。 这时 ，即为最大流的流量，算法结束。 用标号法在得到最大流的同

13、时，可得到一个最小割。即图5-45中虚线所示。 标号点集合为s，即 未标号点集合为 此时割集 1236,ssS Sv vv vv v12456,tSv v v v v v3,SSv v12345611ssstttWfffffftv126,v v v3,sv v,1sv3v16 割集容量 ，与最大流的流量相等。 由此也可以体会到最小割的意义，网络从发点到收点的各 通路中，由容量决定其通过能力，最小割则是这此路中的 咽喉部分，或者叫瓶口，其容易最小，它决定了整个网络 的最大通过能力。要提高整个网络的运输能力，必须首先 改造这个咽喉部份的通过能力。 求最大流的标号算法还可用于解决多发点多收点网络的最

14、 大刘问题，设容量网络G有若干发点 ；若干个 收点 可以添加两个新点 ，用容量为 的有 向边分别连结 得到新的网 络 ， 为只有一个发点 一个收点 的网络，求解 的 最大流问题即可得到G的解，如图5-46。1236,11ssC S ScccGtv,svGG1212,smntvx xxy yyv与与,stv v12,ny yy12,mx xx17 四、最大匹配问题四、最大匹配问题 考虑工作分配问题。有n个工人，m件工作，每个工人能 力不同，各能胜任其中某几项工作。假设每件工作只需要 一人坐，每人只做一件工作，怎样分配才能尽量的工作有 人做，更多的人有工作？ 这个问题可以用土的语言描述，如图5-4

15、7。其中 表示工作，边 个人能胜任第 项工作，这样就得到了一个二部图 G，用点集X表示 ，点集Y表示 ， 二部图 。上述的工作分配问题就是要在途G 中找一个边集E的子集，使得集中任何两条边没有公共端 点，最好的方案就是要使此边集的边数尽可能多，这就是 匹配问题。(, ,)GX Y E12 ,my yy12 ,nx xxjy( ,)ijix yx表示第1212,nmx xxy yy表示工人18 定义定义2323 二部图 ，M是边集E的子集，若M中的任意两条边都没有公共端点，则称M为图G的一个匹配（也称对集）。 M中任意条边的端点v称为（关于M的）饱和点，G中其他定点称为非饱和点。 若不存在另一条

16、匹配 ，则称M为最大匹配。 例如图5-48种用粗线标出的各边组成图G的一个匹配 ，且为最大匹配。图5-48还有另一最大匹配由边 组成，即一个土的最大匹配中所含边数是确定的，但匹配方案可以不同。11253443( ,),(,),(,),(,)x yxyxyxy11253243( ,),(,),(,),(,)Mx yxyxyxy1MM1使得 M(, ,)GX Y E19 二部图中最大匹配问题，可以化为最大流问题。在二部图中增加两个新点 分别作为发点、收点，并拥有向边把他们与原二部图中顶点相连，另全部边上的容量均为1。那么当这个网络的流达到最大时，如果 上的流量为1，就让 工作，这样的方案就是最大匹

17、配的方案。 例5.18 设有5位待业者，5项工作，他们各自能胜任工作情况如图5-49所示，要求设计一个新业方案，使尽量多的人能就业。 解 按前述方法增加虚拟的发、收点 ，用求最大流的标号法求解得到图5-49，在图中略去容量，只标出流量。边 上的流量都是1，所以让 工作可得最大就业方案，即最多可以安排四个人就业。12352154,x x x xyy yy分别干12213554( ,),(,),(,),(,)x yxyx yxy,stv vijxy作( ,)iix y1,vvs20 例5.19 有5批货物，要用船只从 地。规定每批货物出发日期如表5-4所示，又知船只航行所需时间（天）如表5-5所示

18、。每批货物只需一条船装运，船只在空载和重载时航行时间相同，要求制定一个计划，以最小的船只完成这5项运输任务。 设 分别为每项运输任务的出发日期 完成日期。则由表5-4和表5-5知：111222232315721013312134135810iiiabxyxyxyxyxy任务(1,2,3,4,5 )ix,iia b12123,x xy yy地分别运往21 还可以求出第i项运输任务到j项运输任务所需的转移时间，用 表示。如第一项任务是从 地，第二项任务是由 地，其转移时间就是船只要由 地所需的时间，由表5-5知需2天，即 。类似可求出；1314152123242531323435414243455

19、15253541113111331122222222ttttttttttttttttttt122t11yx地返回12xy地运货到11xy地运货到(1,2,3,4,5;1,2,3,4,5)ijtij22 做一个二部图，点集X与Y都表示1，2，3，4，5五项任务，点i，j间有边的条件是第i件任务完成后可以转去作第j键，即满足 者，如图5-50。如X集中点1到Y集中点2有边是因为 10，满足7+210，也即一条船于5日出发完成第一项运货任务，7日到达目的地 ，空船2天返回 地还来得及于10日再去作第二次运输任务。求出上述二部图的一个最大匹配 。如 ：（1，2），（4，5），（5，3），说明一条船可以

20、完成任务1后接着完成任务2，另一条船则可以连续完成任务4、任务5、任务3，即所需最少船只数为 。2|5 MMM1x1y11227,2,bta而iijjbta23第五节 最小费用流问题 上一节讨论的寻求网络最大流问题，只考虑了流的数量， 没有考虑流的费用。实际上许多问题要考虑流的费用最小 问题。 最小费用流问题的一般提法：已知容量网络G=(V,E,C), 每条边 除了已给的容量 外还，给出了单位流量的 费用 ，记G=(V,E,C,d)。求G的一个可行流 使得流量 ，且总费用 最小 特别地，当要求 为最大流量时，此问题即为最小费用最 大流问题。 最小费用流问题的常用算法有两种：（1）原始算法，（2

21、）对偶算法。下面只介绍第二种算法，本算法是由性交算法。fEvvijijjifdfd),()(vfW)(ijff )0(ijdijcjivv ,24 定义 24 已知网络G=(V,E,C ,d)， 是G上的一 份可行流， 为从 到 的（关于 的）可增广 链， 称为链 的费用。 如图5-51所示的可增广链 中， 边上权为费用 ，则链 的费用 =（3+4+1+6）-（5+7）=2。 若 是从 到 所有可增广链中费用最小的链， 则称 为最小费用可增广链。*tvsv*)(dijd),(),(:4512vvvv),(),(),(),(:543321tsvvvvvvvvijijddd)(ftvsvf25 对

22、偶算法的基本思路： 限制奥一个流量为 的最小费用流 ，后然寻找从 到 可广增链 ，用最大流方法将 调整到 ，使 流量为 ，并保证 是在 流量下的最小费用流，不断进行到 为止。 定理 12 若 是流量为 的最小费用流， 是关于 的从 到 的一条最小费用可增广链，则 经过 调整流量 得到新可流量 ，一定是流量为 的可行流中的最小费用。 由于 就是流量为0的最小费用流，所以初始最小费用流可以取 ，余下的问题是如何寻找关于f的最小费用可增广链。为了计算方便：我们构造长度网络。0)0(f0, 0fdij)( fW)(fffftvsvf)( fWfvfWk)()()(0fW)1 (f)(0fW)1 (f)

23、1(f)0(ftvsv)0(f0)(0fW26 定义25 对网络G=（V，E，C，d），有可行流 f，保持原网络各点，每条边用两条方向相反的有 向边代替，各边的权 按如下规则： （1）当边 ，令 （其中 的意义是：这条边已饱和，不能增大流量，否则要花费很高的代价，实际无法实现，因此权为 的边可从网络中去掉。） （2）当边 为原来G中边 的反向边，令 （这里 的意义是此边流量已减少到0，不能再减少，权为 的边也可以去掉。）00ijijijjiffdl当当),(jivv),(ijvvijijijijijijcfcfdl当当Evvji),(ijl27 这样得到的网络 称为长度网络（将费用看成长度）。 显然在G中求关于f的最小费用可增广链等价于在长度网络 中求从 到 的最短路。 对偶算法的基本步骤如下