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'.