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

建模

二、最大流与最小割最大流问题是一类应用极为广泛的问题， 例如在交通运输网络中 有人流、车流、货物流，供水网络中有水流，金融系统中有现金流， 通讯系统中有信息流，等等。 定义 5 设 N = (V , E , c , s , t ) 是一个网络， f 是一个流，若不存在 流 f ,使'

Val f ' > Val f则称 f 为 N 的最大流。 定义 6 若 A V , s ∈ A, t ∈ A = V A , 则称 N 中弧的集合 ( A, A) 是网络 N 的一个割 cut) 记作 K , C ( A, A) = 割 cut) ( , 称 的容量 容量。 容量 设 K 是一个割， 若不存在割 K , 使得 C ( K ) < C ( K ) , 则称 K 是' '( i , j )∈ A i∈S , j∈S

∑

uij 为割 ( A, A)

N 的最小割。 最小割。 最小割注 4:割是从 A 到 A 的有向弧组成的

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