《1166编号网络流算法课件(清华)》由会员分享，可在线阅读，更多相关《1166编号网络流算法课件(清华)（65页珍藏版）》请在金锄头文库上搜索。
1、1,网 络 优 化,Network Optimization ,清华大学数学科学系 谢金星 办公室：理科楼2206# （电话：62787812） Email: ,清华大学课号：70420133,第6章 最大流问题 (Maximum Flow Problem) 第1讲,2,许多实际问题都可以转化为最大流问题,S,T,最大流问题的例子,公路交通网络：车流流量,3,定义6.1 在有向图G=(V，A)上定义如下的权函数： （1）L：AR为弧上的权函数，弧(i,j) 对应的权 L (i,j) 记为lij，称为弧 (i,j)的容量下界（lower bound）; （2）U：A R为弧上的权函数，弧(i,j
2、)对应的权U(i,j)记为uij ，称为弧(i,j) 的容量上界，或直接称为容量（capacity）; （3）D：V R为顶点上的权函数，节点i对应的权D(i)记为di ，称为顶点i的供需量（supply/demand）; 此时网络可称为流网络(Flow Network,一般仍简称为网络),记为 N=(V,A,L,U,D).,6.1.1网络中的流,di 0:供应点(supply node)或源(source)、起始点或发货点 di 0:需求点(demand node)或汇(sink) 、终止点或吸收点 di 0:转运点(transshipment node)或平衡点、中间点,4,定义6.2 对
3、于流网络N=（V，A，L，U，D），其上的一个流(flow) x是指从N的弧集A到实数集合R的一个函数x：A R, 即对每条弧(i,j) 赋予一个实数 (称为弧(i,j)上的流). 如果流x满足,存在可行流的必要条件,则称x为可行流(feasible flow). 至少存在一个可行流的流网络称为可行网络(feasible network). 如果流x只满足容量约束(6.2), 但不一定满足流量守恒条件(6.1), 则称x为伪流(pseudoflow)， 或容量可行流.,流量守恒/平衡条件,容量约束/可行条件,网络中的流,一般可以把L 0的流网络转化为L=0的流网络进行研究(思考？) 除非特别说
4、明, 以后我们总是假设L=0,网络简记为N=(V,A,U,D).,5,运输网络的特点是只有源或汇，没有中间转运点. 显然，此问题有解的一个必要条件是,网络中的流,例 - 运输网络和运输计划,有一批货物从货源地运往目的地，假设货源集合为S，目的地集合为T. 货源i可提供的货物数量为ai个单位，目的地j对货物的需求量为bj个单位. 以（S，T）为节点集作完全二部图，以 ai ，- bj 为节点上的供需量。通过每条弧的运输量没有限制（非负即可）。 一个运输计划就相当于该网络中的一个流。,6,网络中的流,例6.1 有向网络中，令所有弧上的容量下界为0，容量（上界）为1，并令节点s的供需量为1，节点t的
5、供需量为-1。 从s到t的一条有向路正好对应于网络中的一个可行流x （当xij =1时，表示弧(i，j)位于s-t路上， 当xij=0时，表示弧(i，j)不在s-t路上）.,思考：网络中的任意一个可行流是否一定对应于一条有向路？,7,网络中的流,定义6.3 在流网络N=(V,A,U,D)中，对于流x, 如果某条弧(i,j)上的流量等于其容量（），则称该弧为饱和弧（saturated arc）；如果某条弧（i，j）上的流量为0()，则称该弧为空弧（void arc）.,如果所有弧均为空弧，即 则称x为零流，否则为非零流.,8,网络中的流,定义6.4对于给定流网络N=(V,A,U,D)中的流 x：
6、A R ，如果N中存在一条有向路P，使得 ， 则称x为路流（Path flow），v称为该路流的流值（流量）. v=0时，称该路流为零路流，否则称为非零路流.,如果N中存在一个有向圈W，使得 ， 则称x为圈流（Cycle flow），v 称为该圈流的流值（流量）. v=0时，称该圈流为零圈流，否则称为非零圈流.,5,9,定理6.1 在网络N=(V,A,U,D)中，任何一个可行流可以表示为若干个路流和若干个圈流之和，且这些路流和圈流满足下列性质： （1）非零路流对应的有向路从一个源点指向一个汇点； （2）至多有m+n个路流和圈流为非零流，且其中至多有m个圈流为非零流.,流的分解定理 （Flow
7、Decomposition Theorem）,证明 (构造性) 记可行流为x，设i0是网络中的一个源点，则存在弧 (i0, i1) 使得 0.,在一个无源无汇的流网络中，一个可行流称为可行循环流。,推论 一个可行循环流一定可以表示为至多m个非零圈流之和.,如果i1是一个汇点, 则找到了从源点指向汇点的一条有向路. 否则从i1出发重复上述过程,直到找到一个汇点或再次遇到前面经过的某个顶点时为止, 即直到下列两种情况之一出现为止:,10,当找到一个路流时, 重新定义使得某个节点的供需量从非零成为零, 或者使得某条弧的流量从非零成为零. 当找到一个圈流时, 重新定义使得某条弧的流量从非零成为零.,对
8、新网络,重复上述过程,直到所有顶点变成为转运点(平衡点).,然后,找到一个至少有一条出弧上的流量为正的顶点, 继续重复上述过程, 这时只有情形(b)会出现, 即一定获得一个非零圈流. 重复上述过程, 直到重新定义的流x成为零流为止.,(b)找到一个有向圈W. 此时,定义,(a)找到一条从一个源点i0指向一个汇点ik的有向路P. 定义,上述过程找到路流和圈流的次数之和不会多于m+n次，且其中找到圈流的次数不会多于m次.,11,单源单汇的网络，可行流x的流量（或流值）为v=v（x）= ds = - dt 如果我们并不给定ds 和dt, 则网络一般记为N=（s, t,V,A,U），容量可行且转运点流
9、量守恒的流称为s-t可行流，有时为了方便也称为可行流. 最大流问题(Maximum Flow Problem)就是在N=（s, t,V,A,U） 中找到流值最大的s-t可行流 (即最大流).,6.1.2 最大流问题的数学描述,定理6.2 (整流定理) 最大流问题所对应的约束矩阵是全么模矩阵. 若所有弧容量均为正整数,则问题存在最优整数解.,12,引理6.1 任意一个s-t可行流流值不超过任意一个s-t割容量.,6.1.3 增广路定理,定义6.5 设S，T是网络N=(s,t,V,A,U)中给定的一个割，且sS，t T ，则称割S，T为s-t割. s-t割S，T中的弧(i，j)(iS，jT)称为割
10、的前向弧，弧(i, j)(jS，iT)称为割的反向弧. s-t割S，T的容量定义为前向弧的容量之和，记为 一个网络中容量最小的s-t割称为最小割.,13,增广路,引理6.2 如果对于一个可行流存在增广路，则该可行流不是最大流.,定义6.6 设x是流网络N=(s,t,V,A,U)中给定的可行流，P是一条s-t路，则P中满足下列两个条件之一的弧（i，j）称为增广弧(augmenting arc)： （1）弧（i，j）是P的前向弧且为不饱和弧；或 （2）弧（i，j）是P的反向弧且为非空弧. 如果P中的弧都是增广弧，则称P为关于流x的增广路, 简称增广路(augmenting path).,这一过程称
11、为x 关于P的增广 (augmentation),14,证明 必要性可以由前面的引理直接得到. 下面证明充分性.,定理6.3 (增广路定理) 一个可行流为最大流的充要条件是不存在增广路.,增广路定理,假设流网络N=(s,t,V,A,U)中不存在关于可行流 x 的增广路,记网络中从 s 出发沿增广弧可以到达的节点集合为S, 令 T=VS, 则sS，tT，即 S, T 为 s-t 割. 并且, 对于A中的任意弧(i,j), 如果它是该s-t割的前向弧, 则 ; 如果它是该s-t割的后向弧, 则 =0.,引理6.1证明中的中间结果,因此,S,T为最小割,x为最大流.,定理6.4 (最大流最小割定理)
12、 最大流的流值等于最小割的容量.,15,6.2 增广路算法,6.2.1 Ford-Fulkerson标号算法 （）,基本思想：从任何一个可行流开始,沿增广路对流进行增广,直到网络中不存在增广路为止. 问题的关键在于如何有效地找到增广路,并保证算法在有限次增广后一定终止.,基本思想：标号过程来寻找网络中的增广路 pred（j）：节点j 在可能的增广路中的前一个节点; maxf（j）: 沿该可能的增广路到该节点为止可以增广的最大流量. LIST : 记录可能的增广路上的节点,16,STEP5. 转STEP3.,STEP3. 如果LIST 且maxf（t）=0, 继续下一步; 否则: (3a) 如果
13、 t 已经有标号(即maxf(t)0)，则找到了一条增广路，沿该增广路对流 x 进行增广(增广的流量为maxf（t）,增广路可以根据pred回溯方便地得到), 转STEP1. (3b) 如果 t 没有标号(即LIST= 且maxf(t)=0), 转STEP1.,STEP4. 从LIST中移走一个节点i；寻找从节点i出发的所有可能的增广弧： (4a) 对非饱和前向弧（i，j），若节点 j 没有标号(即pred（j）=0)，则对j进行标号，即令maxf(j) = minmaxf(i), uij- xij， pred(j)=i, 并将j加入LIST中. (4b) 对非空反向弧（j，i），若节点 j
14、没有标号(即pred(j) =0)，则对j进行标号，令maxf(j) = minmaxf(i), xji， pred(j) =i, 并将j加入LIST中.,STEP1.若maxf（t） 0, 继续下一步; 否则结束.,STEP0. 置初始可行流 x（如零流）; 对节点 t 标号, 即令maxf（t）=任意正值（如1）.,STEP2. 取消所有节点 jV 的标号，即令maxf（j）=0, pred（j）=0；令LIST=s; 对节点 s 标号，即令maxf（s）=充分大的正值.,17,最大流流值为4,Ford-Fulkerson标号算法,例： （uij，xij）,18,最大流流值为2*106,F
15、ord-Fulkerson标号算法,例： （uij，xij）,19,该算法是否一定在有限步内终止呢？ 如果弧上的容量可以是无理数，可以举出例子说明标号算法不一定在有限步内终止；并且，这一增广路算法的极限过程得到的流的流值即使收敛，也不一定收敛到最大流,Ford-Fulkerson标号算法,标号算法终止时，网络中一定不再含有增广路.,如果所有弧上的容量都是正整数，根据整流定理，最大流v也是整数. 实际上，由于割s，Vs中前向弧的条数最多为n条，因此最大流v的上界为nU（U表示网络中弧上的最大容量）. 由于每次增广至少使得流值增加1个单位，因此增广的次数不会超过v次，算法一定在有限步内终止. 此外
16、，由于每次增广最多需要对所有弧检查一遍，因此算法的复杂度为O（mv），或表示为O（mnU）. 伪多项式时间算法，而不是多项式时间算法.,20,定义6.7 对网络N=(s,t,V,A,U)中给定的s-t可行流x，网络N关于流x的残量网络N(x) = (s, t, V, A(x), U(x) , 其中A(x), U(x)定义如下： （residual network，又常称为增量网络或辅助网络 ）,6.2.2 残量网络,讨论算法复杂度时，假定:弧（i，j）A时，弧（j，i） A；并假定在残量网络中A（x）=A，也就是说弧的条数和弧集合都不变. 这只要允许容量为0的弧仍然保留在网络中就可以了.,命题：若v*是原网络的最大流，则残量网络N(x) 中最大流为 v*-v（x）.,其中称, uij(x)为弧(i,j)上的残留容量(residual capacity).,21,残量网络,例： （uij，xij）,N(x)中的s-t有向路P, 对应于原网络N中的一条增广路 ； 直接称残量网络中的s-t有向路为增广路. 沿P可以增广
