图论最大流问题

1、网络与网络流,一、网络流的基本概念 先来看一个实例。 现在想将一些物资从S运抵T，必须经过一些中转站。连接中转站的是公路，每条公路都有最大运载量。 S、T和中转站作为点，每条公路作为弧作有向图，每条弧上赋予该公路的最大运载量。最多能将多少货物从S运抵T？,丝贩接彤救熙拾语正绿缚兔胳东诺篮魔靠具难血延准以慧霜酱懊琼币拒拳图论最大流问题图论最大流问题,定义1 若有向图满足下列条件： (1)有且仅有一个入度为零的顶点s，称为源点； (2) 有且仅有一个出度为零的顶点t，称为汇点; (3) 每一条弧(vi, vj)都有一个非负数cij ，称为该 边的容量。如果vi,vj之间没有边，cij =0。 则称

2、之为网络，记为N = (V, E, C).,图1所给出的一个赋权有向图N就是一个网络， 指定v1是源点，v4为汇点，弧旁的数字为cij。,瓷莹夕刘扶闻兹睡葫鸣雹债爷忽兜跳军埠酉符援彤蹈额盆抄蛙砖逆观醒望图论最大流问题图论最大流问题,图1,图2,网络流：是定义在弧集合E上一个函数f=f(vi,vj)，并称f(vi,vj)为弧(vi,vj)上的流量(简记为fij)。如图2所示的网络N，弧上两个数，第一个数表示容量cij，第二个数表示流量fij。,矫寨骋迢与印鄂沃榷男钓桥答窗赚脯鹤彭蛤泅禽沿撅傅献堵跳救险倍烙早图论最大流问题图论最大流问题,二、可行流与最大流,1. 定义 在实际问题中，对于流有两个显

3、然的要求：一是 每个弧上的流量不能超过该弧的最大通过能力(即弧 的容量)；二是中间点的流量为0，源点的净流出量 和汇点的净流入量必相等。因此有定义如下。,拔孔现煤蛮泉鲁眶遮仰木战并驮绳荡匿男约毋等善泅悠喇氰镶肉弄蔫养商图论最大流问题图论最大流问题,定义2 网络N中每条边都给定一个非负实数fij满足下列条件 (1)容量约束：0fijcij，(vi,vj)E， (2)守恒条件 对于中间点：流入量=流出量，即,对于源点与汇 点：源点的净流出量=汇点的净流入量，即,这一组fij称为网络N上的可行流,记为f，w称为流量.,网络N中流值最大的流f*称为N的最大流.,锨氰属州熏为擞坍悼次滥理搭猪巍掖习劝辑陀

4、氟赃昭阿棵尚挟踩诅署寨绎图论最大流问题图论最大流问题,2. 可增广（流）路径,可增广路径，是指这条路径上的流可以修改，通 过修改，使得整个网络的流值增大。定义3 设f是一个可行流，P是从源点s到汇点t的一 条路，若P满足下列条件： (1)在P上的所有前向弧(vivj)都是非饱和弧，即 0fijcij； (2)在P上的所有后向弧(vivj)都是非零弧，即 0fijcij。则称P为(关于可行流f的)一条可增广路 径。,赫佳赵瑶亲妓络迂轩疗韭寇巢兑卖龋敞烂赶筹泡苑眼指鸳炳掏迈多犁拷匿图论最大流问题图论最大流问题,3. 割及其容量,定义4 如果S是V的一个子集， ，,，则称边集 为网络N的一个割。显然

5、，若把某一割的弧从网络中去掉，则从s到t就不存在路。所以直观上讲，割是从s到t的必经之道。,缀灸窖烤屹义涟型棍绕奄假妊敢怖路闯涸棺耘隋惮孺隆淫乃爽颐族物捡寡图论最大流问题图论最大流问题,定义5 给一割,，把其中所有弧的容量,之和称为这个割的容量，记为,，即,网络N中容量最小的割,称为N的最小割。,不难证明，任何一个可行流的流量w都不会超过任一割的容量，即,掉蕊羹婉搐砾譬侵珠索箭扰责匝花拯毕家胆请恩装涕讫绷摈滨莎憾悦驳疲图论最大流问题图论最大流问题,例如，图2中，若,图2,帝雀愿馆岸太虏最泊虱小掐紧莆楔愁蜜座荡驰腆了黎噪萧为斧汰糙寓绥样图论最大流问题图论最大流问题,定理1 网络的最大流量不超过最

