graph - 強く接続されたグラフからエッジを削除する

Question

この問題には名前がありますか？

エッジの重みを持つ有向で強く接続されたグラフが与えられた場合、そのエッジのセットを削除すると、グラフが強く接続されなくなるように、最小のコストのエッジのセットを見つけます。

誰かが解決策のアイデアを知っている/持っていますか？これをネットワークフローの問題として設定しようと思っていますが、どうすればよいかわかりません。

Answer 1

トピックごとに最も近いものは「パーコレーション問題」と名付けられています。「パーコレーションしきい値」と「パーコレートされたグラフのパス」の側面について説明しています。それについての完全な理論があります。これで、ググるキーワードができました。

あなたの検索が、グラフ、パス、フラクタルの理論ではなく、いくつかの実用的なモデルによって引き起こされたことは興味深いことです。