DAA - Vertex Cover

Eine Scheitelpunktabdeckung eines ungerichteten Graphen G = (V, E) ist eine Teilmenge von Eckpunkten V' ⊆ V so dass, wenn Kante (u, v) ist eine Kante von Gdann auch nicht u im V oder v im V' oder beides.

Suchen Sie in einem bestimmten ungerichteten Diagramm eine Scheitelpunktabdeckung mit maximaler Größe. Diese optimale Scheitelpunktabdeckung ist die Optimierungsversion eines NP-vollständigen Problems. Es ist jedoch nicht allzu schwer, eine nahezu optimale Scheitelpunktabdeckung zu finden.

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

Beispiel

Die Kantenmenge des angegebenen Diagramms ist -

{(1,6),(1,2),(1,4),(2,3),(2,4),(6,7),(4,7),(7,8),(3,8),(3,5),(8,5)}

Nun wählen wir zunächst eine beliebige Kante (1,6) aus. Wir eliminieren alle Kanten, die entweder auf Scheitelpunkt 1 oder 6 fallen, und fügen der Abdeckung eine Kante (1,6) hinzu.

Im nächsten Schritt haben wir zufällig eine andere Kante (2,3) ausgewählt

Nun wählen wir eine andere Kante (4,7).

Wir wählen eine andere Kante (8,5).

Daher ist die Scheitelpunktabdeckung dieses Graphen {1,2,4,5}.

Analyse

Es ist leicht zu erkennen, dass die Laufzeit dieses Algorithmus ist O(V + E), unter Verwendung der Adjazenzliste zur Darstellung E'.