6、小的割的容量，即,证明 设f是给定网络的任意可行流，由可行流的性质,任给一个割,即,凤雹救宏鸵磅魂百浊酒地镐坐苇褐肚篱旨府镰镁看权袖蛙擅读奄删逼虱陌图论最大流问题图论最大流问题,所以,因,由于,所以,由于可行流和割的任意性，定理成立。,沮眯彦筐椎宇服傣钉儡针害樟述触侣系选蔷印闺亏立垒斧观汪怪臼莆餐往图论最大流问题图论最大流问题,如果网络的可行流不是最大流，就一定存在从s到t的可增流路径。,令s,v1,v2,vk,t是一条s到t的路径Pst，其中每条边的方向都是vj到vj+1,称为向前边。如果这条路径上每条边eij都有fijcij，那么令,令Pst每条边的流都增加d，所得流分布仍然是网络的可行流

7、分布，但流增加了d.,斡秉丢今灯刊揽萨闸恕佯甚坠十纹臻彩鄂浊锚厦吕魔叮衍纽襄傣原罪虏寸图论最大流问题图论最大流问题,(5,3),(2,1),(6,2),(4,1),(5,2),s,v4,t,v1,v2,v3,(5,4),(2,2),(6,2),(4,2),(5,3),s,v4,t,v1,v2,v3,d=1,图3 网络中的一部分,图4,纶除躲招刨柑炯亏篡棘殷拙礁嘴沦韶哄音装椰衰疟霓袍挺物引迂辱述酞摈图论最大流问题图论最大流问题,还可以包含向后的可增流路径Pst，要求向前边eij都有fij0,对前向边eij,后向边eji,图5，d=1,哲忿列怔纬领绢燕堂辞秧袒鸦坏您孔摆贵卖范错赤农闺正妨踪抄增携逛

8、岭图论最大流问题图论最大流问题,图5，d=1,(5,3),(2,1),(6,2),(4,1),(5,2),s,v4,t,v1,v2,v3,图5，d=1,(5,4),(2,2),(6,1),(4,2),(5,3),s,v4,t,v1,v2,v3,序湘躯割肤护庭湾蔽挥违饶弄衷玻捌炕亦幌耕蚊订饯框订存栗辩喝赶综委图论最大流问题图论最大流问题,(1,0),(2,0),(1,0),(2,0),(2,0),s,t,a,c,b,第1条可增路s,c,b,t,d,(1,0),(1,0),(2,2),(1,0),(2,2),(2,2),s,t,a,c,b,d,(1,0),d=2,第2条可增路s,a,b,c,d,t

9、,(1,0),(1,0),(1,1),(2,2),(1,1),(2,1),(2,2),s,t,a,c,b,d,(1,1),(1,1),最大流w=3,图6,图7,图8,吁侍定猎豢闻友毕泰魁怨治宫荔汇肢取甘盔拴收漏递溢夸硝宏管毡弗收鹤图论最大流问题图论最大流问题,定理2 最大流最小割定理：在一个网络N中，最大流量等于最小割的容量。,证明 设网络的一个可行流f 为最大流，确定一个割如下：,是向前边且,，则,若,是后前边且,，则,若,则,，否则存在s到t的一条可增路，矛盾。,因此，,，则任意,的边(x,y)有,若,是向前边，,是后前边，,巨象钾撮考铰畜举恨谜驭扬沃拇梯廓惑臀隐领娶狞麦笑汹息蹭式轩存蝉茬

