建模
二、最大流与最小割最大流问题是一类应用极为广泛的问题， 例如在交通运输网络中 有人流、车流、货物流，供水网络中有水流，金融系统中有现金流， 通讯系统中有信息流，等等。 定义 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 的有向弧组成的