; ~; B7 G3 H" {. c) I j7 H(iii) D :V → R 为顶点上的权函数,节点i ∈V 对应的权 D(i) 记为 ,称为顶 点i 的供需量(supply/demand); / I' z9 `2 T5 H3 r2 E9 c; I- X, {0 m( I4 a, \
此时所构成的网络称为流网络,可以记为 N = (V, A, L,U,D) 。 由于我们只讨论V, A 为有限集合的情况,所以对于弧上的权函数 L,U 和顶点上的 权函数 D ,可以直接用所有孤上对应的权和顶点上的权组成的有限维向量表示,因此 L,U, D 有时直接称为权向量,或简称权。由于给定有向图G = (V, A) 后,我们总是可 以在它的弧集合和顶点集合上定义各种权函数,所以流网络一般也直接简称为网络。 7 N8 Z; Q: a* I * b8 y3 B! L4 p$ _; Y6 ]& ?在流网络中,弧(i, j) 的容量下界 和容量上界表示的物理意义分别是:通过该 弧发送某种“物质”时,必须发送的最小数量为 ,而发送的最大数量为 。顶点i ∈V 对应的供需量则表示该顶点从网络外部获得的“物质”数量( > 0时),或从该顶 点发送到网络外部的“物质”数量(< 0 时)。下面我们给出严格定义。 5 p! g% L0 [; t7 G( n 8 f& y/ u6 I$ O; c! a( q% s可行流(feasible flow) 0 G) n% m* q6 _. H+ A / b: y5 N8 y& x; f2 H* b& h: k ) i2 M" Q/ o _1 Y+ j, q% j+ Q% W0 T
2 }; L* V* a4 L9 U3 W$ U; b& A
可见,当 di > 0时,表示有di 个单位的流量从网络外部流入该顶点,因此顶点i 称 为供应点(supply node)或源(source),有时也形象地称为起始点或发点等;当di < 0 时,表示有|di | 个单位的流量从该顶点流失到网络外部(或说被该顶点吸收),因此顶 点i 称为需求点(demand node)或汇(sink),有时也形象地称为终止点或收点等;当 di = 0时,顶点i 称为转运点(transshipment node)或平衡点、中间点等。此外,根据 (1)可知,对于可行网络,必有 5 ?% |" }7 _5 P$ _1 H1 }6 O9 ^. l9 q+ L) i; U4 X- m 7 c& G7 ]9 Q2 m ( \: s& v+ a* R% ~# V! X: c也就是说,所有节点上的供需量之和为 0 是网络中存在可行流的必要条件 ! T- D. ~& w9 ] . e. r6 m9 i7 e; c4 d : r, C( P% o. d$ Y1 b8 v" r& f, _5 U% f* V8 Z: X& i0 i
; V' H, q" \# y' B
1.2 最大流问题4 Y* b2 E6 \5 I, [' \9 M
考虑如下流网络 N = (V, A,U,D):节点 s 为网络中唯一的源点,t 为唯一的汇点, 而其它节点为转运点。如果网络中存在可行流 f ,此时称流 f 的流量(或流值,flow value)为 (根据(3),它自然也等于 − ),通常记为v 或v( f ) ,即1 c) j+ t! K$ K: U3 s3 H
1 d/ U6 N1 i2 \! f; n ( C# C: ?9 y9 r( f, Y对这种单源单汇的网络,如果我们并不给定 和 (即流量不给定),则网络一 般记为 N = (s,t,V, A,U) 。最大流问题( maximum flow problem )就是在 N = (s,t,V, A,U) 中找到流值最大的可行流(即最大流)。我们将会看到,最大流问题 的许多算法也可以用来求解流量给定的网络中的可行流。也就是说,当我们解决了最大 流问题以后,对于在流量给定的网络中寻找可行流的问题,通常也就可以解决了。9 Y9 Z) r0 L1 ~- V& E' l
2 p; K1 f9 @& N* z
用线性规划描述最大流问题8 F% e* b m' x) ?4 ]! \
因此,用线性规划的方法,最大流问题可以形式地描述如下: / N, z, W8 [2 ~# C; l ! O+ q$ m/ Y' e5 j9 Z0 \/ N6 T. e. m. Y; T
9 v- j" A# Y5 S1 T+ d0 k8 C. U
定义】 如果一个矩阵 A 的任何子方阵的行列式的值都等于0,1或 −1,则称 A 是 全幺模的(totally unimodular TU,又译为全单位模的),或称 A 是全幺模矩阵。 2 y3 ?, f$ m7 a1 m' ?) S6 |* N8 R! y4 t3 i
整流定理( ?! }" B6 N( _$ q
【定理 7】(整流定理) 最大流问题所对应的约束矩阵是全幺模矩阵。若所有弧容量 均为正整数,则问题的最优解为整数解。 最大流问题是一个特殊的线性规划问题。我们将会看到利用图的特点,解决这个问 题的方法较之线性规划的一般方法要方便、直观得多。8 a( M1 t- U7 y, }7 d D) a$ f
" U) U: V6 @) ]6 Q6 f
1.3 单源和单汇运输网络 " h# l5 P8 c& h2 e9 @多源多汇网络 转化成单源单汇网络 4 h3 e3 G& e/ p4 q. {7 F实际问题往往是多源多汇网络,为了计算的规格化,可将多源多汇网络G 化成单 源单汇网络G' 。设 X 是G 的源,Y 是G 的汇,具体转化方法如下:* X8 g* T8 j0 I3 W
9 G0 u. P" H- A* T+ @% }
(i)在原图G 中增加两个新的顶点 x 和 y ,令为新图G' 中之单源和单汇,则G 中 所有顶点V 成为G' 之中间顶点集。. H) f$ _* g1 J: E" u1 b
. a# v$ z' i4 g, ~5 E4 u(ii)用一条容量为∞的弧把 x 连接到 X 中的每个顶点。; B `4 Q% Z+ [2 ]4 Z% A" Q+ F
w: D i0 W+ q7 U& G(iii)用一条容量为∞的弧把Y 中的每个顶点连接到 y 。 G 和G' 中的流以一个简单的方式相互对应。若 f 是G 中的流,则由 1 w5 r3 Y( ]+ n l5 X# A5 N, d! ?! L9 J; f N# n6 K' q. S1 P * a: _1 p/ c( d
& i# c. f6 ?1 K' K- f( ~. ` 2 最大流和最小割关系割的容量, M/ p- r$ K: j, p1 l: x& L
1 W: @5 D% {8 J4 b & B2 @3 w5 {8 a1 `6 v5 }1 m* R, |6 m) [% ~3 a6 y& L8 Z8 s+ a- z
则在这条可增广轨上每条前向弧的流都可以增加一个量δ ,而相应的后向弧的流可减 少δ ,这样就可使得网络的流量获得增加,同时可以使每条弧的流量不超过它的容量, 而且保持为正,也不影响其它弧的流量。总之,网络中 f 可增广轨的存在是有意义的, 因为这意味着 f 不是最大流。 0 u6 J6 {. _. I1 |& u5 H* M5 ?$ O7 l% h+ j5 X
3 最大流的一种算法—标号法 + [+ ]# O2 d8 ^# a% B0 F1 ^标号法是由 Ford 和 Fulkerson 在 1957 年提出的。用标号法寻求网络中最大流的基 本思想是寻找可增广轨,使网络的流量得到增加,直到最大为止。即首先给出一个初始 流,这样的流是存在的,例如零流。如果存在关于它的可增广轨,那么调整该轨上每条 弧上的流量,就可以得到新的流。对于新的流,如果仍存在可增广轨,则用同样的方法 使流的值增大,继续这个过程,直到网络中不存在关于新得到流的可增广轨为止,则该 流就是所求的最大流。0 `+ o1 u. }0 ~3 f
/ U5 J: V4 p$ h; R# O
这种方法分为以下两个过程:- h/ f+ z0 X& K& ~0 \! {. }" q7 g