Tutup verteks
Di dalam disiplin matematika tentang teori graf, vertex cover adalah himpunan simpul (vertex) dimana di setiap busur (edge) setidaknya dicakup oleh satu simpul (vertex) dari himpunan. Permasalahan yang ditemukan adalah bagaimana mencari vertex cover yang jumlahnya minimum. Permasalahan ini termasuk permasalahan optimasi yang sulit (Hard Problem) dalam ilmu komputer.
Definisi
Vertex Cover didapat dari himpunan VC dari simpul (vertex) dalam suatu graf G=(E,V) dimana pada setiap busur (u,v) Є E pada graf G tersebut dapat dicakup oleh setidaknya satu simpul v Є VC. Sebagai contoh diberikan graf sebagai berikut :
Dari 2 gambar tersebut, vertex cover ditunjukkan oleh simpul (vertex) yang berwarna merah.
Minimum Vertex Cover
Dalam kasus minimum vertex cover, permasalahan ini dapat dibuat sederhana. Dimana terdapat M jumlah minimum dari vertex cover. Apabila diambil dari 2 gambar sebelumnya, minimum vertex cover yang terbentuk adalah :
Minimum Vertex Cover Pada Graf Khusus
Ada beberapa graf khusus yang dapat langsung diketahui berapa jumlah vertex covernya. Graf tersebut adalah :
Graf Star
Simpul yang diwarnai dengan warna merah adalah minimum vertex cover dari graf star G = (E,V). Untuk graf star minimum vertex covernya atau |VC| adalah 1. Simpul yang berwarna hitam disebut “anting”, dimana anting adalah suatu simpul v dengan d(v)=1, v Є V dimana (u,v) Є E.
Graf Lengkap
Minimum vertex cover untuk graph lengkap adalah |VC| = |v|-1.
Evaluasi Aproksimasi
Pencarian minimum vertex cover dapat ditempuh dengan cara p-aproksimasi, yang memiliki waktu eksekusi polinomial. Untuk permasalahan minimisasi, akan didapatkan solusi ≤ p kali lebih buruk dari pada solusi aslinya. George Karakostas (Mc Master, 2004) telah berhasil memperkecil nilai p yang dimaksud menjadi : p=2- θ√(1/log n )
Algoritma Vertex Cover P-Aproksimasi
G=(E,V) VC Aproksimasi (G) AVC = Φ E’ = E While E’ ≠ Φ Ambil secara bebas (u,v) Є E’ AVC = AVC ∪ {u,v} Hapus semua busur (x,u), (x,v) Є E’, x Є V Endwhile Return AVC Algoritma tersebut memiliki kompleksitas waktu O(mn)
Claim Vertex Cover
Vertex Cover dapat diperoleh dari ILP, Himpunan Bebas, Maksimum Matching, Hamiltonian Cycle, Hamiltonian Path dimana setiap solusi dari permasalahan tersebut termasuk HARD PROBLEM.
Penerapan Vertex Cover di Dunia Nyata
Di dunia nyata, vertex cover berguna sebagai acuan untuk pemasangan kamera CCTV di suatu gedung agar pemasangan yang dilakukan menjadi efisien.
Referensi
Thomas H Cormen, harles E. Leiserson, Ronald L. Rivest, Clifford Stein, “Introduction to Algorithms”, The MIT Press, Cambridge Massachusetts [CLRS]