フローの値とカットの容量
#グラフ理論
カットとフローの値
定理
$ N
をネットワークとする。このとき任意のフローを
$ f
と任意のカット
$ (S, S^c)
について、
$ \rm{val}(f) = cap((S, S^c))
系
フロー
$ f
とカット
$ (S, S^c)
に対して
$ \rm{val}(f) = cap((S, S^c))
が成立すれば、
$ f
は
最大流
であり、
$ (S,S^c)
は
最小カット
である。
定理の証明
系の証明