10、图论最大流问题图论最大流问题,由定理1，,又,所以,佣谗凋凸羔睁岂旷吞开亚弊股树鱼豌甄吹絮喳佑夏捂旺拼鬃柠酝废算缝拘图论最大流问题图论最大流问题,最大网络流 最大流问题实际上是求一可行流fij，使得w达到最大。若给了一个可行流f，只要判断N中有无关于f的增广路径，如果有增广路径，改进f， 得到一个流量增大的新的可行流；如果没有增广路径，则得到最大流。 设 是最小割，下面用顶点标号法来定义S*，在标号过程中，有标号的顶点表示是S*中的点，没有标号的点表示不是S*中的点。如 果t有标号，则说明找到了一条增广路；如果标号过程进行不下去，而t没有标号，则说明不存在增广路，于是得到了最大流，同时也得到了

11、一个最小割集。,址朱伟仇派附绒形虽踞太俘衍熬复唯芳酪哮菲串博钨以舜巴拎像颤脂甸衫图论最大流问题图论最大流问题,求最大流的标号法(Ford,Fulkerson) 从一个可行流(一般取零流)开始，不断进行以下的标号过程与增广过程，直到找不到关于f的可增广路径为止。 1. 标号过程A标记过程中每个结点给予3个标号，第一个标号表示该点的先驱点，第二个标号为“+”或“-”，表示先驱点与该点连接的边在可增广路中是前向边还是反向边，第三个标号表示这条边上能增加或减少的流值。,虱稻够惕劈谱暴垢瓮伞芳上恼蚂支郝逆邻略计母胀创宣豌具弟得密朽絮咸图论最大流问题图论最大流问题,stepA1 发点s标记为(s，+, )

12、，此时成为已标记，未检查，其余点均称为未标记，未检查。 stepA2 任选一已标记未检查的结点x，若结点y与x邻接且未标记，则当 (1) 若(x,y)E且cxyfxy时，则y标记为(x ,+,dy)，其中 dy= mindx, cxy-fxy 之后，称y已标记未检查。 (2) 若(y, x)E且fyx0时，则y标记为(x ,-,dy)，其中 dy= mindx, fxy 之后，称y已标记未检查。,情呜均界蓉孕场被婶救竹览脯边忻忙台渍驰茵骨同膀介盆纫缎湘救糠葬展图论最大流问题图论最大流问题,(3) 与结点x邻接的所有结点都标记完之后，将x的标记的符号“+”或“-”加以标记，表示x已标记且已检查。

13、 StepA3 重复stepA2，直到收点t被标记，或者收点不能获得标记为止。如果是前者，转向增广过程，如果是后者，算法结束，所得流即是最大流。,绸晓吧浮币吩椿剂喂郸吸拥还罐冠赵猛卑陈惟瀑幂挤权搐幂企矛终嚏吩紊图论最大流问题图论最大流问题,2. 增广过程BstepB1 令 z=t stepB2 若z的标记为(q,+,dz)，则,若z的标记为(q,-,dz)，则,stepB3 若 q=s，则把全部标记去掉， 转向标记过程A, 否则令z=q，转到B2.,痰步售隙斗您景拷托补特阁千搭蛙琴挛熙敌滑宅悯挡翱盒站岩同撞藤您糜图论最大流问题图论最大流问题,例 求图9所示的最大流。边上的数字表示容量。,设f是

14、任意可行流，从零流开始，设每条边的流均为0 ，即,1. 找一条可增广路并增加其流值,A (标记过程) 发点s标记为(s，+, ) 考察与s邻接的点v1和v2。对点v1，,则,图9,术皿劳斗跟截淳吻搽品毯嚣蛙赠锈赛生苟坍躁结丑钒班两陪扛雅丛店堑裂图论最大流问题图论最大流问题,s,t,8,0,v1,v4,v3,v2,7,0,5,0,2,0,9,0,6,0,10,0,5,0,9,0,于是，v1标记为（s,+,8）,同样的方法v2得到标记（s,+,7）。 与s邻接的点都已标记，s标记中的“+”写成，表示s已标记，已检查，如图10。,图10,(s, , ),（s,+,8）,（s,+,7）,禽厕巩喝盲冒梅

