Memahami Vertex Cover

vertex cover

Dalam disiplin matematika teori graf , Vertex Cover atau kadang kita sebut node cover dari graph adalah himpunan simpul sedemikian rupa sehingga masing-masing tepi graph berhadapan dengan setidaknya satu simpul dari himpunan.

Vertex Cover dari undirect graph G = (V, E) adalah himpunan bagian dari simpul  ⊆ V sehingga jika tepi (u, v) adalah tepi G , maka baik u di V atau v di  atau kedua.

menemukan Vertex Cover dengan ukuran maksimum dalam undirect graph yang diberikan. Vertex cover optimal ini adalah versi optimisasi dari masalah NP-complete. Namun, tidak terlalu sulit untuk menemukan vertex-cover 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 grafik yang diberikan adalah

Sekarang, mulai dengan memilih edge arbitrary (1,6).  Menghilangkan semua edge, yang merupakan kejadian pada simpul 1 atau 6 dan menambahkan edge (1,6) untuk menutupi.

Pada langkah berikutnya, memilih edge lain, misal (2,3) secara acak.

Kemudian pilih edge lain lagi (4,7).

Dan terakhir kita pilih edge lain (8,5).

Jadi, Vertex Cover dari graph contoh diatas adalah {1,2,4,5}.

Sangat mudah untuk melihat bahwa running time dari algoritma ini adalah O (V + E)

Leave a Reply

Your email address will not be published. Required fields are marked *

× Mau Merchandise? bisa, Chat WA yak