第十章网络的流 网络模型的很多问题可以归结为网络流问题。第九章中介绍的最短路问题,本质上也 是网络流问题,属于网络流问题的一类特殊问题。而多数网络流向题又是线性规划的特殊 类型.都可以建立对应的线性规划或整数规划摸型。那么为什么要用网络流的方法代替线 性规划,不用线性规划的一般求解方法,而要另外建立一些算法呢?由于实际问题中抽象 出来的网络流模型是一类具有特殊结构的问题,利用其特性常常可以研究、寻求一些较单 纯形法更为有效的方法去求解,又由于网络模型的直观性常常可以通过顶点一边的关系 代数学模型来措述一个实际问题,更易于接受.网络流题是图论的重要方面,在广泛 的领域里具有重要的应用。 这一章我们以运输网络为例,介绍网络的流及其它有关问题。主要内容是:流和割的 概念。最大流最小制定理,确定最大流的标记法,最小费用流以及最小费用最大流的网络 模型。 S10.1基本概念和定理 一、流 设G=(W,E)为一有向图,顶点V表示一些城市(或中转站),边集E表示连接顶点 的道路。给每边e∈E(G)赋予一个非负整数c(e) c,),或简记为c4,通常称为容 量,它表示在一定时间内这条边货物的最大通过量则称G为一个网络,现在假定在网络 中有一点s有大批货物要通过网络运送到网络的另一点t.s点我们称为网络的源,通常 假定它没有射入边t点称为汇,假定它没有射出边.除了源和汇以外的点称为G的中间 顶点.这样的网络就是在物资运输问题中常用的数学榄型,常常称为运输网络。 在运输网络中边可以用来表示城市之间的公路或铁路,电信局之间的通讯线路等,边 的容量则可以表示输送的物资量,速率公路或铁路上通过的车辆数或信息量等等。 图10-1表示一个具有一个源s,一个汇t以及4个中间顶点,2,,”的运输网 络.边旁的数字为c· 图10-1 假如,我们把网络中的边视为交通网中的道路,每条道路都有一定输送货物的能力即 容量,问题就成为如何在该运输网络中寻找最佳运输方案 一个货物运输方案,可以用网络上的一个可行流来表示。 所谓网络上的流是指定义在边集合E上的一个函数f(e)=f(,),并称f(e)为 1
✂✁✂✄ ☎✂✆✂✝✂✞ ✟✡✠☞☛☞✌☞✍☞✎☞✏☞✑☞✒☞✓☞✔✖✕☞✗✖✘✙✟✚✠☞✛✖✑✖✒☞✜✣✢☞✤✖✥✙✦✚✧☞★✖✍✖✩☞✪✖✫☞✑✖✒, ✬☞✭☞✮☞✯ ✰✟✡✠☞✛☞✑☞✒, ✱☞✲ ✟✡✠☞✛☞✑☞✒☞✍☞✳☞✴☞✵☞✶✖✑☞✒✖✜✸✷✖✏✖✹✙✟✚✠☞✛✖✑✖✒☞✺✰☞✻✖✼✖✽☞✾✍☞✵✖✶ ✴☞✌, ✿✓☞✔☞❀☞❁☞❂☞❃☞✍✻☞✼☞✽☞✾✖❄✖❅✹✽☞✾☛✖✌☞✜✣❆✖❇☞✘✖❈☞❇✖❉✖❊✙✟✚✠☞✛✖✍✖❋☞●✖❍☞■✻ ✼✖✽✖✾, ❏ ❊✻✖✼✖✽✖✾✍✖✳✖❑✖▲✖▼✖❋◆●, ✷✖❉✖❖✖P✖❀✖❁✖✳✖◗✖❘✖●✖❙? ❚✚✲✖❯✖❱✑✖✒❲✦✚❳✖❨ ❩☞❬✍✙✟✡✠☞✛☞☛☞✌✰✳☞✴✖❭☞❪✖✵☞✶✖✗✖❫☞✍✖✑☞✒, ❴ ❊☞❵☞✵✼☞❛☞❛✓☞✔☞❜☞❝☞❞✣❡✖▲☞✳✖◗☞❢✖❣ ❤✖✐●✖❥✖✘✖❪✖❦✖✍✖❋✖●✖❧✖▲✖▼, ✺ ❚✚✲ ✟✚✠✖☛✖✌✖✍✖♠✖♥✼ , ❛✖❛✓✖✔✖♦✖♣✖q✖r – s ✍✖t✖✉ ❍✖■✖✹✖✈✖☛✖✌❬✖✇✖①✳✖②❯✖❱✑✖✒, ❥✖③✲✖④✖⑤✜✡✟✚✠✖✛✖✑✖✒✰✖⑥✖⑦✍✖⑧✖❉◆❋✖⑨, ⑩✖❶✖❷ ✍✖❸✖❹✖❺✖❭✖❪✖⑧✖❉✖✍✖❃✖❊✖✜ ❻✳✖✥✖❼✖❽✖✔✖❾✖❿❲✟✚✠✖✘✖➀, ✧✖★❲✟✚✠✖✍✖✛✖➁✖❵✖➂✖❪✖t✖✑✖✒✖✜➄➃◆❉❲➅✚➆✰ : ✛✖➇✖➈✖✍ ➉◆➊, ✩◆➋◆✛◆✩◆➌◆➈◆➍◆➎, ➏➍◆✩◆➋◆✛◆✍◆➐◆➑◆●, ✩◆➌◆➒◆❊◆✛◆✔◆➁◆✩◆➌◆➒◆❊◆✩◆➋◆✛◆✍➓✟➔✠ ☛✖✌✖✜ §10.1 →↔➣↔↕↔➙↔➛↔➜↔➝ ➞➠➟➢➡ ➤ G = (V, E) ✘✖✳✖❪❲➥⑥ , q✖r V ➦✖➧✳✖◗✖➨✖➩ (❄ ✦✚➫✖➭), s✖➯ E ➦✖➧✖➲✖④q✖r ✍✖➳✖✫✖✜➄➵✖➸s e ∈ E(G) ➺✖➻✳✖②✖➼✖➽❅✹ c(e) = c(vi , vj ), ❄✖➾➑✖✘ ci,j , ♦❛✖➚✘➶➪ ➹ , ➂➦✖➧✖⑩✳✖➍✖➘✖➴❲➅❻✖➷s✖➬✖➮✍✖✩✖➋✖♦✖♣✖➱, ✃➚ G ✘✖✳✖②❲✟✚✠✖✜❒❐⑩✖❮➍ ⑩ ✟✚✠ ✦✚❪✖✳✖r s ❪✖➋✖❰➬✖➮❉✖♦✖♣❲✟✚✠✖❾✖Ï✖Ð❲✟✚✠✖✍✖❖✖✳✖r t✜ s r✖❼✖❽➚✘❲✟✚✠✖✍ÒÑ, ♦❛ ❮ ➍✖➂✖Ó✖❪✖Ô✖Õs;t r➚✘×Ö, ❮ ➍✖➂✖Ó✖❪✖Ô❩ s ✜ÙØ✖Ú✖Û✖➇✖Ü✖✔✖P✖✍✖r➚✘ G ✍×Ý✖Þ ß✖à✜ ❻✖á✍❲✟✚✠✖â✰ ⑩✖➮✖ã❾✖❿✖✑✖✒❲✦❛❊✖✍✖✹✖✈✖☛✖✌, ❛✖❛✖➚✘×ä✖å✖æ✖ç✖✜ ⑩❾✖❿❲✟✚✠❲✦s ✓✖✔✖❊❬➦✖➧➨✖➩✖è✖➴✖✍✖é✖✫❄✖ê✫ , ë✚ì✖íè✖➴✖✍✖♦✖î✻✫✖ï, s ✍✖➆✖➱✃✓✖✔ ➦✖➧❿✖Ï✖✍➮✖ã➱ , ð✖ñ, é✖✫❄✖ê✫ ✮♦✖♣✖✍✖ò✖ó✖✹❄ì✖ô➱✖ï✖ï✖✜ ⑥ 10–1 ➦◆➧✳◆②◆❭◆❪◆✳◆②◆Û s, ✳◆②◆Ü t ✔◆➁ 4 ②➓✦➔➴◆q◆r v1, v2, v3, v4 ✍◆❾◆❿➓✟ ✠✖✜ s✖õ✍✖✹✖ö✖✘ ci,j ✜ ⑥ 10–1 ❮✖÷, ❼✖❽✖ø❲✟✚✠❲✦✚✍s✖ù✘✖ú✖♦❲✟✖✦✚✍✖➳✖✫, ➸➷➳✖✫✿ ❪✖✳✖➍✖❿✖Ï➬✖➮✍✖û✖ü✖ý ➆✖➱, ✑✖✒✖â✖þ✖✘÷✖ÿ✖⑩✁❾✖❿❲✟✚✠❲✦✚❡✁✂✖✩✁✄✖❾✖❿✖❋✁☎✖✜ ✳✖②➬✖➮❾✖❿✖❋✁☎, ✓✖✔✖❊❲✟✚✠✮ ✍✖✳✖②✖✓✁✆✖✛❬➦✖➧✜ ✝✁✞ ✟✚✠✮ ✍✠✟, ✰✁✡➍✁☛⑩✖s✖➯✁☞ E ✮ ✍✖✳✖②✁✌✖✹ f(e) = f(vi , vj ), ✍➚ f(e) ✘ 1
第十章网络的流 边(,)上的流量(有时也简写作). 图10-2所示的运输方案,就可看作是图10-1上的一个流,每条边上的第二个数字就 是该边上的运输量,称为流量,即1=3,∫2=1,13=1,14=1,f12=1,24=2, f=1,f3=2,j=2. 图10-2 以图10-2为例,显而易见,在运输网络的实际问题中,对于流有两个要求:一是每边 上的流量不能超过该边的最大通过能力(即边的容量):二是中间点的流量为零。因为中间 点只起转运作用,进出该点的流量相等所以我们说中间点的流量为零,另外,发点的净流 出量和收点的净流入量必相等,也是这个方案的总运输量,因此有 对于网络G上给出的满足以下条件的一组流称为可行流 1.容量限制条件.对任意边e=(i.)∈E有 0≤f≤c (10.1) 2.中间点平衡条件,对每个中间点(位≠s,)有 (10.2) 若以v(f)表示网络从s→t的流量(流值),则有 ∑-工-{0喜:时 (10.3) 任一网络G,至少存在一个可行流.因为对于所有的边e,定义=0,则∫显然满 足上述两个条件,称为零流。流值()=0。而运输网络的主要问题是要找出它的一个最 大流,即在满足容量限制和中间点平衡的条件下,使流值()达到最大.容量限制条件是 一个不等式,所以最大流问题是一个典型的线性规划问题, 因此,网络流的线性规划模型可以表示为 max 2=v(f) 满足 当i=s时 ∑f-∑fi= 0, 当i≠s,t时 -v(f),当i=t时 0≤f≤j其中()eE
2 ✎✑✏✓✒✕✔✓✖✑✗✓✘ s (vi , vj ) ✮ ✍✙✟➹ (❪✖➘✯ ➾✁✚✁✛ fij )✜ ⑥ 10–2 ✝ ➧ ✍✖❾✖❿✖❋✁☎, â✖✓✁✜✛✖✰✖⑥ 10–1 ✮ ✍✖✳✖②✖✛, ➸➷s✖✮✍✖✢✁✢✖②✖✹✖ö✖â ✰◆s◆✮✍◆❾◆❿◆➱, ➚✘◆✛◆➱, ý fs1 = 3, fs2 = 1, f13 = 1, f14 = 1, f12 = 1, f24 = 2, f43 = 1, f3t = 2,f4t = 2✜ ⑥ 10–2 ✔ ⑥ 10–2 ✘✖➀, ✣ ✷✖③✁✤, ⑩❾✖❿❲✟✚✠✖✍❯✖❱✑✖✒❲✦, ❂ ✲ ✛✖❪✁✥✖②✖❉✖▲: ✳✰➸ s ✮ ✍☞✛☞➱❏ û✧✦☞♣☞s✍✖✩✖➋☞♦✖♣☞û✖ü (ýs ✍☞➆☞➱); ✢✰✦✡➴☞r☞✍☞✛☞➱☞✘✧★☞✜✪✩✖✘✙✦✚➴ r✧✫✧✬☞➫☞❾✛❊ , ✭ ❩ r☞✍☞✛☞➱✧✮☞ï, ✝✔☞❼☞❽✧✯✙✦✡➴☞r☞✍☞✛☞➱✖✘✧★✖✜✸❖✖P, ✰ r☞✍✧✱☞✛ ❩ ➱✖➇✁✲✖r✖✍✁✱✖✛✖Õ✖➱✁✳✁✮✖ï, ✯ ✰❻②✖❋✁☎✖✍✁✴✖❾✖❿✖➱✖✜✵✩✁✶✖❪: ❂ ✲ ✟✚✠ G ✮➵❩ ✍✁✷✁✸✖✔✁✹➷✁✺✍✖✳✁✻✖✛➚✘✖✓✁✆✖✛: 1. ➆✖➱✁✼✁✽➷✁✺, ❂✁✾✁✿s e = (i, j) ∈ E ❪ 0 ≤ fij ≤ cij (10.1) 2. ✦✚➴✖r✁❀✁❁➷✁✺, ❂✖➸✖②❲✦✚➴✖r vi(i 6= s,t) ❪ X (vi,vj )∈E fij = X (vj ,vi)∈E fji (10.2) ❂✔ v(f) ➦✖➧ ✟✚✠✁❃ s → t ✍✖✛✖➱ (✛✁❄), ✃❪ Xfij − Xfji = ( v(f), ❅ i = s ➘ −v(f), ❅ i = t ➘ (10.3) ✾✖✳❲✟✚✠ G, ❆✁❇✁❈✖⑩✳✖②✖✓✁✆✖✛✖✜✵✩✖✘◆❂✲✝❪✖✍s e, ➍✁☛ fij = 0, ✃ f ✣✁❉✷ ✸ ✮①✥✖②➷✁✺, ➚✘❋❊✁✟✖✜❒✛✁❄ v(f) = 0✜❒✷✖❾✖❿❲✟✚✠✖✍✖➃✖❉✖✑✖✒✰❉✁✂❩ ➂✖✍✖✳✖②✖✩ ➋✖✛, ý⑩✷✁✸✖➆✖➱✁✼✁✽✖➇❲✦✚➴✖r✁❀✁❁✖✍➷✁✺✹ , ● ✛✁❄ v(f) ❍ Ð✖✩✖➋✖✜ ➆✖➱✁✼✁✽➷✁✺✰ ✳✖②❏ï✁■, ✝✔✖✩✖➋✖✛✖✑✖✒✰✳✖②✁❏✖✌✖✍✻✖✼✖✽✖✾✑✖✒✖✜ ✩✁✶, ✟✚✠✖✛✖✍✻✖✼✖✽✖✾☛✖✌✖✓✖✔ ➦✖➧✘ max z = v(f) ✷✁✸ Pfij − Pfji = v(f), ❅ i = s ➘ 0, ❅ i 6= s,t ➘ −v(f), ❅ i = t ➘ 0 ≤ fij ≤ ci,j , ❵❲✦(vi , vj ) ∈ E
$10.1基本概念和定理 3 列出运输网络图10-1的线性规划模型: max z=(f) 满足 f1+f2=v(f) (源s的流量平衡) 2+f3+4=j1(顶点1流量平衡 f24=f12+f2 (顶点2流量平衡 f3t=f13+f43 (顶点3流量平衡 far+faa=fi4+f4(顶点4流量平衡 v(f)=fst+ft (汇t的流量平衡 0≤f1≤4 0<f2<3 0≤f2≤2 (各边的流非负和不超过其容量) 0≤f13≤3 0≤f14≤1 0≤f4≤2 0≤fa≤2 0≤f3t≤3 0≤f≤4 这个模型显然可以用单纯形法求解。共15个约束条件,10个实际变量,9个松弛变量,6 个人工变量,共25个变量.若用单纯形法求解费时费事
§10.1 ❑✁▲✁▼✁◆✁❖✁P✁◗ 3 ❘❩ ❾✖❿❲✟✚✠⑥ 10–1 ✍✻✖✼✖✽✖✾☛✖✌: max z = v(f) ✷✁✸ fs1 + fs2 = v(f) (Û s ✍✖✛✖➱✁❀✁❁) f12 + f13 + f14 = fs1 (q✖r 1 ✛✖➱✁❀✁❁) f24 = f12 + fs2 (q✖r 2 ✛✖➱✁❀✁❁) f3t = f13 + f43 (q✖r 3 ✛✖➱✁❀✁❁) f4t + f43 = f14 + f24 (q✖r 4 ✛✖➱✁❀✁❁) v(f) = f3t + f4t (Ü t ✍✖✛✖➱✁❀✁❁) 0 ≤ fs1 ≤ 4 0 ≤ fs2 ≤ 3 0 ≤ f12 ≤ 2 (❙✖s✍✖✛✖➼✖➽✖➇❏✦✖♣✖❵✖➆✖➱ ci,j ) 0 ≤ f13 ≤ 3 0 ≤ f14 ≤ 1 0 ≤ f24 ≤ 2 0 ≤ f43 ≤ 2 0 ≤ f3t ≤ 3 0 ≤ f4t ≤ 4 ❻②☞☛☞✌✣✧❉✓☞✔☞❊☞❣❤☞✐●☞▲☞▼☞✜❯❚ 15 ②✧❱✧❲➷✧✺,10 ② ❯☞❱✧❳➱ ,9 ②✧❨✧❩❳ ➱ ,6 ②✧❬✧❭❳ ➱ , ❚ 25 ② ❳ ➱☞✜ ❂❊☞❣❤☞✐●☞▲☞▼, ➒☞➘☞➒✧❪ 1
第十章网络的流 图10-3 解在图10-3所示的网络G中,取={,,小,71={,4,t小,那么割 K(,T1)={1,),(2,) 制K的容量 c(%,71)=9+9=18. 注意在组成上述划的边集合中不句括(,2) 我们用表10-1列出图10-3中全部不同的割K及割K的容量c(M,), 表101 K(,T) cy,7) ,2,的,4, (s,,(s,2】 8,1 t2,均,4:t (s.y),(U1,2),(U1,s】 21 S.U7 v1.U3.U4.t (s.1),(y,v4) 17 ,4, 8,1, U2,U, (s,2,(o1,2,(g,,(,t) 19 5,2,4 ,3,t (s,1),(U4,3),(U4,t) 24 51,2,鸭 (2,a,(g,) s,1,2,4 3, (1,),(u4,g(v4,) 25 8,的,2,g,4 (g,t,(4,t) 15 具有最小容量的制称为最小割。由表10-1可知,图10-3中制K(,T)={(,,(,t} 的容量c(,7)=14是最小制 若用f(%,7)表示割中所有→71方向边的流量的总和,f(T1,M)表示割中所有 71一上方向边的流量的总和,则 f%,7)= (10.5) 0,) f,)= (10.6) G.0e71.M) 因为从源s到汇t的流量实际上等于从一了的流量中减去一的流量所 以对应于割处的流量为: (f)=f%,V)-f,) (10.7)
4 ✎✑✏✓✒✕✔✓✖✑✗✓✘ ⑥ 10–3 ⑤ : ⑩ ⑥ 10–3 ✝ ➧ ✍❲✟✚✠ G ✦ , ⑥ V1 = {s, v1, v2}, V 1 = {v3, v4,t}, ❆✖❇✖➈ K(V1, V 1) = {(v1, v3),(v2, v4)}. ➈ K ✍✖➆✖➱✖✜ c(V1, V 1) = 9 + 9 = 18. ⑦✿⑩✻✖þ✮①➈✖✍s✖➯✁☞ ✦❏✁⑧✁⑨ (v3, v2)✜ ❼✖❽✖❊➦ 10–1 ❘❩ ⑥ 10–3 ✦✓✇✁⑩❏✁④✍✖➈ K ➁✖➈ K ✍✖➆✖➱ c(V1, V 1). ➦ 10–1 V1 V 1 K(V1, V 1) c(V1, V 1) s v1, v2, v3, v4,t (s, v1),(s, v2) 15 s, v1 v2, v3, v4,t (s, v2),(v1, v2),(v1, v3) 21 s, v2 v1, v3, v4,t (s, v1),(v2, v4) 17 s, v1, v2 v3, v4,t (v1, v3),(v2, v4) 18 s, v1, v3 v2, v4,t (s, v2),(v1, v2),(v3, v2),(v3,t) 19 s, v2, v4 v1, v3,t (s, v1),(v4, v3),(v4,t) 24 s, v1, v2, v3 v4,t (v2, v4),(v3,t) 14 s, v1, v2, v4 v3,t (v1, v3),(v4, v3),(v4,t) 25 s, v1, v2, v3, v4 t (v3,t),(v4,t) 15 ❭❪✩➌➆➱✍➈➚✘❷❶❹❸❹❺☞✜ ❚✡➦ 10–1 ✓❹❻, ⑥ 10–3 ✦➈ K(V1, V 1) = {(v2, v4),(v3,t)} ✍✖➆✖➱ c(V1, V 1) = 14 ✰✩✖➌✖➈✖✜ ❂❊ f(V1, V 1) ➦✖➧➈❲✦✝❪ V1 → V 1 ❋❲➥s ✍✖✛✖➱✖✍✁✴✖➇,f(V 1, V1) ➦✖➧➈❲✦✝❪ V 1 → V1 ❋❲➥s ✍✖✛✖➱✖✍✁✴✖➇, ✃: f(V1, V 1) = X (i,j)∈(V1,V 1) fi,j (10.5) f(V 1, V1) = X (j,i)∈(V 1,V1) fj,i (10.6) ✩✖✘✁❃✖Û s Ð✖Ü t ✍✖✛✖➱❯✖❱✖✮ï ✲❃ V1 → V 1 ✍✖✛✖➱❲✦✓❼✖❧ V 1 → V1 ✍✖✛✖➱, ✝ ✔✖❂✖❃✲ ➈✁❽✖✍✖✛✖➱✖✘: v(f) = f(V1, V 1) − f(V 1, V1) (10.7)
$10.1基本概念和定理 5 若用(f)表示网络中从源s到t的最大流,则有: v(f)=f'(M,7)-f1,) (10.8) 用K表示最小割.根据割的概念,(f)应小于等于网络中最小割的容量(K),即 (f)=f(,T)-f(,)≤c(K*) (10.9) 由表10-1得出网络图10-3中从源s到汇t的最大流量不超过14单位。 三、最大流最小割定理 前面曾经指出,若∫广为满足下列条件的流: (f)=max{u(ff为G的一个流) 则称f为G的最大流 若K为满足下列条件的制 c(K)=min{c(K)川K为G的一个割} 则称K为最小割。 若网络G中由源s到汇t的流量达到最大值只能等于最小割K的容量,即()- c(K)。这就是著名的Ford-Fulkerson的最大流最小制定理,这是图和网络理论方面的 个重要定理,也是下面要叙述的用标记法求网络最大流的依据,在讲述这个定理之前先介 绍增流链的概念 在网络G中,设Q是一条从源到汇t的链,则在这条链Q上并且与Q的方向一致 的边,称为前向边,在Q上并且与Q的方向相反的边称为后向边. 例如在图10-3中,顶点序列s14t构成一条链,其中(s,),(1,),(4,)是前向 边,(,)是后向边 如果Q是从s到t的一条链,)是G的一个可行流,满足: 1.0≤0,则可 选择一适当小的正数: 0=min 了c-f,当(色,)是Q的前向边 当(6,)是Q的后向边 然后,再令前向边上的流都加日,后向边上的流都减A,不在增流链上的边,流不变。 用算式表示就是 +8,当位,)是Q的前向边: -8,当(位,》是Q的后向边: 其它
§10.1 ❑✁▲✁▼✁◆✁❖✁P✁◗ 5 ❂❊ v(f ∗ ) ➦✖➧ ✟✚✠❲✦✓❃✖Û s Ð t ✍✖✩✖➋✖✛, ✃❪ : v(f ∗ ) = f ∗ (V1, V 1) − f ∗ (V 1, V1) (10.8) ❊ K∗ ➦✖➧✩✖➌✖➈✖✜✵❾✁❿✖➈✖✍➉✖➊,v(f ∗ ) ❃✖➌✲ï ✲ ✟✚✠❲✦✚✩✖➌✖➈✖✍✖➆✖➱ c(K∗ ), ý v(f ∗ ) = f ∗ (V1, V 1) − f ∗ (V 1, V1) ≤ c(K∗ ) (10.9) ❚✚➦ 10–1 ❧❩ ✟✚✠⑥ 10–3 ✦✓❃✖Û s Ð✖Ü t ✍✖✩✖➋✖✛✖➱❏✦✖♣ 14 ❣✁➀✖✜ ➁➟♦➂➄➃➠➡➄➂➆➅✠♥➆➇✠➈ ➉⑨✑➊✓➋✡❩ , ❂ f ∗ ✘✁✷✁✸✁✹❘➷✁✺✍✖✛: v(f ∗ ) = max{v(f)|f✘ G ✍✖✳✖②✖✛}, ✃➚ f ∗ ✘ G ✍✙❶✁➌✁✟✖✜ ❂ K∗ ✘✁✷✁✸✁✹❘➷✁✺✍✖➈: c(K∗ ) = min{c(K)|K✘ G ✍✖✳✖②✖➈}, ✃➚ K∗ ✘✙❶✁❸✁❺✖✜ ❂✟✚✠ G ✦ ❚ Û s Ð✖Ü t ✍✖✛✖➱❍ Ð✖✩✖➋✁❄✁✫✖û✖ï✲✩✖➌✖➈ K ✍✖➆✖➱, ý v(f ∗ ) = c(K∗ )✜ ❻â✰✁➍✁➎ ✍ Ford-Fulkerson ✍✖✩✖➋✖✛✖✩✖➌✖➈✖➍✖➎✖✜ ❻✰✖⑥➇❲✟✚✠◆➎⑦❋✖⑨◆✍✖✳ ②☞⑧☞❉☞➍☞➎, ✯ ✰✹☞⑨☞❉✧➏①✍☞❊☞➐☞➑✖●☞▲❲✟✡✠✖✩✖➋☞✛✖✍✧➐✁❿☞✜ ⑩✁➑①❻②✖➍✖➎☞è➉r✖✧ ★✁➒✖✛✁➓✖✍➉✖➊✜ ⑩ ✟✚✠ G ✦ , ➤ Q ✰✳➷❃✖Û s Ð✖Ü t ✍✁➓, ✃✖⑩❻✖➷➓ Q ✮✁✍❛✁➔ Q ✍✖❋❲➥✚✳✁→ ✍s, ➚✘➉➥s, ⑩ Q ✮✁✍❛✁➔ Q ✍✖❋❲➥✓✮✁➣✖✍s ➚✘✁↔❲➥s ✜ ➀÷✖⑩⑥ 10–3 ✦ , q✖r✁↕❘ sv1v3v4t ❫✖þ✖✳➷➓ , ❵❲✦ (s, v1),(v1, v3),(v4,t) ✰➉➥ s,(v3, v4) ✰↔❲➥s ✜ ÷✁➙ Q ✰❃ s Ð t ✍✖✳➷➓ ,fij ✰ G ✍✖✳✖②✖✓✁✆✖✛, ✷✁✸: 1. 0 ≤ fij 0, ✃✓ ➝✁➞✳✁➟❅➌✖✍✁➠✖✹ θ: θ = min ( ci,j − fi,j , ❅ (i, j) ✰ Q ✍➉➥s, fi,j , ❅ (i, j) ✰ Q ✍✁↔❲➥s ❉ ↔ , ➡✁➢➉➥s✖✮✍✖✛✿✁➤ θ, ↔❲➥s✖✮✍✖✛✿❼ θ, ❏✖⑩➒✖✛✁➓✮ ✍s, ✛❏✁❳✜ ❊✖❘✁■➦✖➧â✰ : f 0 i,j = fi,j + θ, ❅ (i, j) ✰ Q ✍➉➥s; fi,j − θ, ❅ (i, j) ✰ Q ✍✁↔❲➥s; fi,j , ❵✖➂
第十章网络的流 此时()=x()+日.显然仍为一个可行流,但较之原来的可行流f,这时网络中从源 s到汇t的流量增大了一个日值.因此,对于一个给定的网络可行流,经过儿次调整,直至 找不出增流链,就得到最大流。 这也就是说。若网络中的流量已达到最大值则在该网络中不可能再找出增流链。对 给定的流∫,我们构造 个点的集合,定义 1.sEVi: 2.若,∈和f0,则∈. 根据的定义,可以证明t∈了1.否则,将有一条从s到t的增流链,此链的全部前 向边(,+)满足 f(,+1)0 这样,这条能将是可增流的,与假设矛盾。因此必有t∈T. 由此K(K,T)为网络的一个割,该制的容量为c(,下)。同时,按的定义通过 这个刺的流为: f,)=∑=∑c=c%,7) (10.10) (iJ)E(V.V;) f7,y)= j=0 (10.11) 00E(M,) 因我们假定网络中流量已达到最大,有 f)=fM,T)=c(,)2c(K (10.12) 由(10.9),(f)≤c(K) (10.9)与(10.12)式同时满足,一定有v(f*)=c(K). 根据上述论证,我们可得最大流最小割定理: 定理10.1.1在运输网络中,最大流的流值等于最小割的容量 §10.2求网络最大流的标记算法 一、算法思路 标记法求最大流是从一个可行流出发(若网络G中没有给定的初始可行流,可由零 流出发),经过标记和调整两个过程。 标记过程:这是用来寻找增流链的过程 先从源开始,若源能正向输送流到顶点,就说明顶点是可标的.在这个过 程中,网络中的顶点或被标记(按标记的先后顺序需逐点检在,所以又分检查和未检查两 种),或者未被标记,每个顶点给两种不同的记号:第一个表示它的标记是从哪一顶点得到 的。以便找出增流能第二个标记是为确岸增流麟的用格量日用的.在标记过程中,有标记 的顶点表示是中的点,没有标记的不是中的点。一旦汇t得到了标记,表明找到了
6 ✎✑✏✓✒✕✔✓✖✑✗✓✘ ✶✖➘ v(f 0 ) = v(f) + θ✜ ✣✁❉ f 0 ➥✘✖✳✖②✖✓✁✆✖✛, ➦ ❢✖è✁➧❬✍✖✓✁✆✖✛ f, ❻➘❲✟✚✠❲✦✓❃✖Û s Ð✖Ü t ✍✖✛✖➱✁➒✖➋✖Ú✖✳✖② θ ❄✖✜➨✩✁✶, ❂ ✲✳✖②✖➵✖➍✖✍❲✟✚✠✖✓✁✆✖✛, ➋✖♣✁➩✁➫✁➭❅ , ♠ ❆ ✂❏ ❩ ➒✖✛✁➓, â✁❧✖Ð✖✩✖➋✖✛✖✜ ❻ ✯ â✰✯ , ❂✟✚✠❲✦✚✍✖✛✖➱✑➯❍ Ð✖✩✖➋✁❄, ✃✖⑩✁✟✚✠❲✦❏✓✖û➡ ✂❩ ➒✖✛➲➓✖✜➄❂ ➵✖➍✖✍✖✛ f, ❼✖❽✖❫✁➳✖✳✖②✖r✖✍➯✁☞ V1, ➍✁☛: 1. s ∈ V1; 2. ❂ vi ∈ V1 ➇ fi,j 0, ✃ vj ∈ V1 ✜ ❾✁❿ V1 ✍✖➍✁☛, ✓✖✔✁➵✑➸ t ∈ V 1 ✜✵➺✃, ❤✖❪✖✳➷❃ s Ð t ✍✁➒✖✛✁➓, ✶✁➓✖✍✁✇✁⑩➉ ➥s (vi , vi+1) ✷✁✸: f(vi , vi+1) 0. ❻✖á, ❻✖➷➓✁❤✰✓✁➒✖✛✖✍, ➔❮ ➤✁➻✁➼✜✵✩✁✶✁✳✖❪ t ∈ V 1 ✜ ❚ ✶ ,K(V1, V 1) ✘❲✟✚✠✖✍✖✳✖②✖➈, ➈✖✍✖➆✖➱✖✘ c(V1, V 1)✜ ④➘ , ➽ V1 ✍✖➍✁☛, ♦✖♣ ❻②✖➈✖✍✖✛✖✘: f(V1, V 1) = X (i,j)∈(V1,V 1) fij = X (i,j)∈(V1,V 1) cij = c(V1, V 1) (10.10) f(V 1, V1) = X (j,i)∈(V1,V 1) fji = 0 (10.11) ✩✖❼✖❽❮ ➍❲✟✚✠❲✦✚✛✖➱✑➯❍ Ð✖✩✖➋, ❪ v(f ∗ ) = f(V1, V 1) = c(V1, V 1) ≥ c(K∗ ) (10.12) ❚ (10.9),v(f ∗ ) ≤ c(K∗ ). (10.9) ➔ (10.12) ■ ④➘✁✷✁✸, ✳✖➍✖❪ v(f ∗ ) = c(K∗ )✜ ❾✁❿✮①⑦➵ , ❼✖❽✖✓✁❧✖✩✖➋✖✛✖✩✖➌✖➈✖➍✖➎: ➾✁➚ 10.1.1 ➪✁➶✁➹✑➘✓➴✑➷ , ➬✁➮✁➱✁✃✁➱✁❐✁❒✁❮✁➬✁❰✁Ï✁✃✁Ð✁Ñ✜ §10.2 ÒÔÓÔÕÔÖÔ×ÔØÔÙÔÚÔÛÔÜ❷Ý Þ❞✵ß✁à✁á✁â ➐◆➑◆●◆▲◆✩◆➋◆✛✰❃◆✳◆②◆✓➲✆◆✛❩ ✰ (❂ ✟➔✠ G ✦➔Ó◆❪◆➵◆➍◆✍➲ã➲ä◆✓➲✆◆✛, ✓ ❚ ★ ✛❩ ✰), ➋✖♣✖➐✖➑✖➇✁➭❅✥✖②✖♣✁å✖✜ æ✁ç✁è✁é: ❻✰❊❬❡✁✂✁➒✖✛✁➓✖✍✖♣✁å. r➲❃◆Û s ê ä , ❂Û s û➲➠➓➥➔❿◆Ï◆✛◆Ð◆q◆r vi , â➲✯ë➸➔q◆r vi ✰✓◆➐◆✍◆✜ ⑩❻②◆♣ å➓✦, ✟➔✠➓✦➔✍◆q◆r❄➲ì➐◆➑ (➽ ➐◆➑◆✍➲r➲↔➲í➲↕➲q➲î◆r➲ï➲ð, ✝✔◆✺➲ñ➲ï➲ð◆➇➲ò➲ï➲ð➲✥ ❫ ), ❄✁óòì➐✖➑✖✜ ➸✖②✖q✖r✖➵✁✥❫ ❏✁④✍✖➑✁ô: ✢✖✳✖②➦✖➧➂✖✍✖➐✖➑✰❃✁õ✖✳✖q✖r✁❧✖Ð ✍ , ✔✧❦✧✂❩ ➒☞✛✧➓; ✢✧✢☞②☞➐☞➑✰✘ ➏➍✧➒☞✛✧➓✖✍✧➭❅➱ θ ❊☞✍☞✜ ⑩ ➐☞➑☞♣✧å✙✦, ❪☞➐☞➑ ✍✖q✖r➦✖➧✰ V1 ✦✚✍✖r, Ó✖❪✖➐✖➑✖✍❏✰ V1 ✦✚✍✖r✖✜➄✳✁ö✖Ü t ❧✖Ð✖Ú✖➐✖➑, ➦ ➸✓✂✖Ð✖Ú
510.2录网络最大流的标记算法 7 一条从s到t的增流链如果标记过程无法进行下去,而t尚未标记则表明不存在s到t 的增流能,于是得到最大流,同时也得到一个最小割 调整过程:这是用来增大流量的过程 根据顶点的第一个标记,“反向追踪”找出增流链Q.令调整量0是④),即t点的第二 个标记。在增流链上的一切前向边上增加日,后向边上减少日,其它边的流量保持不变.这 样就得到新的可行流。对新的可行流重新转入标记过程当再也找不到新的增流链时,即 汇t得不到标记时,算法终止, 二、算法步骤 第一步:开始给源s标上(0,+)(括号中第一个数字,因S是源故记为0),这时S 是已标记而未检查的点,其余都是未标记点。按得到标记的先后顺序,取一个已标记而未 检查的点,对相邻的一切未标记的点 L.若在边(,)上,0则给标记(-,l(y).这里l(y,))=mim{l(,f. 这时顶点成为已标记而未检查的点 第二步:成为已标记已检在过的顶点,在标记下面划一横线。重复第一步,一旦汇 被标记表明得到一条从s到t的增流链Q,进行第三步,若所有被标记的顶点都已检查 过,而标记过程进行不下去时,则算法结束,这时的可行流就是最大流 第三步:按汇t及其它顶点的第一个标记,“反向追踪”找出增流Q,用双线画出。 令调整量0=1),即汇t的第二个标记.令: +,当(,)是Q的前向边 f=了,-8,当(位,)是Q的后向边 其它 按新的可行流画出网络G,对新流(新G)重新进入标记过程。 例2.用标记法求图10-4所示网络的最大流,并找出最小割。边旁的数字是(c,), 图10-4 解(一、标记过程 (1).先给源S标上(0,+∞) (2).对S进行检查,从S点出发的边(s,)上,f1-c1-8故m1得不到标记 边(s,)上,f2<c,2,故2的标记为(+s,(2,其中,1(2)=mim{l(s,(c,2-,2}
§10.2 ÷✁✔✓✖✁ø✁ù✁✘✑✗✓ú✁û✁ü✑ý 7 ✳➷❃ s Ð t ✍✁➒✖✛✁➓; ÷✁➙➐✖➑✖♣✁å✁þ✖●✭ ✆✁✹✖❧, ✷ t ❴ò✖➐✖➑, ✃✖➦ ➸❏✁❈✖⑩ s Ð t ✍✁➒✖✛✁➓, ✲✰❧✖Ð✖✩✖➋✖✛, ④➘ ✯ ❧✖Ð✖✳✖②✖✩✖➌✖➈✖✜ ÿ✁è✁é: ❻✰❊❬➒✖➋✖✛✖➱✖✍✖♣✁å. ❾✧❿☞q☞r☞✍☞✢☞✳☞②☞➐☞➑,“➣❲➥✄✂✁☎” ✂❩ ➒☞✛✧➓ Q✜ ➢ ➭❅➱ θ ✰ l(t), ý t r☞✍☞✢✧✢ ②✖➐✖➑✖✜ ⑩ ➒✖✛✁➓✮ ✍✖✳✁✆➉➥s✖✮➒➤ θ, ↔❲➥s✖✮❼ ❇ θ, ❵✖➂s ✍✖✛✖➱✁✝✁✞❏✁❳✜ ❻ áâ✁❧✖Ð✁✟✖✍✖✓✁✆✖✛✖✜➄❂✁✟✖✍✖✓✁✆✖✛◆⑧✁✟✖➫◆Õ✖➐◆➑✖♣➲å, ❅✁➡✖✯✂❏ Ð✁✟✖✍✁➒✖✛✁➓✖➘, ý Ü t ❧ ❏ Ð✖➐✖➑✖➘, ❘✖●✈✁✠✜ ✡☞☛✍✌✏✎✏✑✏✒ ✓Þ✁✔: ê ä✖➵✖Û s ➐ ✮ (0, +∞)(⑨ ô❲✦✚✢✖✳✖②✖✹✖ö, ✩ S ✰Û , ✕ ➑✖✘ 0), ❻➘ S ✰ ➯✚➐✖➑✖✷✁ò✁ï✁ð✖✍✖r, ❵✁✖✿✰ò✖➐✖➑✖r✖✜ ➽ ❧✖Ð✖➐✖➑✖✍✁r✁↔➲í✁↕, ⑥ ✳✖②✑➯✚➐✖➑✖✷✁ò ï✁ð✖✍✖r vi , ❂✁✮✁✗✖✍✖✳✁✆✁ò✖➐✖➑✖✍✖r vj : 1. ❂ ⑩☞s (vi , vj ) ✮, fi,j 0, ✃➵ vj ➐✖➑ (−vi , l(vj ))✜ ❻❺ l(vj ) = min{l(vi), fj,i}✜ ❻➘✖q✖r vj þ✖✘✑➯✚➐✖➑✖✷✁ò✁ï✁ð✖✍✖r✖✜ ✓✁✘✔: vi þ✖✘✑➯✚➐✖➑✑➯✓ï✁ð✖♣✖✍✖q✖r, ⑩ ➐✖➑✁✹✖⑨✾✳✁✙✻✜ ⑧✁✚✖✢✖✳✁✛, ✳✁ö✖Ü t ì➐✖➑, ➦ ➸✓❧✖Ð✖✳➷❃ s Ð t ✍✁➒✖✛✁➓ Q, ✭ ✆✖✢✁✜✁✛✖✜ ❂✝❪ì➐✖➑✖✍✖q✖r✿ ➯✓ï✁ð ♣ , ✷✖➐✖➑✖♣✁å✭ ✆ ❏✹✖❧✖➘, ✃❘✖●✖✗✁❲, ❻➘✖✍✖✓✁✆✖✛✖â✰✩✖➋✖✛✖✜ ✓✣✢✔: ➽ Ü t ➁✣✤✣✥✣✦✣✧✣★✣✩✣✪✣✫✣✬✣✭,“➣✯✮✰✂✣☎” ✱✣✲✣✳✣✴✣✵ Q, ✶✣✷✣✸✣✹✣✲✣✺ ✻✁✼✁✽✁✾ θ = l(t), ✿✁❀ t ★✁✩✁❁✁✫✁✬✁✭✺ ✻ : f 0 i,j = fi,j + θ, ❂ (i, j) ❃ Q ★✁❄❅✮❇❆ fi,j − θ, ❂ (i, j) ❃ Q ★✁❈❅✮❇❆ fi,j , ✤✁✥ ❉✁❊★✁❋✁●✴✁✹✁✲❅❍❇■ G, ❏ ❊ ✴ (❊ G) ❑ ❊✁▲✁▼✬✁✭✁◆✁❖✺ P 2. ✶✬◗✭◗❘◗❙◗❚ 10–4 ❯◗❱❲❍❳■★◗❨◗❩✴, ❬◗✱◗✲❨◗❭◗❪✺ ❆◗❫◗★◗❴◗❵❃ (ci,j , fi,j )✺ ❚ 10–4 ❛ : (✪ )❜ ✬✁✭✁◆✁❖ (1). ❝✁❞✁❡ S ✬✁❢ (0, +∞) (2). ❏ S ▲●✁❣✁❤, ✐ S ✧ ✲✁❥★✁❆ (s, v1) ❢ , fs,1 = cs,1 = 8 ❦ v1 ❧✁♠✁♥✬✁✭✺ ❆ (s, v2) ❢ ,fs,2 < cs,2, ❦ v2 ★✁✬✁✭✁♦ (+s, l(v2)), ✤❅♣,l(v2) = min{l(s),(cs,2 − fs,2)} =
8 第十章网络的流 mim{+oo,2}=2.S成为已检在过的点。 (3.取已标记而未检查的点2,检查2,在边(m,2)上,,2=4>0,故对1标记 (-2,(m),并且有:l(m)=min{l(2,f五2}=min2,4}=2.在边(,2)上,f,2=0,故 的得不到标记。在边(2,)上,f24=24=9,不满足标记条件,4也得不到标记。2也 成为已检查过的点 (4).检查1,在边(心1,均)上,方.3=40,故给标记为(-,(》,其中1() min(3,f4,3}=min{2,1}=1.在边(,t)上,f,t=c3,t=5,t不能标记. (6).检查4,在边(4,t)上ft=8<c4t=10,故t点得到标记(+4,l(t),其中 minl(a),(G -.》=mim1,2}=1,因汇t得到标记进行下一步调整过程 (二).调整过程 (1).“反向追踪”,按顶点的第一个标记找到一条增流链Q=s2144,如图10-4双 线所示。 (②).按6-1(-1调增流上各边的流量 f2=f.2+0=5+1=6 fi3=f1.3+0=4+1=5 fie=fa+-8+1-9 f12=i2-9-4-1=3 f{3=f3-0=1-1=0 其它边上流量保持不变.调整后得到网络图上一个新的可行流,如图10-5所示: 图10-5 在图10-5中重复上述标记过程,寻找增流链.开始给S标记(0,+∞,检查5,给 标记(+s,1),检查2,给1标记(-2,1),检查1,给购标记(+1,1),检察购,边(4,) 上3=0,边(,)上,1=,均不符合标记条件标号过程无法进行,算法结束。故 图10-5给出的可行流即为该网络的最大流,最大流量为: f=f,1+f,2=f3.t+f4,t=14. 现已标记的顶点集合={s,1,2,,未标记的顶点集合了1={4,,故有 K(,了)={2,4(,t}是该网络的最小割它的容量c(,)-14 由此可见,最小割的容量大小影响最大流的流值.最小割是网络中能力最紧张的那些 边.为提高最大流值,必须增大割中边的容量.反过来,如果最小割中边的能力被降低,就 会使最大流的流值降低
8 q❅r❇s✉t❇✈❅✇❇① min{+∞, 2} = 2✺ S ② ♦❅③❇❣✁❤✁◆✁★✁✧✺ (3). ④ ③✰✬✣✭✣⑤✣⑥✣❣✣❤✣★✣✧ v2, ❣✣❤ v2, ⑦❆ (v1, v2) ❢ ,f1,2 = 4 > 0, ❦✣❏ v1 ✬✣✭ (−v2, l(v1)), ❬✁⑧✁⑨:l(v1) = min{l(v2), f1,2} = min{2, 4} = 2✺⑩⑦❆ (v3, v2) ❢ ,f3,2 = 0, ❦ v3 ❧✁♠✁♥✬✁✭✺⑩⑦❆ (v2, v4) ❢ , f2,4 = c2,4 = 9, ♠✁❶✁❷✬✁✭✁❸✁❹,v4 ❺✁❧✁♠✁♥✬✁✭✺ v2 ❺ ② ♦❅③❇❣✁❤✁◆✁★✁✧✺ (4). ❣✣❤ v1, ⑦❆ (v1, v3) ❢ , f1,3 = 4 0, ❦✁❞ v4 ✬✁✭✁♦ (−v3, l(v4)), ✤❅♣ l(v4) = min{l(v3), f4,3} = min{2, 1} = 1✺⑩⑦❆ (v3,t) ❢ ,f3,t = c3,t = 5,t ♠✁❻✬✁✭✺ (6). ❣✣❤ v4, ⑦❆ (v4,t) ❢ ,f4,t = 8 < c4,t = 10, ❦ t ✧❧✣♥✬✣✭ (+v4, l(t)), ✤✯♣ l(t) = min{l(v4),(c4,t − f4,t)} = min{1, 2} = 1, ❼✁❀ t ❧✁♥✬✁✭, ▲●✁❽✁✪✁❾✼✁✽◆✁❖✺ (❿)❜⑩➀✁➁✁➂✁➃ (1). “➄ ✮❇➅✁➆”, ❉✦✁✧✁★✁✩✁✪✁✫✁✬✁✭✱♥✪✁❸✳✁✴✁✵ Q = sv2v1v3v4t, ➇ ❚ 10–4 ✷ ✸✁❯✁❱✁✺ (2). ❉ θ = l(t) = 1 ✼✁✽✳✁✴✁✵❢✁➈✁❆✁★✴✾ : f 0 s,2 = fs,2 + θ = 5 + 1 = 6 f 0 1,3 = f1,3 + θ = 4 + 1 = 5 f 0 4,t = f4,t + θ = 8 + 1 = 9 f 0 1,2 = f1,2 − θ = 4 − 1 = 3 f 0 4,3 = f4,3 − θ = 1 − 1 = 0 ✤✁✥✁❆✁❢✴✾✁➉✁➊♠✁➋✺ ✼✁✽❈❧✁♥ ❍❇■❚✁❢✁✪✁✫❊★✁❋✁●✴, ➇ ❚ 10-5 ❯✁❱: ❚ 10–5 ⑦ ❚ 10–5 ♣❑✁➌❢✁➍✁✬✁✭✁◆✁❖, ➎✁✱✁✳✁✴✁✵✁✺⑩➏✁➐✁❞ S ✬✁✭ (0, +∞), ❣✁❤ S, ❞ v2 ✬✁✭ (+s, 1), ❣✁❤ v2, ❞ v1 ✬✁✭ (−v2, 1), ❣✁❤ v1, ❞ v3 ✬✁✭ (+v1, 1), ❣✁➑ v3, ❆ (v4, v3) ❢ f4,3 = 0, ❆ (v3,t) ❢ , f3,t = c3,t, ➒♠✁➓✁➔✬✁✭✁❸✁❹, ✬✁→✁◆✁❖✁➣✁❘▲● , ↔❘✁↕✁➙✺➛❦ ❚ 10–5 ❞✁✲ ★✁❋✁●✴✁✿♦✁➜❍❇■★✁❨✁❩✴✁✺ ❨✁❩✴✾♦ : v(f ∗ ) = fs,1 + fs,2 = f3,t + f4,t = 14. ➝ ③➞✬➟✭➟★➟✦➟✧➟➠➔ V1 = {s, v1, v2, v3}, ⑥➟✬➟✭➟★➟✦➟✧➟➠➔ V 1 = {v4,t}, ❦➟⑨ K(V1, V 1) = {(v2, v4),(v3,t)} ❃➜ ❍❇■★✁❨✁❭✁❪, ✥✁★✁➡✾ c(V1, V 1) = 14✺ ➢✄➤❋➦➥, ❨➦❭➦❪➦★➦➡✾❩➦❭➦➧➦➨➦❨➦❩✴ ★✴➦➩✁✺ ❨✁❭➦❪❃➫❍❇■♣❻✁➭❨✁➯➦➲✁★➦➳✁➵ ❆ ✺ ♦✁➸✁➺✁❨✁❩✴✁➩, ➻✁➼✁✳❩✁❪❅♣❇❆✁★✁➡✾ ✺➽➄◆✁➾, ➇✁➚❨✁❭✁❪❅♣❇❆✁★❻✁➭✁➪✁➶✁➹, ➘ ➴✁➷❨✁❩✴ ★✴✁➩➶✁➹✺
$10.3最大流最小割定理的推广 9 §10.3最大流最小割定理的推广 在这一节里,我们介绍一下最大流最小割定理的推广, 一、多源多汇的运输网络 一个运输网络上可能有多个源s1,s2,…,sm和多个汇t1,2,,tn.如图10-6所示 图10-6 顶点和妇都是和台都是汇是中转点,间题是使从源1和。 输送到汇1和2的总流量最大。为了能够利用上述定理和求解算法,我们把原问题转换 成单源,单汇形式.具体来说。建立一个虚设的源s和汇t,连接新的边(s,s1,(s,s2)和 (化1,),(2,t),同时指定它们的容量均为+0,这样,就有了一个如图10-7所示的典型最 大流问题网络。 图10-7 二、顶点具有容量的运输网络 假如在一个网络G上不仅边具有容量而且顶点也具有容量,顶点包括源和汇。求从 源到汇的最大流时,可能会受到顶点容量的限制,或者是顶点有容量限制,而边上的容量 无限制。对于这种类型的网络不难把它转换为我们已讨论过的网络,具体做法是: 把有容量的顶点分为两个顶点和心,同时在和《之间连一条边(,),并 且约定所有可达顶点的边都改为到达而把所有的边(,)改为(,)并给边 (,以容量c(心,)-c().如图10-8所示,这样,就可以把顶点也具有容量的网络上 求最大流问题转换为我们已讨论过的网络向题了
§10.3 ➬✁➮✁①✁➬✁➱❅✃❇❐✁❒❅✇❇❮✁❰ 9 §10.3 ÏÑÐÑÒÑÏÑÓÑÔÑÕÑÖÑ×ÑØÚÙ ⑦✁Û✪✁Ü✁Ý, Þ✁ß✁à✁á✪✁❽✁❨✁❩✴❨✁❭✁❪✁â✁ã✁★✁ä✁å✺ æèçêéèëèéèìîíðïðñîòðó ✪✁✫✁ô✁õ ❍❇■❢✁❋❻⑨✁ö✫❡ s1, s2, . . . , sm ÷ö✫ ❀ t1,t2, . . . ,tn ✺⑩➇❚ 10–6 ❯✁❱: ❚ 10–6 ✦✣✧ s1 ÷ s2 ø❃✣❡,t1 ÷ t2 ø❃✣❀,v1,v2,. . .,v6 ❃ ♣✰ù✣✧✺ûú✣ü✣❃➷✐✣❡ s1 ÷ s2 õ✁ý♥❀ t1 ÷ t2 ★✁þ✴✾❨✁❩✺ ♦✁ÿ❻✁✁✂✶❢✁➍✁â✁ã÷❙✁✄↔❘ , Þ✁ß✁☎✁✆✁ú✁üù✁✝ ②✟✞✣❡, ✞✣❀✟✠✟✡✣✺☞☛✟✌➾✟✍, ✎✟✏✪✣✫✟✑✟✒✣★❡ s ÷❀ t, ✓✟✔❊★✣❆ (s, s1),(s, s2) ÷ (t1,t),(t2,t), ✕✁✖✁✗â✁✘ß ★✁➡✾ ➒♦ +∞ ✺⑩Û✁✙, ➘✁⑨ÿ✁✪✁✫➇ ❚ 10–7 ❯✁❱★✁✚✁✛✁❨ ❩ ✴✁ú✁ü❅❍❇■✁✺ ❚ 10–7 ✜ç✣✢✥✤✥✦✥✧✩★✫✪ðíðïîñðòîó ✬ ➇✣⑦✪✣✫ ❍✰■ G ❢ ♠✟✭❆ ☛✣⑨➡✾⑤⑧ ✦✣✧❺☛✣⑨➡✾ , ✦✣✧✟✮✟✯❡÷❀✣✺ ❙✐ ❡♥❀ ★✁❨✁❩✴✁✖, ❋ ❻➴✁✰♥✦✁✧✁➡✾★✁✱✁✲, ✳✁✴✁❃✦✁✧⑨ ➡✾✱✁✲✺ ⑤✁❆✁❢✁★✁➡✾ ➣✁✱✁✲✺⑩❏✁✵✁Û✁✶✁✷✛✁★ ❍❇■♠✁✸☎ ✘✁ù✁✝✁♦Þ✁ß ③✺✹✁✻✁◆✁★ ❍❇■, ☛✁✌✁✼❘ ❃: ☎✁⑨➡✾★✁✦✁✧ vi ✽ ♦✁✾✁✫✁✦✁✧ v 0 i ÷ v 00 i , ✕✁✖✁⑦ v 0 i ÷ v 00 i ✿✁❀✓ ✪✁❸✁❆ (v 0 i , v 00 i ), ❬ ⑧✟❁â❯✣⑨❋✟❂✣✦✣✧ vi ★✣❆ø✟❃♦ ♥❂ v 0 i ; ⑤☎✣❯✣⑨★✣❆ (vi , vj ) ❃ ♦ (v 00 i , vj ), ❬✣❞❆ (v 0 i , v 00 i ) ❄ ➡✾ c(v 0 i , v 00 i ) = c(vi), ➇ ❚ 10-8 ❯✁❱✁✺ Û✁✙, ➘ ❋ ❄✁☎✦✁✧❺☛✁⑨➡✾★ ❍❇■❢ ❙✁❨✁❩✴✁ú✁üù✁✝✁♦Þ✁ß ③✺✹✁✻✁◆✁★ ❍❇■✁ú✁üÿ ✺
10 第十章网络的流 图10-8 三、应用举例 例3.某种物资有两个产地1和2,三个销地,t2和ta.运输网络如图10-9所示, 其中和2是两个中转站。所标数字是线路的最大输送能力。试求从产地到销地的最 大运送量,并找出最小羽: 图10-9 解这是一个多源多汇的运输网络.为了能该用本章第二节中介绍的算法求它的最 大流,需要索它化成源汇的网络。我们在网络中虚设一个源s和一个汇t以及s到 51,。的边,不2到的翅。边(6)的容量取作所有以为始点的边的容量之和或为 +,这里取10+5+12=27.同样,边(s,s2)的容量可取作15+12=27。而边(,)的 容量取作所有以1为终点的边的容量之和或为+,边(2,)和(3,t)的容量类同,这样 就得到网络图10-10.求佳的结果也标在图10-10上,边旁的数字是(c,f). 图10-10
10 q❅r❇s✉t❇✈❅✇❇① ❚ 10–8 ❅ç✣❆✥❇✥❈✥❉ P 3. ❊✟✶✟❋✟●✣⑨✾✣✫✟❍✟■ s1 ÷ s2, ❏ ✫✟❑✟■ t1,t2 ÷ t3 ✺ ô✣õ ❍✰■✣➇❚ 10-9 ❯✣❱, ▲ ♣ v1 ÷ v2 ❃ ✾✣✫✯♣✰ù✟▼✺⑩❯✬✣❴✣❵❃✣✸✟◆★✣❨✣❩✣õ✣ý❻✣➭✺P❖❙✐ ❍✟■♥ ❑✟■✣★✣❨ ❩✁ô✁ý✾ , ❬✁✱✁✲ ❨✁❭✁❪✺ ❚ 10–9 ❛ : Û✣❃✪✣✫ö✣❡✣ö✣❀★✣ô✣õ ❍✰■✣✺ ♦✣ÿ ❻✟✶✟◗✟❘✩✣❁✣Ü✍♣à✣á★↔❘✣❙✟✘★✣❨ ❩ ✴, ❙✟❚✟☎✘✟❯②✟✞✣❡✟✞✣❀★ ❍✰■✣✺⑩Þ✣ß✣⑦✯❍✰■ ♣❱✑✟✒✣✪✣✫❡ s ÷✪✣✫❀ t ❄✟❲ s ♥ s1,s2 ★✁❆,t1,t2,t3 ♥ t ★✁❆✺ ❆ (s, s1) ★✁➡✾ ④✁❳✁❯✁⑨✁❄ s1 ♦➐ ✧✁★✁❆✁★✁➡✾ ✿÷✳ ♦ +∞ , Û Ý ④ 10 + 5 + 12 = 27✺❨✕✁✙, ❆ (s, s2) ★✁➡✾❋ ④✁❳ 15 + 12 = 27✺ ⑤✁❆ (t1,t) ★ ➡✾ ④❩❳➦❯➦⑨❩❄ t1 ♦❩❬➦✧➦★➦❆➦★➦➡✾ ✿÷✳ ♦ +∞, ❆ (t2,t) ÷ (t3,t) ★➦➡✾ ✷❩✕➦✺ Û❩✙ ➘❧✁♥ ❍❇■❚ 10–10✺ ❙✁✄✁★✁↕➚❺ ✬ ⑦ ❚ 10–10 ❢ , ❆✁❫✁★✁❴✁❵❃ (cij , fij )✺ ❚ 10–10