DAA-頂点カバー

無向グラフ G =（V、E） の頂点カバーは、頂点 V ^ '^⊆V のサブセットであるため、エッジ （u、v） が* G_のエッジである場合*、次に '_V の u または V ^ '^ _ の _v' 、あるいはその両方。

特定の無向グラフで最大サイズの頂点カバーを見つけます。この最適な頂点カバーは、NP完全問題の最適化バージョンです。ただし、最適に近い頂点カバーを見つけることはそれほど難しくありません。

APPROX-VERTEX_COVER (G: Graph) c ← { } E' ← E[G]
while E' is not empty do
   Let (u, v) be an arbitrary edge of E' c ← c U {u, v}
   Remove from E' every edge incident on either u or v
return c

例

与えられたグラフのエッジのセットは-

*\ {（1,6）、（1,2）、（1,4）、（2,3）、（2,4）、（6,7）、（4,7）、（7,8） 、（3,8）、（3,5）、（8,5）}*

エッジの設定

ここで、任意のエッジ（1,6）を選択することから始めます。頂点1または6に付随するすべてのエッジを削除し、カバーにエッジ（1,6）を追加します。

任意のエッジ

次のステップでは、ランダムに別のエッジ（2,3）を選択しました

Another Edge

次に、別のエッジ（4,7）を選択します。

別のエッジを選択

別のエッジ（8,5）を選択します。

エッジ

したがって、このグラフの頂点カバーは\ {1,2,4,5}です。

分析

このアルゴリズムの実行時間は O（V + E） であり、隣接リストを使用して _E ^ '^ _ を表すことは簡単にわかります。

Design-and-analysis-of-algorithms-vertex-cover

DAA-頂点カバー

例

分析