1 最大流问题的数学描述! O8 y! ^! Q O- V0 ^+ y/ P
1.1 网络中的流 定义 2 d" o- j: Q& K+ J3 b0 w在以V 为节点集, A 为弧集的有向图G = (V, A) 上定义如下的权函数: # I' N) B2 l9 c! U6 h4 A/ }% S $ F2 v- ]+ _1 P. w% x4 m(i) L : A → R 为孤上的权函数,弧 (i, j)∈ A 对应的权 L(i, j) 记为 ,称为孤 (i, j) 的容量下界(lower bound);$ c+ ^- G+ l. `5 g
; I# r8 y& V( H+ V(ii)U : A → R 为弧上的权函数,弧(i, j)∈ A对应的权U(i, j) 记为 ,称为孤 (i, j) 的容量上界或容量(capacity); ]" C' r f7 \ ^* J
* K4 `- x, p- H( ~4 t) N6 e
(iii) D :V → R 为顶点上的权函数,节点i ∈V 对应的权 D(i) 记为 ,称为顶 点i 的供需量(supply/demand);1 J( q I, _4 [- O m2 J
/ }- p) ~+ L! G0 W' t
此时所构成的网络称为流网络,可以记为 N = (V, A, L,U,D) 。 由于我们只讨论V, A 为有限集合的情况,所以对于弧上的权函数 L,U 和顶点上的 权函数 D ,可以直接用所有孤上对应的权和顶点上的权组成的有限维向量表示,因此 L,U, D 有时直接称为权向量,或简称权。由于给定有向图G = (V, A) 后,我们总是可 以在它的弧集合和顶点集合上定义各种权函数,所以流网络一般也直接简称为网络。" ~- e* t! q3 U5 V- I) G7 ]
( x8 s$ s! A; x1 x+ }0 O; g在流网络中,弧(i, j) 的容量下界 和容量上界表示的物理意义分别是:通过该 弧发送某种“物质”时,必须发送的最小数量为 ,而发送的最大数量为 。顶点i ∈V 对应的供需量则表示该顶点从网络外部获得的“物质”数量( > 0时),或从该顶 点发送到网络外部的“物质”数量(< 0 时)。下面我们给出严格定义。6 T, e7 W+ W2 W( R7 X0 Z% {3 c
+ Z! Q4 e( p1 ?- m* f
可行流(feasible flow)3 g1 H7 D8 d m3 [ U5 G7 K* X) M5 X$ N
/ b- z9 I, D' h, p
9 F+ h& v6 j# X3 s
0 D1 A! K1 X1 h
- N( j+ P$ }, X; N2 j; P
可见,当 di > 0时,表示有di 个单位的流量从网络外部流入该顶点,因此顶点i 称 为供应点(supply node)或源(source),有时也形象地称为起始点或发点等;当di < 0 时,表示有|di | 个单位的流量从该顶点流失到网络外部(或说被该顶点吸收),因此顶 点i 称为需求点(demand node)或汇(sink),有时也形象地称为终止点或收点等;当 di = 0时,顶点i 称为转运点(transshipment node)或平衡点、中间点等。此外,根据 (1)可知,对于可行网络,必有 5 ?; M4 N% N5 j+ a) \" v( J( N" q8 W; p6 h3 h6 @
' [# Q) d/ M. [7 `8 f * M! S2 _: U# w7 F( \也就是说,所有节点上的供需量之和为 0 是网络中存在可行流的必要条件8 W! Y& [% s8 q2 V2 D- N1 ?( W2 L
, |1 g9 v6 Z2 q; g6 C; F7 I; ?# I - y2 y; M% X$ d( u, J" G 9 x z+ H. T% L! Y+ h/ o$ c+ B4 D6 _
1.2 最大流问题 6 Z! y& p' I4 P6 q! e3 P8 b0 Y考虑如下流网络 N = (V, A,U,D):节点 s 为网络中唯一的源点,t 为唯一的汇点, 而其它节点为转运点。如果网络中存在可行流 f ,此时称流 f 的流量(或流值,flow value)为 (根据(3),它自然也等于 − ),通常记为v 或v( f ) ,即$ j5 S: x2 p7 d
1 @6 F# `% S. v , ~) A, d6 k6 G* D- `2 ?: ~对这种单源单汇的网络,如果我们并不给定 和 (即流量不给定),则网络一 般记为 N = (s,t,V, A,U) 。最大流问题( maximum flow problem )就是在 N = (s,t,V, A,U) 中找到流值最大的可行流(即最大流)。我们将会看到,最大流问题 的许多算法也可以用来求解流量给定的网络中的可行流。也就是说,当我们解决了最大 流问题以后,对于在流量给定的网络中寻找可行流的问题,通常也就可以解决了。 % u1 c% X1 }9 k. K* }+ o+ B) i% o& v
用线性规划描述最大流问题4 l3 c0 I$ Z) a. Q% Y, h
因此,用线性规划的方法,最大流问题可以形式地描述如下:2 Z2 e/ r( Z8 I' ?
, p o9 p0 h0 o
1 c- o* n2 n0 F: P3 W5 u. G2 D' n2 d: I; x
定义】 如果一个矩阵 A 的任何子方阵的行列式的值都等于0,1或 −1,则称 A 是 全幺模的(totally unimodular TU,又译为全单位模的),或称 A 是全幺模矩阵。& c$ v0 q* K# `7 \9 V, C
1 v+ x. J, j8 o- f7 ~整流定理) K) u! C5 c7 r+ a5 O! {! g4 A y
【定理 7】(整流定理) 最大流问题所对应的约束矩阵是全幺模矩阵。若所有弧容量 均为正整数,则问题的最优解为整数解。 最大流问题是一个特殊的线性规划问题。我们将会看到利用图的特点,解决这个问 题的方法较之线性规划的一般方法要方便、直观得多。 / x* t9 [5 I, I9 ?5 j* h. E( z+ O8 v9 x I9 G
1.3 单源和单汇运输网络 " ^; ?8 e7 H9 n: Y* i多源多汇网络 转化成单源单汇网络 : M2 l, ~! }6 ~% Q. w8 T实际问题往往是多源多汇网络,为了计算的规格化,可将多源多汇网络G 化成单 源单汇网络G' 。设 X 是G 的源,Y 是G 的汇,具体转化方法如下: 9 j1 U/ N8 r, o! r2 z3 b- w$ `/ T1 @9 M+ ^
(i)在原图G 中增加两个新的顶点 x 和 y ,令为新图G' 中之单源和单汇,则G 中 所有顶点V 成为G' 之中间顶点集。3 U' G( t/ V6 d' b" o9 {' k# i. a, q) E
& m7 {/ d5 ~ P7 j(ii)用一条容量为∞的弧把 x 连接到 X 中的每个顶点。 a2 P7 U. o: {! v% E2 Y& o3 V, r) ~4 t2 f; V0 e, ]
(iii)用一条容量为∞的弧把Y 中的每个顶点连接到 y 。 G 和G' 中的流以一个简单的方式相互对应。若 f 是G 中的流,则由4 b+ p5 _$ D k+ I/ V: z
2 Q$ U# b7 s; W: L& ^