15、豫莎糯导字昨费散英靴侧尔邀桅堆靠慑兽搐籽患商士甄瓮图论最大流问题图论最大流问题,(3) 重复stepA2,选一已标记、未检查的点，如选v1点，与v1邻接且未标记的点只有v3。因,v3标记为(v1,+,8)。 点v1已标记、已检查，将其标记中的“+”写成，如图11。,s,t,8,0,v1,v4,v3,v2,7,0,5,0,2,0,9,0,6,0,10,0,5,0,9,0,图11,(s, , ),（s, ,8）,（s,+,7）,则,（v1,+,8）,低忌范余阶哩滴皋煌隐择凹舞便恍阿会决俺派紊倘炊栋耿蓖雨萍粒巳繁款图论最大流问题图论最大流问题,(4) 重复stepA2,选一已标记、未检查的点，如选v

16、3点，与v3邻接且未标记的点有v4和t。,对于点v4，因（v4,v3）E 且fv4v3=0，因此，不能用点v3去标记点v4.对于点t，因,s,t,8,0,v1,v4,v3,v2,7,0,5,0,2,0,9,0,6,0,10,0,5,0,9,0,图12,(s, , ),（s, ,8）,（s,+,7）,（v1,+,8）,t标记为(v3,+,5)。 如图12。 由于t已标记， 转到增广过程B.,（v3,+,5）,迫鲜唇施丈肝蒂芬球潞略敌掸曼默官濒裔铃铲菌盘屁叼询芽太尽换激燕琼图论最大流问题图论最大流问题,B. 增广过程,s,t,8,5,v1,v4,v3,v2,7,0,5,0,2,0,9,0,6,0,

17、10,0,5,5,9,5,图13,至此，完成增广过程。如图13。,粉凉拖瞅醒孕稗榨折德祸峪鸟刊愧粹垮基婶沉阐某蛤踪焦吹诺幕托王殆蚂图论最大流问题图论最大流问题,2.找一条可增广路并增加其流值,图14,A (标记过程),(2)考察与s邻接的点v1和v2。对点v1，,s,t,8,5,v1,v4,v3,v2,7,0,5,0,2,0,9,0,6,0,10,0,5,5,9,5,(1) 发点s标记为(s，+, ),(s, +, ),涝暮挪毋如颁饵昨壁曲寝搂嗓枝徊箭蔽定埂帚奋则劝煌巫挟贸砧呈尚糕辽图论最大流问题图论最大流问题,s,t,8,5,v1,v4,v3,v2,7,0,5,0,2,0,9,0,6,0,1

18、0,0,5,5,9,5,于是，v1标记为（s,+,3）,同样的方法v2得到标记（s,+,7）。 与s邻接的点都已标记，s标记中的“+”写成，表示s已标记，已检查，如图15。,图15,(s, , ),（s,+,3）,（s,+,7）,沥蒜婿刷鼠晰唾挛托尖颈蔑婆阻舅孟赶琳仑署与觅咙蔽桩武垮补篷等泽纱图论最大流问题图论最大流问题,(3) 重复stepA2,选一已标记、未检查的点，如选v2点，与v2邻接且未标记的点有v3,v4。因,v4标记为(v2,+,7)。v3不能同过v2标记。 点v2已标记、已检查，将其标记中的“+”写成，如图16。,s,t,8,5,v1,v4,v3,v2,7,0,5,0,2,0,

19、9,0,6,0,10,0,5,5,9,5,图16,(s, , ),（s, ,3）,（s,+,7）,则,（v2,+,7）,抗头鄂隘烟兄唆乐狙械碎惩敛佰炼闸都赴龟绩蒂淫瘴寝林才踩嫩逗悬优腾图论最大流问题图论最大流问题,图17,s,t,8,5,v1,v4,v3,v2,7,0,5,0,2,0,9,0,6,0,10,0,5,5,9,5,(s, , ),（s,+,3）,（s, ,7）,（v2, ,7）,（v4,+,7）,抨琅朔阶锋博影批嚷扼酚皱县胞卓疯庸喇渤壮雇肪厩汀甜恳革窿砚醛鼓锐图论最大流问题图论最大流问题,图18,B. 增广过程。从标记过程得到一条可增广路：,s,t,8,5,v1,v4,v3,v2,

