第十章网络的流 此时()=x()+日.显然仍为一个可行流，但较之原来的可行流f,这时网络中从源 s到汇t的流量增大了一个日值.因此，对于一个给定的网络可行流，经过儿次调整，直至 找不出增流链，就得到最大流。 这也就是说。若网络中的流量已达到最大值则在该网络中不可能再找出增流链。对 给定的流∫，我们构造 个点的集合，定义 1.sEVi: 2.若，∈和f<则巴∈：若∈和fm>0,则∈. 根据的定义，可以证明t∈了1.否则，将有一条从s到t的增流链，此链的全部前 向边(，+)满足 f（,+1)<c(,+1 而其全部后向边(+1，)满足： f1+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 < cij , ✃ vj ∈ V1; ❂ vi ∈ V1 ➇ fji > 0, ✃ vj ∈ V1 ✜ ❾✁❿ V1 ✍✖➍✁☛, ✓✖✔✁➵✑➸ t ∈ V 1 ✜✵➺✃, ❤✖❪✖✳➷❃ s Ð t ✍✁➒✖✛✁➓, ✶✁➓✖✍✁✇✁⑩➉ ➥s (vi , vi+1) ✷✁✸: f(vi , vi+1) < c(vi , vi+1). ✷✖❵✁✇✁⑩✁↔❲➥s (vi+1, vi) ✷✁✸: f(vi+1, vi) > 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.若在边(，)上，<c4,则给标记(，(》.这里1()=min[(),- f.这时顶点马成为已标记而未检查的点. 2.若在边(e,)上，：>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 < ci,j , ✃➵ vj ➐☞➑ (+vi , l(vj ))✜ ❻❺ l(vj ) = min{l(vi), ci,j − fi,j}✜ ❻➘✖q✖r vj þ✖✘✑➯✚➐✖➑✖✷✁ò✁ï✁ð✖✍✖r✖✜ 2. ❂ ⑩✖s (vj , vi) ✮,fj,i > 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=4<c13=9,给标记为(+1，()》，其中， 1()-minl(,(c3-fi.3)}=min{25}-2. (⑤).检在，在边(4，)上f3=1>0,故给标记为(-，(》，其中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 < c1,3 = 9, ❞ v3 ✬✣✭✣♦ (+v1, l(v3)), ✤✯♣, l(v3) = min{l(v1),(c1,3 − f1,3)} = min{2, 5} = 2✺ (5). ❣✁❤ v3, ⑦❆ (v4, v3) ❢ ,f4,3 = 1 > 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