第十章网络的流 网络模型的很多问题可以归结为网络流问题。第九章中介绍的最短路问题，本质上也 是网络流问题，属于网络流问题的一类特殊问题。而多数网络流向题又是线性规划的特殊 类型.都可以建立对应的线性规划或整数规划摸型。那么为什么要用网络流的方法代替线 性规划，不用线性规划的一般求解方法，而要另外建立一些算法呢？由于实际问题中抽象 出来的网络流模型是一类具有特殊结构的问题，利用其特性常常可以研究、寻求一些较单 纯形法更为有效的方法去求解，又由于网络模型的直观性常常可以通过顶点一边的关系 代数学模型来措述一个实际问题，更易于接受.网络流题是图论的重要方面，在广泛 的领域里具有重要的应用。 这一章我们以运输网络为例，介绍网络的流及其它有关问题。主要内容是：流和割的 概念。最大流最小制定理，确定最大流的标记法，最小费用流以及最小费用最大流的网络 模型。 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