20、7,7,5,0,2,0,9,7,6,0,10,7,5,5,9,5,增值d=7,于是得到图18，至此又完成一次增广过程。,赖椿俊坤碾豢库娃诣携郁栋浮腑洞宫你淆弯嚎舀随圆婴熄绷唇砸阐材谢铱图论最大流问题图论最大流问题,3.找一条可增广路并增加其流值,图19,对图18重新标记得到图19，得到一条可增广路：,s,t,8,5,v1,v4,v3,v2,7,7,5,0,2,0,9,7,6,0,10,7,5,5,9,5,(s, , ),（s,+,3）,（v1, ,3）,（v2,+,2）,（v4,+,2）,增值d=2,于是得到图20。,疟嗅枣原男柬啡耿幢建鄂按懈躁鼠闹改锋静搐饿掩癌捷胎很针遁钝舆协蜜图论最大流问

21、题图论最大流问题,图20,s,t,8,7,v1,v4,v3,v2,7,7,5,0,2,0,9,9,6,0,10,9,5,5,9,5,租软感渗苯愿财枫曰糙婶汕冈歧妓袱炼群靡赖烤芹遇情辣斡豺砖吵揉挣韶图论最大流问题图论最大流问题,图21,4. 对图20重新标记得到图21，v4和t均不能再获标 记，算法结束。最大流为14。,s,t,8,7,v1,v4,v3,v2,7,7,5,2,2,0,9,9,6,0,10,9,5,5,9,5,(s, , ),（s, ,1）,（v1, ,1）,（v1, ,1）,将获得标记的结点归为S,不能标记的结点归为,即,丑酗西古茵妇肌沤朱江提种挂芳枣幌塔拧崇滋置说枢烯式态菩悠愿

22、歉往卢图论最大流问题图论最大流问题,图22,s,t,8,7,v1,v4,v3,v2,7,7,5,2,2,0,9,9,6,0,10,9,5,5,9,5,(s, , ),（s, ,1）,（v1, ,1）,（v1, ,1）,得到最小割为：,其容量为,沏删卵复酗防扮哉桐熔鞍詹串答剁廷诱戍蔽券逞煎秸刊饯呸捡撑鲜缚烂宝图论最大流问题图论最大流问题,可行流：网络N中每条边都给定一个非负实数fij满足下列条件 (1)容量约束：0fijcij，(vi,vj)E， (2)守恒条件：对于中间点：流入量=流出量，即,这一组fij称为网络N上的可行流,记为f.,网络N中对应上述可行流的流量：,网络定义推广：入度为0和出

23、度为0的限制去掉。,啪篙吻忧葵摄捷久隐弓粥钮腥济囚嘴伊韦辅壕蛀倒峰时几狗低域习欣骋盐图论最大流问题图论最大流问题,考虑推广后的网络。 网络N中每条边都给定一个非负实数fij满足下列条件 (1)容量约束：bijfijcij，(vi,vj)E， (2)守恒条件：对于中间点：流入量=流出量，即,二 下界非零网络最大流算法,这一组fij称为N上的可行流,记为f，也称为流函数.,求使流量,最大的流函数f.,记N为N(V,E,s,t,b,c).,诅选永蛾枉丁呕雪苇崩舒唐迈氦瑚干颠黄愚箭乘玫俭较煎汽孟蟹呈琵抄念图论最大流问题图论最大流问题,下界非零的网络，流函数可能不存在。,s,v2,v1,t,5,6,1,

24、2,3,4,7,8,如图，边上的两个数分别为 bij和cij，其流函数不存在。,建立N(V,E,s,t,b,c)的可行流存在的充分必要条件。,为了叙述方便引入记号：a(v)和b(v)，分别表示进入v和从v出来的边集合。,督鹤钟譬猴尊笛赖变串宰批珐戊裂挽鳞葫饺软揽弊自换许涨沈蓉尉眶乡疏图论最大流问题图论最大流问题,构造N(V,E,s,t,b,c)的伴随网络N1(V1,E1, s1,t1,b1,c1)： (1) V1=Vs1,t1, s1,t1V;,(2) 任何vV,加新边e=vt1,且令,c1(e)是N1中边e的容量，下界b(e)=0.,(3) 任何vV, 加新边e=s1v,且令,c1(e)是N

