ネットワーク G=(V,E) 、最大フロー f 、および E のエッジ e が与えられた場合、e を含む最小カットがあるかどうかを検出するために、efficeint アルゴリズムを見つける必要があります。別の質問は、e がいくつかの最小カットに含まれていることがわかった場合、それがカット全体の最も軽いエッジであるかどうかを検出することは可能ですか?
Ford-Fulkerson アルゴリズムを実行し、指定されたエッジの容量を増減して何が起こるかを確認することを考えましたが、問題の解決に役立つ可能性のあるものは思いつきませんでした。
誰かが私に解決策を教えてくれたらうれしいです。よろしくお願いします。