息流…等。五十年代,Ford(福特)、 Fulkerson(富克逊)建立的“网络流理 论”,是网络应用的重要组成部分 、网络与流的概念 对于有向图D=(V,A),如果V中有一发点v(亦称源还有一收点(亦 称为汇)记为v其余均为中间点,且对A中的每条弧均有权W(v,v)≥20(简 记为W,并称为弧容量),则称这样的赋权有向图D为容量网络,记为 D=(V,A,wW)。通过D中弧(vv)的物流量f,称为弧(v,v)的流量。所有弧上 流量的集合f={f}称为该网络D的一个流。 在图13中,弧旁括号中的两个数字(Wfi),第1个数字表示弧容量, 第二个数字表示通过该弧的流量。弧(vs,V)上的(8,6),前者是弧容量,表示 可通过该弧最大流量的能力为8,后者是目前通过该弧的实际流量为6。 (8 10,5 (6,1) (4,2) (,2) (73) (54) (图13) 从图13中可见:(1)通过每弧的流量均不超过弧容量(2)发点v 流出的总量为6+3=9,等于流入收点v的总量5+4=0;(3)各中间点的流出 量等于其流入量。各中间点v2的流出量减去其流入量等于0,即4-(3+1)=0 一般地,在容量网络D=(VA,W)中,满足以下条件的流f,称为可行 (1)弧流量限制条件0fi≤c (v,v)∈A (2)平衡条件 v(/)当 ∑f-∑fn 式中v()为该可行流的流量,即发点的净输出量,或收点的净输入量。 对于网络的流,可行流总是在存在的。如f={0}。34 息流……等。五十年代，Ford(福特)、Fulkerson(富克逊)建立的“网络流理 论”，是网络应用的重要组成部分。 一、网络与流的概念 对于有向图 D=(V,A)，如果 V 中有一发点 vs（亦称源还有一收点（亦 称为汇）记为 vt 其余均为中间点，且对 A 中的每条弧均有权 W(vi,vj)0（简 记为 Wij，并称为弧容量），则称这样的赋权有向图 D 为容量网络，记为 D=(V,A,W)。通过 D 中弧(vi,vj)的物流量 fij，称为弧(vi,vj)的流量。所有弧上 流量的集合 f={fij}称为该网络 D 的一个流。 在图 13 中，弧旁括号中的两个数字(Wij,fij)，第 1 个数字表示弧容量， 第二个数字表示通过该弧的流量。弧(vs,v1)上的(8,6)，前者是弧容量，表示 可通过该弧最大流量的能力为 8，后者是目前通过该弧的实际流量为 6。 v1 v4 v2 v3 （图 13） 从图 13 中可见：（1）通过每弧的流量均不超过弧容量（2）发点 vs 流出的总量为 6+3=9,等于流入收点 vt 的总量 5+4=0；（3）各中间点的流出 量等于其流入量。各中间点 v2 的流出量减去其流入量等于 0,即 4－(3+1)=0 一般地，在容量网络 D=(V,A,W)中，满足以下条件的流 f，称为可行 流： （1）弧流量限制条件 0fijcij (vi,vj)A （2）平衡条件        − =  = − = i j ij ji v f i t O i s t v f i s f f 当 当 当 ( ) , ( ) 式中 v(f)为该可行流的流量，即发点的净输出量，或收点的净输入量。 对于网络的流，可行流总是在存在的。如 f={0}。       vt vs (10,5) (3,3) (8,6) (6,1) (6,2) (4,2) (5,4) (7,3) (5,4)