ST分は、私は、次のネットワークフロー問題の証拠を見つけようとしている交差点

Question

をカットまた、セントのmincutです。 sの最小数の頂点でs-t min cutを見つけるアルゴリズムを作成します。

私はカットから何とかすべてのエッジをチェックする必要があることを理解していますが、それをより効果的に行う方法はありますか？アルゴリズムに関しては、すべての最小カットの交差を見つけることが望ましいと思うが、すべての最小カットを見つける方法を理解することはできない（1つは問題なし）

私は非常にうれしいそれを手伝ってください。

ありがとうございます。

Answer 1

明らかに宿題なので、ここにヒントがあります。最小フローを仮定すると、残余ネットワークに対するその容量がゼロである場合に限り、s-t cutは最小であることを証明する。ゼロ容量カットについての良い点は、出力アークの容量がすべてゼロであることです。これはグローバルアークではなくローカルプロパティです。ここから、交差点プロパティの証明はカップルラインであり、アルゴリズムは簡単です（「すべて」s-t min cutを計算しません）。