没有幻灯片标题复旦大学精品课程

1、8.2网络最大流网络最大流 运输网络问题是很大一类网络问题，通运输网络问题是很大一类网络问题，通过介绍有些运输网络问题，可以使我们过介绍有些运输网络问题，可以使我们建立起一些处理网络问题的基本概念和建立起一些处理网络问题的基本概念和方法。方法。 这里涉及的运输网络问题只是考虑简单这里涉及的运输网络问题只是考虑简单情况。情况。 一、运输网络一、运输网络 1.运输网络的定义运输网络的定义 定义定义 8.7：一个带权有向图：一个带权有向图G=(V,E)若满足如下条件：若满足如下条件： (1)G是连通无自环的；是连通无自环的； (2)每条弧每条弧(i,j)的权的权cij为非负整数，称为弧的容量，为非负

2、整数，称为弧的容量，cij全体所构成的集合记为全体所构成的集合记为C； (3)存在存在2个不同的顶点个不同的顶点s和和t。 则称该有向图为则称该有向图为运输网络运输网络, 简称网络，记为简称网络，记为N(V,E,C)。称称s为为发点发点, t为为收点收点, 除除s和和t以外其它顶点称为以外其它顶点称为中间中间点点。C称为称为容量函数容量函数。 2.运输网络运输网络N中的流中的流 定义定义 8.8：在网络：在网络N(V,E,C)的弧集的弧集E上定义了一个非上定义了一个非负整值函数负整值函数f=fij, 称称f为网络为网络N上的上的流流, fij称为弧称为弧(i,j)上的上的流量流量。若无弧。若无

3、弧(i,j), 则则fij定义为定义为0。设流。设流f满足下满足下列条件列条件: (1)容量限制条件：对每一条弧容量限制条件：对每一条弧(i,j), 有有fijcij。 (2)平衡条件：除平衡条件：除s和和t外的每个中间点外的每个中间点k, 有有 即流出和等于流入和。即流出和等于流入和。 对于对于s和和t有有 则称则称f为网络为网络N的一个的一个可行流可行流, Vf为为流流f的值的值, 或称或称f的的流量流量。 若若N中无可行流中无可行流f, 使使VfVf, 则称则称f为为最大流最大流。VjjkVikifffVitiVjjtVjjsVisiVffff 定义定义 8.9：若：若fij=cij,

4、则称弧则称弧(i,j)是是饱和的饱和的; 若若fij0, 则称弧则称弧(i,j)是是f-正正的的. 现在的关键是如何求最大流的值。现在的关键是如何求最大流的值。割割(P,P)的容量是它的每条弧的容量之和的容量是它的每条弧的容量之和,记为记为 C(P,P)即即:PjPiijcPPC,),(对于不同的割对于不同的割, 它的容量显然是不同的。它的容量显然是不同的。4.运运输输网网络络中中流流和和割割的的关关系系定定理理 8.4:对对于于给给定定的的网网络络N=(V,E,C), 对对任任一一 可可 行行 流流f和和 任任 一一 割割(P,P), 成成 立立Vf C(P,P)。证证明明：因因为为f是是可

5、可行行流流，根根据据流流的的平平衡衡条条件件可可知知：对对于于发发点点s P有有fVjjsVisiVff （1）对对于于P中中不不是是发发点点s和和收收点点t的的中中间间点点k有有VjjkVikiff0VjjkVikiff （2） 二、最大流最小割定理二、最大流最小割定理 引理：对于给定的网络引理：对于给定的网络N=(V,E,C), 若可若可行流行流f和割和割(P,V-P), 成立成立Vf=C(P,V-P)，则则Vfmax=Vf，Cmin(P,V-P)=C(P,V-P)。 因此求最大流的一个想法就是构造流和因此求最大流的一个想法就是构造流和割，使得流量和割容量相等。割，使得流量和割容量相等。

6、福特福特,富克逊富克逊(Frod,Falkerson)于于1956 年给年给出的最大流最小割定理出的最大流最小割定理 基本思想：基本思想： 1）对任意网络构造初始流。）对任意网络构造初始流。 零流零流,或其他可行流。或其他可行流。 2）在初始流基础上寻找可增加流的路，）在初始流基础上寻找可增加流的路，这样的路称为增广路。并在寻找增广路这样的路称为增广路。并在寻找增广路的同时，计算在该路上可增加多少流。的同时，计算在该路上可增加多少流。 3）若找到了从）若找到了从s到到t的可增加流的路，则的可增加流的路，则修改流，得到新的可行流。然后转回修改流，得到新的可行流。然后转回2） (1)怎样找增广路怎

7、样找增广路 (2)如果找不到这样的增广路，是否此时如果找不到这样的增广路，是否此时的流就是最大流？的流就是最大流？ 1.寻找增广路的方法寻找增广路的方法 设设u为为s到到t的路（不考虑弧的方向）的路（不考虑弧的方向） (1)先考察该路上与路方向一致的弧先考察该路上与路方向一致的弧(称为称为向前弧向前弧)。 若路上所有弧均为向前弧，且每条弧的若路上所有弧均为向前弧，且每条弧的流量流量相应弧的容量，则可增加流的路。相应弧的容量，则可增加流的路。 对于向前弧对于向前弧(i,j)，fij是否是否cij。 可增加流的通路，采用标号法。可增加流的通路，采用标号法。 1)对源点对源点s标号标号(-) 2)设

