Tutup verteks: Perbedaan antara revisi

Konten dihapus Konten ditambahkan

Sebaris

Revisi terkini sejak 24 November 2022 13.07

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

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

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

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

Graf Star

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

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

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

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

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]
^ 2 Springerlink^{[pranala nonaktif permanen]}

[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]}

[1]

[2]

@@ Baris 1: / Baris 1: @@
-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]].
+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 ==
-''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 [1]. Dilihat dari definisi, ''vertex cover'' berbeda dengan ''[[edge cover]]''. Sebagai contoh diberikan graf sebagai berikut :
+''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.<ref>Thomas H Cormen, harles E. Leiserson, Ronald L. Rivest, Clifford Stein, “Introduction to Algorithms”, The MIT Press, Cambridge Massachusetts [CLRS]</ref>
+Dilihat dari definisi, ''vertex cover'' berbeda dengan ''[[edge cover]]''.<!--Sebagai contoh diberikan graf sebagai berikut:
-{| align="center"
+Dari 2 gambar tersebut, ''vertex cover'' ditunjukkan oleh simpul (''vertex'') yang berwarna merah.-->
-|-
-! [[Berkas:Graf 1.jpg|thumb|center|Contoh Graf (1)]]
-! [[Berkas:Graf 2.jpg|thumb|center|Contoh Graf (2)]]
-|}
-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 :
+Dalam kasus ''minimum vertex cover'', permasalahan ini dapat dibuat sederhana. Di mana terdapat M jumlah ''minimum'' dari ''vertex cover''.<!--Apabila diambil dari 2 gambar sebelumnya, ''minimum vertex cover'' yang terbentuk adalah:
+{| align="center"
-{|
 |-
 ! [[Berkas:Graf 1-1.jpg|thumb|center|Contoh Graf (1-1)]]
 ! [[Berkas:Graf 2-1.jpg|thumb|center|Contoh Graf (2-1)]]
-|}
+|}-->
 == ''Minimum Vertex Cover'' Pada Graf Khusus ==
-Ada beberapa graf khusus yang dapat langsung diketahui berapa jumlah ''vertex cover''-nya. Graf tersebut adalah :
+Ada beberapa graf khusus yang dapat langsung diketahui berapa jumlah ''vertex cover''-nya. Graf tersebut adalah graf star dan graf lengkap.
 === Graf Star ===
+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.
-{|
-|-
-! [[Berkas:Graf star 1.jpg|thumb|center|Contoh Graf (3)]]
-! [[Berkas:Graf star 2.jpg|thumb|center|Contoh Graf (4)]]
-|}
-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”, dimana anting adalah suatu simpul v dengan d(v)=1, v Є V  dimana (u,v) Є E.
 === Graf Lengkap ===
-{|
-|-
-! [[Berkas:Graf lengkap 1.jpg|thumb|center|Contoh Graf (5)]]
-! [[Berkas:Graf lengkap 2.jpg|thumb|center|Contoh Graf (6)]]
-|}
 ''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.
+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) [[http://www.springerlink.com/content/0d5wck103pc57nbq 2]] telah berhasil memperkecil nilai p yang dimaksud menjadi :
+George Karakostas (Mc Master, 2004) <ref>[http://www.springerlink.com/content/0d5wck103pc57nbq 2 Springerlink]{{Pranala mati|date=Maret 2021 |bot=InternetArchiveBot |fix-attempted=yes }}</ref> telah berhasil memperkecil nilai p yang dimaksud menjadi:
 <br>
-'''p=2-θ√(1/log n )'''
+<p align="center"> '''p=2-θ√(1/log n)'''
-== Algoritma ''Vertex Cover'' P-Aproksimasi ==
+== Algoritme ''Vertex Cover'' P-Aproksimasi ==
 G=(E,V)<br>
 <pre>
@@ Baris 55: / Baris 43: @@
 Return AVC
 </pre><br>
-Algoritma tersebut memiliki kompleksitas waktu ''O(mn)''
+Algoritme tersebut memiliki kompleksitas waktu ''O(mn)''
 == ''Claim Vertex Cover'' ==
-''Vertex Cover'' dapat diperoleh dari ILP, [[Himpunan bebas|Himpunan Bebas]], Maksimum ''Matching'', ''Hamiltonian Cycle'', ''Hamiltonian Path'' dimana setiap solusi dari permasalahan tersebut termasuk ''HARD PROBLEM''.
+''Vertex Cover'' dapat diperoleh dari ILP, [[Himpunan bebas|Himpunan Bebas]], Maksimum ''Matching'', ''[[Hamilton Cycle|Hamiltonian Cycle]]'', ''Hamiltonian Path'' di mana setiap solusi dari permasalahan tersebut termasuk ''HARD PROBLEM''.
 == Penerapan ''Vertex Cover'' di Dunia Nyata ==
@@ Baris 64: / Baris 52: @@
 == Referensi ==
+{{reflist}}
-[1] Thomas H Cormen, harles E. Leiserson, Ronald L. Rivest, Clifford Stein, “Introduction to Algorithms”, The MIT Press, Cambridge Massachusetts [CLRS]
+[[Kategori:Teori graf]]
-[2] [http://www.springerlink.com/content/0d5wck103pc57nbq/ Springerlink]