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 :