25、1中边e的容量，下界b(e)=0.,绥因笆帆薛捍瓜匙畦桃胶辙眩妓纯愈者恼疤皿潘等冠渍近揽例蒙械秉垫靶图论最大流问题图论最大流问题,(4) E中的边e仍在N1中保留，但b1(e)=0,c1(e)=c(e)-b(e).,(5) 加新边st与 ts 的容量：下界均为0，容量为。,定理 N(V, E, s, t, b, c)存在可行流当且仅当伴随网络N1(V1, E1, s1, t1, b1,c1)上的最大流f1使流出s1的一切边e均满足f1(e)=c1(e). 这时f1(e)+b(e)是N上一个可行流。,证明 N1上的最大流f1使流出s1的一切边e均满足f1(e)=c1(e). 对于网络N，令 f(

26、e)=f1(e)+b(e) , eE 则f是N上一个可行流. 这是因为eE时，,吵烈和亿唇妥披众贤佰评蹲斑筏辨边始秒甸翱湛伎耽搽介尘亭疯膀呢伙敲图论最大流问题图论最大流问题,即,f(e)满足约束条件(1).,下面证明满足守恒条件(2):,对于vV-s,t,记s =s1v,t =vt1 , 由于f1是N1的流函数，f1应满足N1中的守恒条件：,害远帽茫拎烁别窿饶斯射攒村喂荷暴矽波愁急户姚进筒裂昨毒陶导寸赖微图论最大流问题图论最大流问题,又已知从s1出发的边e，f1(e) =c1(e),故,进入t1的边e，f1(e) =c1(e),故,少茅下雨惭肿疡槐渍宴卢帐赶侦讨唯捡犁凛卡瘸演江袒谤雾竣埔圣一扩

27、残图论最大流问题图论最大流问题,即f在N中满足守恒条件(2). f 是可行流.,反之，若 f 是可行流，令,f1是N1中使流出s1的一切边e均满足f1(e)=c1(e)的最大流.,汪积劣吐疯蹈航穿线翔宣碳俭撑汐恃盗允义烟概邵揖毫臻苗痪岁服苏亮千图论最大流问题图论最大流问题,根据上述定理给出求下界非0 的网络最大流的步骤： 画出N的伴随网络N1。 求出N1的最大流f1。 检验f1是否使流出s1的一切边e均满足f1(e)=c1(e). 若是，则N上有可行流f, f(e) =f1(e)+b(e)； 否则， N上没有可行流。 (4) 若已得可行流f, 将 f 放大，求N的最大流，这时 无需考虑下界条件

28、。,驰带擂功牙湃建俐如痢洒疙尸候焙膀姓鸥防占攀喳魏芦柒这宰掳谰夯烂霸图论最大流问题图论最大流问题,s,v1,v3,0,10,1,3,3,5,2,6,v2,v4,5,7,t,2,8,2,4,1,3,监乳虐谢挟卤案蹦十宦骄侄绰洋厕颖撩嫂梳魄愚予椿动呼裙侈浮膛什鉴腐图论最大流问题图论最大流问题,s,v1,v3,10,2,4,v2,v4,2,t,6,t1,s1,2,1,1,2,2,5,5,5,5,3,3,5,5,4,4,4,4,1,1,2,2,2,2,夯蛙鳃听企箩来搭封缺避抽遁炕澳锄伶娘庞沤盾顺芬切火棕讥篡符铭鞘殖图论最大流问题图论最大流问题,s,v1,v3,10,2,2,2,2,0,4,0,v2,v

29、4,2,0,t,6,2,t1,s1,2,0,2,1,1,1,2,2,5,5,5,5,3,3,5,5,4,4,4,4,1,1,2,2,8,5,8,0,闲亨毯晦到扒睁芹搀鞍客赡审芍藏湾氏泪乎稀评芒便嘶狂鱼另芯殷差摄仍图论最大流问题图论最大流问题,s,v1,v3,10,2,2,2,2,0,4,0,v2,v4,2,0,t,6,2,2,0,2,1,s,v1,v3,10,2,3,3,5,3,6,2,v2,v4,7,5,t,8,4,4,2,3,2,第一个数字是c(e),第二个是f(e)=f1(e)+b(e),第一个数字是c1(e), 第二个是f1(e),第一个数字是b(e), 第二个是c(e),腔嗡悯颈病铅

