DAA - Penutup Vertex

Penutup simpul dari grafik yang tidak berarah G = (V, E) adalah bagian dari simpul V' ⊆ V sehingga jika tepi (u, v) adalah tepi G, lalu salah satunya u di V atau v di V' atau keduanya.

Temukan penutup-puncak dengan ukuran maksimum dalam grafik yang tidak berarah. Vertexcover yang optimal ini adalah versi pengoptimalan dari masalah NP-complete. Namun demikian, tidak terlalu sulit untuk menemukan penutup-simpul yang mendekati optimal.

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

Contoh

Himpunan tepi dari grafik yang diberikan adalah -

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

Sekarang, kita mulai dengan memilih tepi arbitrer (1,6). Kami menghilangkan semua tepi, yang bersisian dengan simpul 1 atau 6 dan kami menambahkan tepi (1,6) untuk menutupi.

Pada langkah berikutnya, kami telah memilih sisi lain (2,3) secara acak

Sekarang kami memilih tepi lain (4,7).

Kami memilih tepi lain (8,5).

Oleh karena itu, penutup puncak grafik ini adalah {1,2,4,5}.

Analisis

Sangat mudah untuk melihat bahwa waktu berjalan dari algoritma ini adalah O(V + E), menggunakan daftar kedekatan untuk mewakili E'.