Pohon rentang minimum - Riwayat revisi

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

2026-08-23T04:04:39Z

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

← Revisi sebelumnya		Revisi per 23 Agustus 2026 04.04
Baris 1:		Baris 1:
			[[File:Minimum_spanning_tree.svg\|thumb\|right\|280px\|Minimum spanning tree]]

	'''Pohon rentang minimum''' atau '''pohon rentang berbobot minimum''' (, '''MST''') adalah himpunan bagian dari himpunan garis-garis (''edge'') suatu [[Graf (matematika)\|graf]] berbobot tak berarah yang menghubungkan semua titik tanpa membentuk siklus dan dengan total bobot minimum. Dengan kata lain, ini adalah [[pohon rentang]] yang total bobotnya minimum.		'''Pohon rentang minimum''' atau '''pohon rentang berbobot minimum''' (, '''MST''') adalah himpunan bagian dari himpunan garis-garis (''edge'') suatu [[Graf (matematika)\|graf]] berbobot tak berarah yang menghubungkan semua titik tanpa membentuk siklus dan dengan total bobot minimum. Dengan kata lain, ini adalah [[pohon rentang]] yang total bobotnya minimum.

Baris 10:		Baris 12:

	=== Keunikan ===		=== Keunikan ===

	Jika tiap garis memiliki bobot yang berbeda, hanya ada satu pohon rentang minimum. Hal ini benar untuk banyak kasus di kehidupan nyata karena jarang ada dua bobot yang ''tepat'' sama. Hal ini juga berlaku untuk hutan rentang.		Jika tiap garis memiliki bobot yang berbeda, hanya ada satu pohon rentang minimum. Hal ini benar untuk banyak kasus di kehidupan nyata karena jarang ada dua bobot yang ''tepat'' sama. Hal ini juga berlaku untuk hutan rentang.

