重み付けされた連結グラフが与えられたとします。グラフから削除できるエッジのリストを見つけて、グラフを 2 つのコンポーネントに分割し、削除されたエッジの重みの合計が小さくなるようにしたいと考えています。理想的には、最小の合計を取得したいのですが、妥当な概算で解決します。
これは難しい問題のようです。これを行うための適切なアルゴリズムはありますか?
それが役立つ場合、私の場合、ノードの数は約 50 であり、グラフは密集している可能性があるため、ほとんどのノードのペアはそれらの間にエッジがあります。
最小カットアルゴリズムを探していると思います。ウィキペディア
Edmunds-Karp アルゴリズムが登場する前に、Ford-Fulkerson アルゴリズムが登場しました。アルゴリズムの本 [Cormen, Rivest] では、グラフ理論の章でこれら 2 つのアルゴリズムが引用されています。
あなたが探しているのは、最小カットを計算するためのアルゴリズムだと思います。Edmonds-Karp アルゴリズムは、フロー ネットワークに対してこれを行います (ソース頂点とシンク頂点を使用)。Hao と Orlin (1994)は、これを有向加重グラフに一般化しています。彼らのアルゴリズムは、 n個の頂点とm個のエッジに対してO( nm lg( n ^2/ m )) で実行されます。チェクリら。(1997)いくつかのアルゴリズムを経験的に比較し、そのうちのいくつかは Hao や Orlin よりも大きな O の方が優れています。