最大フロー最小カット定理
このネットワーク Ν のカット (S, T) とは、ノード(頂点)V を2つの集合 S {\displaystyle S} と T {\displaystyle T} に分割し、 S {\displaystyle S} には s {\displaystyle s} が含まれ、 T {\displaystyle T} には t {\displaystyle t} が含まれるようにすることをいう。
s と t 以外は自由にどちらかの集合に属することができるので、可能なカットの種類は
2 | V | − 2 {\displaystyle 2^{|V|-2}\,}
個ある。
カット ( S , T ) {\displaystyle (S,T)} の容量 c(S, T) とは、S と T の境界となっているエッジのうち、 S {\displaystyle S} から T {\displaystyle T} に向かっているものの容量の合計である。
c ( S , T ) = ∑ u ∈ S , v ∈ T a n d ( u , v ) ∈ E c ( u , v ) {\displaystyle c(S,T)=\sum _{u\in S,v\in T\mathrm {and} (u,v)\in E}c(u,v)}
フローでは流量が保存することから、あるフローが与えられている時、S と T の境界となっているエッジで、S から T へ流れる量から、T から S へ流れる量を引くと、フローの流量と等しくなる。