Baris 22:		Baris 23:
	# Hal ini menjadi kontradiksi dari pernyataan bahwa ''B'' adalah MST.		# Hal ini menjadi kontradiksi dari pernyataan bahwa ''B'' adalah MST.

	Secara umum, jika ada garis-garis yang memiliki bobot yang sama, hanya sebagian garis pada pohon rentang minimum yang pasti unik.		Secara umum, jika ada garis-garis yang memiliki bobot yang sama, hanya sebagian garis pada pohon rentang minimum yang pasti unik.<ref>[https://cs.stackexchange.com/q/2204 Do the minimum spanning trees of a weighted graph have the same number of edges with a given weight?]. ''cs.stackexchange.com''.</ref>

	=== Graf bagian dengan bobot minimum ===		=== Graf bagian dengan bobot minimum ===
Baris 33:		Baris 34:

	== Algoritma ==		== Algoritma ==
	Algoritma pertama yang dipakai untuk mencari pohon rentang minimum dikembangkan oleh ilmuwan Ceko [[Otakar Borůvka]] pada tahun 1926 (lihat [[algoritme Borůvka]]). Kegunaan awalnya adalah membuat sistem kelistrikan yang efisien di daerah [[Moravia]]. Algoritma ini bekerja dalam deretan tahapan yang disebut langkah Boruvka. Kompleksitas algoritmanya adalah O(''m'' log ''n'').		Algoritma pertama yang dipakai untuk mencari pohon rentang minimum dikembangkan oleh ilmuwan Ceko [[Otakar Borůvka]] pada tahun 1926 (lihat [[algoritme Borůvka]]). Kegunaan awalnya adalah membuat sistem kelistrikan yang efisien di daerah [[Moravia]]. Algoritma ini bekerja dalam deretan tahapan yang disebut langkah Boruvka. Kompleksitas algoritmanya adalah O(''m'' log ''n'').<ref>Seth Pettie. [https://web.eecs.umich.edu/~pettie/papers/jacm-optmsf.pdf An optimal minimum spanning tree algorithm]. ''Journal of the Association for Computing Machinery''. 2002. Vol. 49 (1). hlm. 16–34. doi:10.1145/505241.505243..</ref>

	Algoritma kedua adalah [[algoritme Prim]]. Algoritma ini ditemukan oleh [[Vojtěch Jarník]] pada tahun 1930 dan ditemukan ulang oleh [[Robert C. Prim\|Prim]] pada tahun 1957 dan [[Edsger W. Dijkstra\|Dijkstra]] pada tahun 1959. Secara sederhana, algoritma ini mengembangkan MST (''T'') garis demi garis. Awalnya, ''T'' terdiri dari titik bebas. Pada tiap langkah, ''T'' ditambahkan garis berbobot minimum (''x'', ''y'') dengan ''x'' ada dalam ''T'' dan ''y'' belum ada dalam ''T''. Dengan sifat pemotongan, semua garis yang ditambahkan adalah MST. Kompleksitas algoritmanya adalah math\|O(''m'' log ''n'') atau O(''m'' + ''n'' log ''n'') tergantung struktur data yang dipakai.		Algoritma kedua adalah [[algoritme Prim]]. Algoritma ini ditemukan oleh [[Vojtěch Jarník]] pada tahun 1930 dan ditemukan ulang oleh [[Robert C. Prim\|Prim]] pada tahun 1957 dan [[Edsger W. Dijkstra\|Dijkstra]] pada tahun 1959. Secara sederhana, algoritma ini mengembangkan MST (''T'') garis demi garis. Awalnya, ''T'' terdiri dari titik bebas. Pada tiap langkah, ''T'' ditambahkan garis berbobot minimum (''x'', ''y'') dengan ''x'' ada dalam ''T'' dan ''y'' belum ada dalam ''T''. Dengan sifat pemotongan, semua garis yang ditambahkan adalah MST. Kompleksitas algoritmanya adalah math\|O(''m'' log ''n'') atau O(''m'' + ''n'' log ''n'') tergantung struktur data yang dipakai.
Baris 44:		Baris 45:

	== Penerapan ==		== Penerapan ==
	Pohon rentang minimum dipakai dalam desain jaringan, termasuk [[jaringan komputer]], [[jaringan telekomunikasi]], [[jaringan transportasi]], [[jaringan penyediaan air]], dan [[sistem kelistrikan]] (yang menjadi alasan penemuannya, sudah dijelaskan di atas).		Pohon rentang minimum dipakai dalam desain jaringan, termasuk [[jaringan komputer]], [[jaringan telekomunikasi]], [[jaringan transportasi]], [[jaringan penyediaan air]], dan [[sistem kelistrikan]] (yang menjadi alasan penemuannya, sudah dijelaskan di atas).<ref>R. L. Graham. ''On the history of the minimum spanning tree problem''. ''Annals of the History of Computing''. 1985. Vol. 7 (1). hlm. 43–57. doi:10.1109/MAHC.1985.10011..</ref>

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

			== Sumber dan atribusi ==

			Konten artikel ini diadaptasi dari [https://id.wikipedia.org/w/index.php?title=Pohon+rentang+minimum&oldid=28425096 Wikipedia bahasa Indonesia], revisi 28425096 (2025-11-12T08:59:49Z), yang tersedia berdasarkan lisensi Creative Commons Atribusi-BerbagiSerupa (CC BY-SA). Gambar pada artikel ini bersumber dari Wikimedia Commons dan mengikuti ketentuan lisensi masing-masing berkas. Mohon gunakan konten dan media secara bijak serta sesuai dengan ketentuan lisensi yang berlaku.

	~~== Sumber dan atribusi ==~~		<!-- WIKI_UNISSULA_PRESENTATION_V4 -->

	~~Konten artikel ini diadaptasi dari [https://id.wikipedia.org/w/index.php?title=Pohon+rentang+minimum&oldid=28425096 Wikipedia bahasa Indonesia], revisi 28425096 (2025~~-11-~~12T08:59:49Z), yang tersedia berdasarkan lisensi Creative Commons Atribusi~~-~~BerbagiSerupa (CC BY~~-~~SA). Mohon gunakan konten ini secara bijak serta sesuai dengan ketentuan lisensi yang berlaku.~~

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

2026-08-23T03:25:00Z

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

Halaman baru

'''Pohon rentang minimum''' atau '''pohon rentang berbobot minimum''' (, '''MST''') adalah himpunan bagian dari himpunan garis-garis (''edge'') suatu [[Graf (matematika)|graf]] berbobot tak berarah yang menghubungkan semua titik tanpa membentuk siklus dan dengan total bobot minimum. Dengan kata lain, ini adalah [[pohon rentang]] yang total bobotnya minimum.

Ada beberapa kasus yang menggunakan pohon rentang minimum. Misalnya, perusahaan telepon mencoba untuk menghubungkan telepon-telepon rumah dengan kabel sehingga kabel yang dipakai sependek mungkin. Di beberapa tempat, mungkin dibutuhkan penggalian sehingga biayanya bertambah. Dengan kata lain, "bobot" garisnya bertambah. Satuan yang biasa dipakai dalam masalah ini adalah biaya (''cost''). Dalam konteks ini, pohon rentang minimum adalah jalur yang menggunakan kabel sependek mungkin atau dengan biaya serendah mungkin.

== Sifat ==
=== Peluang ketergandaan (''multiplicity'') ===
Jika ada ''n'' titik pada graf, tiap pohon rentang memiliki ''n'' − 1 garis.

Mungkin ada beberapa pohon rentang minimum dengan bobot yang sama. Untuk graf dengan bobot garis yang seragam, semua pohon rentang adalah minimum.

=== Keunikan ===

Jika tiap garis memiliki bobot yang berbeda, hanya ada satu pohon rentang minimum. Hal ini benar untuk banyak kasus di kehidupan nyata karena jarang ada dua bobot yang ''tepat'' sama. Hal ini juga berlaku untuk hutan rentang.

Bukti:
# [[Pembuktian melalui kontradiksi|Misalkan kebalikannya]], yaitu ada dua MST yang berbeda: ''A'' dan ''B''.
# Karena ''A'' dan ''B'' berbeda, meski memiliki nodus yang sama, setidaknya ada satu garis yang berada dalam salah satu pohon, tetapi tidak dalam pohon lainnya. Di antara garis-garisnya, misalkan ''e''1 adalah garis dengan bobot terendah; pilihan ini unik karena bobot-bobot garis berbeda satu sama lain. Misalkan ''e''1 berada dalam ''A''.
# Karena ''B'' adalah MST, {''e''1} <math>\cup</math> ''B'' harus memiliki siklus ''C'' dengan ''e''1.
# Sebagai pohon, ''A'' tidak memiliki siklus, maka ''C'' harus memiliki garis ''e''2 yang tidak ada dalam ''A''.
# Karena ''e''1 dipilih sebagai garis unik berbobot minimum di antara garis-garis yang dimiliki oleh tepat salah satu dari ''A'' dan ''B'', bobot ''e''2 harus lebih besar daripada bobot ''e''1.
# Karena ''e''1 dan ''e''2 adalah bagian dari siklus ''C'', penggantian ''e''2 dengan ''e''1 mengakibatkan pohon rentang dengan bobot yang lebih kecil.
# Hal ini menjadi kontradiksi dari pernyataan bahwa ''B'' adalah MST.

Secara umum, jika ada garis-garis yang memiliki bobot yang sama, hanya sebagian garis pada pohon rentang minimum yang pasti unik.

=== Graf bagian dengan bobot minimum ===
Jika semua bobot adalah positif, pohon rentang minimum adalah graf bagian (subgraf) berbobot minimum yang menghubungkan semua titik. Graf bagian yang memiliki siklus membutuhkan total bobot yang lebih banyak.

=== Sifat siklus ===
Untuk tiap siklus ''C'' dalam graf, jika bobot suatu garis ''e'' yang ada dalam ''C'' lebih besar daripada bobot tiap-tiap garis yang ada dalam ''C'', garis ini tidak dapat dimasukkan ke dalam MST.

Bukti: [[Pembuktian melalui kontradiksi|Misalkan sebaliknya]], yaitu ''e'' dimasukkan ke dalam MST ''T''1, maka penghapusan ''e'' akan membagi ''T''1 menjadi dua pohon bagian (subpohon) yang berbeda. Sisa ''C'' menghubungkan kedua pohon bagian, sehingga ada garis ''f'' yang berada dalam dua pohon bagian. Dengan kata lain, garis ''f'' menghubungkan dua pohon bagian menjadi pohon ''T''2 dengan bobot yang lebih kecil daripada ''T''1 karena bobot ''f'' lebih kecil daripada bobot ''e''.

== Algoritma ==
Algoritma pertama yang dipakai untuk mencari pohon rentang minimum dikembangkan oleh ilmuwan Ceko [[Otakar Borůvka]] pada tahun 1926 (lihat [[algoritme Borůvka]]). Kegunaan awalnya adalah membuat sistem kelistrikan yang efisien di daerah [[Moravia]]. Algoritma ini bekerja dalam deretan tahapan yang disebut langkah Boruvka. Kompleksitas algoritmanya adalah O(''m'' log ''n'').

Algoritma kedua adalah [[algoritme Prim]]. Algoritma ini ditemukan oleh [[Vojtěch Jarník]] pada tahun 1930 dan ditemukan ulang oleh [[Robert C. Prim|Prim]] pada tahun 1957 dan [[Edsger W. Dijkstra|Dijkstra]] pada tahun 1959. Secara sederhana, algoritma ini mengembangkan MST (''T'') garis demi garis. Awalnya, ''T'' terdiri dari titik bebas. Pada tiap langkah, ''T'' ditambahkan garis berbobot minimum (''x'', ''y'') dengan ''x'' ada dalam ''T'' dan ''y'' belum ada dalam ''T''. Dengan sifat pemotongan, semua garis yang ditambahkan adalah MST. Kompleksitas algoritmanya adalah math|O(''m'' log ''n'') atau O(''m'' + ''n'' log ''n'') tergantung struktur data yang dipakai.

Algoritma ketiga yang sering dipakai adalah [[algoritme Kruskal]]. Kompleksitas algoritmanya adalah O(''m'' log ''n'').

Algoritma keempat yang jarang dipakai adalah [[algoritme hapus mundur]] yang merupakan kebalikan dari algoritma Kruskal. Kompleksitas algoritmanya adalah O(''m'' log ''n'' (log log ''n'')3).

Keempat algoritma tersebut termasuk [[algoritme rakus]] (''greedy'').

== Penerapan ==
Pohon rentang minimum dipakai dalam desain jaringan, termasuk [[jaringan komputer]], [[jaringan telekomunikasi]], [[jaringan transportasi]], [[jaringan penyediaan air]], dan [[sistem kelistrikan]] (yang menjadi alasan penemuannya, sudah dijelaskan di atas).

== Referensi ==

== Sumber dan atribusi ==

Konten artikel ini diadaptasi dari [https://id.wikipedia.org/w/index.php?title=Pohon+rentang+minimum&oldid=28425096 Wikipedia bahasa Indonesia], revisi 28425096 (2025-11-12T08:59:49Z), yang tersedia berdasarkan lisensi Creative Commons Atribusi-BerbagiSerupa (CC BY-SA). Mohon gunakan konten ini secara bijak serta sesuai dengan ketentuan lisensi yang berlaku.