Tutup verteks

Dari Wikipedia bahasa Indonesia, ensiklopedia bebas

Di dalam disiplin matematika tentang teori graf, tutup verteks (bahasa Inggris: vertex cover) adalah himpunan simpul (vertex) di mana 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[sunting | sunting sumber]

Vertex Cover didapat dari himpunan VC dari simpul (vertex) dalam suatu graf G=(E,V) di mana pada setiap busur (u,v) Є E pada graf G tersebut dapat dicakup oleh setidaknya satu simpul v Є VC.[1]

Dilihat dari definisi, vertex cover berbeda dengan edge cover.

Minimum Vertex Cover[sunting | sunting sumber]

Dalam kasus minimum vertex cover, permasalahan ini dapat dibuat sederhana. Di mana terdapat M jumlah minimum dari vertex cover.

Minimum Vertex Cover Pada Graf Khusus[sunting | sunting sumber]

Ada beberapa graf khusus yang dapat langsung diketahui berapa jumlah vertex cover-nya. Graf tersebut adalah graf star dan graf lengkap.

Graf Star[sunting | sunting sumber]

Simpul yang diwarnai dengan warna merah adalah minimum vertex cover dari graf star G = (E,V). Untuk graf star, minimum vertex cover-nya atau |VC| adalah 1. Simpul yang berwarna hitam disebut “anting”, di mana anting adalah suatu simpul v dengan d(v)=1, v Є V di mana (u,v) Є E.

Graf Lengkap[sunting | sunting sumber]

Minimum vertex cover untuk graph lengkap adalah |VC| = |v|-1.

Evaluasi Aproksimasi[sunting | sunting sumber]

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 daripada solusi aslinya. George Karakostas (Mc Master, 2004) [2] telah berhasil memperkecil nilai p yang dimaksud menjadi:

p=2-θ√(1/log n)

Algoritme Vertex Cover P-Aproksimasi[sunting | sunting sumber]

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


Algoritme tersebut memiliki kompleksitas waktu O(mn)

Claim Vertex Cover[sunting | sunting sumber]

Vertex Cover dapat diperoleh dari ILP, Himpunan Bebas, Maksimum Matching, Hamiltonian Cycle, Hamiltonian Path di mana setiap solusi dari permasalahan tersebut termasuk HARD PROBLEM.

Penerapan Vertex Cover di Dunia Nyata[sunting | sunting sumber]

Di dunia nyata, vertex cover berguna sebagai acuan untuk pemasangan kamera CCTV di suatu gedung agar pemasangan yang dilakukan menjadi efisien.

Referensi[sunting | sunting sumber]

  1. ^ Thomas H Cormen, harles E. Leiserson, Ronald L. Rivest, Clifford Stein, “Introduction to Algorithms”, The MIT Press, Cambridge Massachusetts [CLRS]
  2. ^ 2 Springerlink[pranala nonaktif permanen]