最小s-tカットからの最大流量の計算

Question

残余グラフのソースからのBFSを使用すると、最大フローfを仮定すると、最小容量のs-tカットを得るのは簡単です。最小容量のs-tを与えた場合、最大フローfを得るアルゴリズムはありますか？

Answer 1

いいえ、基本的には、問題は、一般的に最小限のカットではほとんど分からないということです。与えられたネットワークでは、シンクから新しいアークを新しい頂点に付け加えて新しいネットワークを形成します。新しい頂点は新しいシンクになり、古いmaxフローと同じ容量になります。今では、最小カットはちょうどその弧であり、残りのネットワークに関する情報はありません。