建模
注 3:任何一个多源多汇网络 N = (V , E , c, X , Y ) 都等价与一个 ： 单源单汇网络 N = (V , E , c , X , Y ) 。在解决实际问题时，常把多源 多汇网络转化为单源单汇网络。' ' ' ' ' '
(1) V = V ∪ {s, t} , s, t 分别是 N 的发点与收点；''
(2) E = E ∪ {( s, x) | x ∈ X } ∪ {( y, t ) | y ∈ Y } ;'
(3)c = c(e), e ∈ E ;c ( s, x) = ∞, x ∈ X ,c ( y, t ) = ∞, y ∈ Y 。 图 1 所示网络等价于图 2 所示的单源单汇网络。' ' '
x1
6,1 1,1 2,2 3,0
v14,01,0
5,1 1,0 2,1
y12,2
∞,2s
∞,4
v43,2
5,3
3,1
s 6,06,44,4
∞,0 ∞,6 t y2 ∞,0
x2
v3
图2
y3