8、点设点i已经标号，已经标号，j点没有标，对于向前点没有标，对于向前弧弧(i,j)，若若fijcij，则点则点j标号标号i+；若若fij=cij，则点则点j不标号。不标号。 3)若收点若收点t最后被标号，如最后被标号，如t点被标号点被标号c+，则找到了从则找到了从s到到t的增广路。的增广路。 还需要知道这条路可增加多少流量，以还需要知道这条路可增加多少流量，以便修改流。便修改流。 1)对源点对源点s标号标号(-),令令s=+。 2)设点设点i已经标号，增量为已经标号，增量为i，j点没有标，点没有标，对于向前弧对于向前弧(i,j)，若若fij0，则则c点标号点标号(b-,c)，这里这里c=minb

9、, fcb。 0)对任意网络构造初始流。对任意网络构造初始流。 1)对源点对源点s标号标号(-，+)。 2)设点设点i已经标号，增量为已经标号，增量为i，j点没有标，点没有标， i)对于向前弧对于向前弧(i,j)，若若fij0，则则j点标号点标号(i-,j)， 这里这里j=mini, fji。 若若fij=0，则点则点j不标号。不标号。 (3)重复第重复第2步，直到步，直到 i)若收点若收点t最后被标号最后被标号(x+,t)，这就找到了从这就找到了从s到到t的增广路，的增广路，可增加的流量是可增加的流量是t。 修改流时，对该路上所有向前弧流量修改流时，对该路上所有向前弧流量+t，向后弧上的向后

10、弧上的流量减少流量减少t，并以此结果作为新的流，转向并以此结果作为新的流，转向1)。 ii)若不再有新的顶点被标号，且若不再有新的顶点被标号，且t仍没有被标号，则说明仍没有被标号，则说明网络中的流为最大流网络中的流为最大流 定理：用上述标号法在算法停止时得到定理：用上述标号法在算法停止时得到的一定是最大流。的一定是最大流。 证明：算法停止时证明：算法停止时,已经标号的点构成集已经标号的点构成集合合P，没有标号的构成没有标号的构成V-P，则，则(P,V-P)构构成割。然后证明网络中的流的值就等于成割。然后证明网络中的流的值就等于该割的容量。该割的容量。 关于算法有关于算法有2点要说明：点要说明：

11、 1)在某点有多种标号选择时，可任意选在某点有多种标号选择时，可任意选择择1种进行标号。种进行标号。 2)初始流不一定是零流，只要是可行流初始流不一定是零流，只要是可行流即可。即可。8.3图与二分图的匹配图与二分图的匹配 一、匹配的概念一、匹配的概念 定义定义 8.11：在图：在图 G=(V,E)中中, M是边集是边集E的子集的子集,并且并且M中没有两条边相邻中没有两条边相邻, 称称M是是G的一个的一个匹配匹配。定义定义:若若M中的一边关中的一边关联于顶点联于顶点v, 则称则称v为为关关于于M饱和的饱和的。M中的边的两端点称为中的边的两端点称为在在M下下配对配对。定义定义:若若G中每一个顶点是

12、关于中每一个顶点是关于M 饱和的饱和的, 则则称称M为为G的的完美匹配完美匹配。一个图不一定存在完美匹配一个图不一定存在完美匹配 完美匹配不一定唯一完美匹配不一定唯一. 定理定理:无自环的图无自环的图G,若它有完美匹配若它有完美匹配,则则|V(G)|为偶数为偶数. 定义：若定义：若G中不存在匹配中不存在匹配M,使使|M|M|, 则称则称M为为G的的最大匹配最大匹配。图可能有许多不同的最大匹配。图可能有许多不同的最大匹配。完美匹配必是最大匹配完美匹配必是最大匹配, 反之不一定。反之不一定。如果如果G有完美匹配有完美匹配,则它的任一最大则它的任一最大匹配是否一定为完美匹配匹配是否一定为完美匹配?

13、二、匹配的基本定理二、匹配的基本定理 首先引进首先引进2个定义。个定义。 定义定义 8.12：设：设M是是G的一个匹配的一个匹配, (1)若在若在G中有一条路中有一条路,它的边在它的边在E-M和和M中交错中交错地出现地出现, 则称该路为则称该路为关于关于M的交错路的交错路。(2)若关于若关于M的交错路的交错路的起点和终点不是关的起点和终点不是关于于M饱和的饱和的, 则称该路则称该路为为关于关于M的增广路的增广路。 定理：关于定理：关于M的增广路中属于的增广路中属于E-M的边数比属的边数比属于于M的边数多的边数多 1。 定理定理 8.8：在图：在图G中中,M是最大匹配当且仅当是最大匹配当且仅当G中中不包含关于不包含关于 M的增广路。的增广路。 证明：证明：用反证法。假设用反证法。假设G中存在关于中存在关于 M的增