Maintenance script: Presentation V4: sitasi, referensi, Math, Wikimedia Commons, dan atribusi

2026-08-23T10:31:21Z

Presentation V4: sitasi, referensi, Math, Wikimedia Commons, dan atribusi

← Revisi sebelumnya		Revisi per 23 Agustus 2026 10.31
Baris 2:		Baris 2:

	== Definisi ==		== 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.		''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]]''.		Dilihat dari definisi, ''vertex cover'' berbeda dengan ''[[edge cover]]''.
Baris 19:		Baris 19:
	== Evaluasi Aproksimasi ==		== Evaluasi Aproksimasi ==
	Pencarian ''minimum vertex cover'' dapat ditempuh dengan cara p-aproksimasi, yang memiliki waktu eksekusi [[polinomial]]. Untuk masalah minimisasi, akan didapatkan solusi ≤ p kali lebih buruk daripada solusi aslinya.		Pencarian ''minimum vertex cover'' dapat ditempuh dengan cara p-aproksimasi, yang memiliki waktu eksekusi [[polinomial]]. Untuk masalah minimisasi, akan didapatkan solusi ≤ p kali lebih buruk daripada solusi aslinya.
	George Karakostas (Mc Master, 2004) telah berhasil memperkecil nilai p yang dimaksud menjadi:		George Karakostas (Mc Master, 2004) <ref>[http://www.springerlink.com/content/0d5wck103pc57nbq 2 Springerlink]</ref> telah berhasil memperkecil nilai p yang dimaksud menjadi:
	<br>		<br>
	<p align="center"> '''p=2-θ√(1/log n)'''		<p align="center"> '''p=2-θ√(1/log n)'''
Baris 27:		Baris 27:
	<pre>		<pre>
	VC Aproksimasi (G)		VC Aproksimasi (G)
	AVC = ø		AVC = ø
	E’ = E		E’ = E
	While E’ ≠ ø		While E’ ≠ ø
	Ambil secara bebas (u,v) Є E’		Ambil secara bebas (u,v) Є E’
	AVC = AVC ∪ {u,v}		AVC = AVC ∪ {u,v}
	Hapus semua busur (x,u), (x,v) Є E’, x Є V		Hapus semua busur (x,u), (x,v) Є E’, x Є V
	Endwhile		Endwhile
	Return AVC		Return AVC
Baris 45:		Baris 45:

	== Referensi ==		== Referensi ==
			<references />


	== Sumber dan atribusi ==		== Sumber dan atribusi ==

	Konten artikel ini diadaptasi dari [https://id.wikipedia.org/w/index.php?title=Tutup+verteks&oldid=29227604 Wikipedia bahasa Indonesia], revisi 29227604 (2026-05-14T14:49:32Z), yang tersedia berdasarkan lisensi Creative Commons Atribusi-BerbagiSerupa (CC BY-SA). Mohon gunakan konten ini secara bijak serta sesuai dengan ketentuan lisensi yang berlaku.		Konten artikel ini diadaptasi dari [https://id.wikipedia.org/w/index.php?title=Tutup+verteks&oldid=29227604 Wikipedia bahasa Indonesia], revisi 29227604 (2026-05-14T14:49:32Z), yang tersedia berdasarkan lisensi Creative Commons Atribusi-BerbagiSerupa (CC BY-SA). Mohon gunakan konten ini secara bijak serta sesuai dengan ketentuan lisensi yang berlaku.

			<!-- WIKI_UNISSULA_PRESENTATION_V4 -->

Maintenance script: Impor teks terkontrol dari Wikipedia bahasa Indonesia; revisi 29227604; atribusi sumber disertakan.

2026-08-23T10:07:18Z

Impor teks terkontrol dari Wikipedia bahasa Indonesia; revisi 29227604; atribusi sumber disertakan.

Halaman baru

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. Masalah yang ditemukan adalah bagaimana mencari ''vertex cover'' yang jumlahnya ''minimum''. Masalah ini termasuk masalah 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.

Dilihat dari definisi, ''vertex cover'' berbeda dengan ''[[edge cover]]''.

=== ''Minimum Vertex Cover'' ===
Dalam kasus ''minimum vertex cover'', masalah 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 masalah minimisasi, akan didapatkan solusi ≤ p kali lebih buruk daripada solusi aslinya.
George Karakostas (Mc Master, 2004) telah berhasil memperkecil nilai p yang dimaksud menjadi:
<br>
<p align="center"> '''p=2-θ√(1/log n)'''

== Algoritma ''Vertex Cover'' P-Aproksimasi ==
G=(E,V)<br>
<pre>
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
</pre><br>
Algoritma tersebut memiliki kompleksitas waktu ''O(mn)''

== ''Claim Vertex Cover'' ==
''Vertex Cover'' dapat diperoleh dari ILP, [[Himpunan bebas|Himpunan Bebas]], Maksimum ''Matching'', ''[[Hamilton Cycle|Hamiltonian Cycle]]'', ''Hamiltonian Path'' di mana setiap solusi dari masalah 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 ==

== Sumber dan atribusi ==

Konten artikel ini diadaptasi dari [https://id.wikipedia.org/w/index.php?title=Tutup+verteks&oldid=29227604 Wikipedia bahasa Indonesia], revisi 29227604 (2026-05-14T14:49:32Z), yang tersedia berdasarkan lisensi Creative Commons Atribusi-BerbagiSerupa (CC BY-SA). Mohon gunakan konten ini secara bijak serta sesuai dengan ketentuan lisensi yang berlaku.

Tutup verteks - Riwayat revisi

Maintenance script: Presentation V4: sitasi, referensi, Math, Wikimedia Commons, dan atribusi

Maintenance script: Impor teks terkontrol dari Wikipedia bahasa Indonesia; revisi 29227604; atribusi sumber disertakan.