問題は、加重エッジ双方向グラフが与えられた場合、特定のノードのセットが互いに切断されるノードを削除することにより、エッジのセットを見つけることです。また、これらのエッジの重みの合計も最小にする必要があります。この問題に名前はありますか? それらを解決するための特定のアルゴリズムはありますか? これが NP 完全問題に違いないことはわかっています。
質問する
827 次
1 に答える
2
グラフを2つの部分に分割する最小のウェイトカットを見つけたい場合は、最大フロー/最小カットアルゴリズム（エドモンズアルゴリズムなど）を実行するだけでこれを実行できます。1つの頂点を修正してから、他のすべての| V | -1頂点でその最小カットを見つけ、最後にすべてのカットの中で最小カットを出力する必要があります。固定頂点はコンポーネントの1つにある必要があることに注意してください。無向グラフで最大フロー/最小カットアルゴリズムを実行するには、各エッジを2方向に描画するだけです。このアルゴリズムにより、最大フローアルゴリズム* O（| V |）が実行されます。
しかし、問題がグラフを最小の重みカットでk連結成分に分割する方法である場合、これはNP困難な問題です。
于 2012-04-26T22:19:50.553 に答える