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