第2讲 最大流与最小费用流(8)

建模

注 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

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库第2讲 最大流与最小费用流(8)在线全文阅读。