最小重みのエッジを削除してノードの集合を切断する

Question

問題は、与えられた重み付けされたエッジの双方向グラフでは、与えられたノードの集合が互いに切断されるようにすることによってエッジの集合を見つける。また、これらの辺の重みの合計も最小にする必要があります。この問題には名前がありますか？特定のアルゴリズムをそれらを解決するには？私はこれがNPの完全な問題でなければならないことを知っています。

Answer 1

グラフを2つの部分に分ける最小の重量カットを探したい場合は、max flow/min cutアルゴリズム（たとえばEdmondsアルゴリズム）を実行するだけで簡単に行うことができます。 1つの頂点を修正し、他のすべての| V | -1頂点でその最小カットを見つけ、最終的にすべてのカット間に最小カットを配置するだけです。固定頂点は、コンポーネントの1つにある必要があります。無向グラフ上でmax-flow/min cutアルゴリズムを実行すると、各エッジを2方向に描画するだけです。このアルゴリズムは、max-flowアルゴリズム* O（| V |）を実行させます。

しかし、あなたの問題がグラフを最小の重量削減でk連結成分に分割する方法であるなら、これはNP困難な問題です。