切断された二部無向グラフがあります。グラフを完全に切り離したい。私が実行できる唯一の操作は、ノードの削除です。ノードを削除すると、そのエッジが自動的に削除されます。タスクは、削除するノードの数を最小限に抑えることです。グラフの各ノードには最大 4 つのエッジがあります。
グラフを完全に切り離すということは、リンクを介して 2 つのノードを接続してはならないということです。基本的に空のエッジ セットです。
質問する
1843 次
4 に答える
7
実際、アルゴリズムが最適ではないため、アルゴリズムが最適であることを証明することはできないと思います。
削除するノードの数を最小限に抑えてグラフを完全に切断するには、グラフの最小頂点被覆に属するすべてのノードを削除する必要があります。最小頂点被覆の検索は通常NP完全ですが、2部グラフの場合は多項式時間の解があります。
グラフで最大の一致を見つけます（おそらくホップクロフト-カープアルゴリズムを使用）。次に、ケーニヒの定理を使用して、最小頂点被覆を取得します。
頂点が左（L）と右（R）のセットに分割されている2部グラフについて考えてみます。エッジをマッチングで使用されるエッジ（E_m）と使用されないエッジ（E_0）に分割する最大マッチングがあるとします。Tを、Lからの一致しないすべての頂点と、E_0からのエッジに沿って左から右に、E_mからのエッジに沿って右から左に移動することによって到達可能なすべての頂点で構成します。これは基本的に、Lの一致しない頂点ごとに、E_0とE_mのエッジ間で交互に発生するパスで発生するすべての頂点をTに追加することを意味します。
その場合、（L \ T）OR（R AND T）は最小頂点被覆です。
于 2012-08-06T20:21:32.147 に答える
3
提案されたアルゴリズムの反例を次に示します。
最善の解決策は、ノード A と B の両方を削除することです。これらの色は異なります。
于 2012-08-06T20:35:03.030 に答える
0
すべてのエッジは 1 つのセットから別のセットにあるため、たとえば BFS を使用してこれら 2 つのセットを見つけ、2 色を使用して色付けします。次に、小さいセットのノードを削除します。
それらの間にエッジがないため、残りのノードも同様に切断されます。
[前処理ステップとして、最初にエッジが 0 のノードを除外できます。]
于 2012-08-07T06:11:08.867 に答える
0
そのためのアルゴリズムを考えましたが、それが最適かどうかを証明することはできません。
私のアルゴリズム: 切断された各サブグラフで、BFS を実行し、それに応じて色を付けます。次に、各色で着色されたノードの数を特定し、2 つの最小値を取得して保存します。サブグラフごとに手順を繰り返し、合計して必要な最小値を取得します。アルゴリズムが正しいかどうかを証明するのを手伝ってください。
編集: 上記のアルゴリズムは最適ではありません。受け入れられた回答が正しいことが確認されました。
于 2012-08-06T19:46:32.690 に答える