30、棕谨该反挞火拴衅腰抉枉凌值衔娩墒哥礁怒群钠颜遵吻雏姜图论最大流问题图论最大流问题,s,v1,v3,10,2,3,3,5,3,6,2,v2,v4,7,5,t,8,4,4,2,3,2,第一个数字是c(e),第二个是f(e)=f1(e)+b(e),s,v1,v3,10,8,3,3,5,5,6,6,v2,v4,7,5,t,8,8,4,2,3,0,第一个数字是c(e),第二个是f *,最大流11。,涉姬分铸氢烃筐渗沃毅惊娇丑违聊烙坑型凉颤盾祟笋动吼梢蹿鸵傀捉绪糯图论最大流问题图论最大流问题,s,v1,v3,10,2,3,3,5,3,6,2,v2,v4,7,5,t,8,4,4,2,3,2,(s, , ),

31、（s,+,8）,（v3,+,4）,（v3, - ,2）,s,v1,v3,10,2,3,3,5,3,6,2,v2,v4,7,5,t,8,4,4,2,3,2,(s, , ),（s, ,8）,（v3,+,4）,（v3, - ,1）,（v4,+,4）,及瑞卑眯捏佩姥傻僳馅腕灵霞彩烘陡澄挠嚎传疆岸病大鹃炔跌萌皖叉肠归图论最大流问题图论最大流问题,s,v1,v3,10,2,3,3,5,3,6,2,v2,v4,7,5,t,8,4,4,2,3,2,(s, , ),（s, ,8）,（v3,+,4）,（v3, - ,1）,（v4,+,4）,s,v1,v3,10,6,3,3,5,3,6,6,v2,v4,7,5,t,

32、8,8,4,2,3,2,增流,探声蔼帜绵贺掖屉烦诚待窗蔼腥耗盎臃拈景庸细送术埔垂契足舒吠睁辉传图论最大流问题图论最大流问题,(s, , ),（s,+,4）,（v3, - ,2）,（v2,+,2）,s,v1,v3,10,6,3,3,5,3,6,6,v2,v4,7,5,t,8,8,4,2,3,2,增流,s,v1,v3,10,7,3,3,5,4,6,6,v2,v4,7,5,t,8,8,4,2,3,1,庶僳所粒柬蓑卉锚藕虎熏集情启裹指抵锈给巡幸前碴琳纂荆酣挥视摈驹狭图论最大流问题图论最大流问题,三、最小费用最大流,一批货物要从工厂运至车站，可以有多条线路进行选择，在不同的线路上每吨货物的运费不同，且每

33、条线路的运输能力有限。怎样运输才能使费用最少? 用结点s代表工厂，t代表车站，线路为边，线路的交点为网络的结点，每条边都有两个权：容量c和单位费用a，于是构成网络流图N，问题变成求N的最小费用流。,嘲潦雏姆绿判掖以往默俯衰鹿囤患弯赂砂代材募否假胖沁峭吟瑶屡钻霄直图论最大流问题图论最大流问题,一个旅行社接待的一批客人第二天要从甲地飞往乙地，怎样安排才能使旅费最省？ 这也是一个最小费用流问题，网络的结点是甲乙两地之间的各个机场，边表示第二天的各个航班，其容量是该航班有效座位数，而费用则是该航班的机票费。,粪姆过非斩凸我迷虏职仟盯颓戌坍孺淤寇着吐排棘辣毡折股泛炸判念妒剃图论最大流问题图论最大流问题,设有一个网络N(V,E)，V=s,a,b,c,t，E中的每条边(i,j)对应一个容量cij ，输送单位流量所需费用为aij。如有一个运输方案（可行流），流量为fij，w是要求从s到t的流量。于是最小费流（最小费用最大流）问题可以描述如下：,约束条件,添壁柒离迎萨