DAA - Köşe Kapağı

Yönlendirilmemiş bir grafiğin tepe noktası G = (V, E) köşelerin bir alt kümesidir V^' ⊆ V öyle ki kenar (u, v) kenarı G, O zaman ya u içinde V veya v içinde V^' ya da her ikisi de.

Yönlendirilmemiş bir grafikte maksimum boyutta bir tepe noktası bulun. Bu optimal köşe kapağı, NP-complete probleminin optimizasyon versiyonudur. Bununla birlikte, optimuma yakın bir tepe noktası bulmak çok da zor değildir.

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

Misal

Verilen grafiğin kenar seti -

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

Şimdi keyfi bir kenar (1,6) seçerek başlıyoruz. Tepe 1 veya 6'ya denk gelen tüm kenarları ortadan kaldırıyoruz ve örtmek için kenar (1,6) ekliyoruz.

Bir sonraki adımda, rastgele başka bir kenar (2,3) seçtik

Şimdi başka bir kenar seçiyoruz (4,7).

Başka bir kenar (8,5) seçiyoruz.

Dolayısıyla, bu grafiğin tepe noktası {1,2,4,5} 'dir.

Analiz

Bu algoritmanın çalışma süresinin O(V + E), temsil etmek için bitişiklik listesi kullanma E^'.