Penentuan Pohon Perentang Minimum Ke-k Dengan Menggunakan Algoritma k-MST

Erliana, Erliana (2023) Penentuan Pohon Perentang Minimum Ke-k Dengan Menggunakan Algoritma k-MST. Skripsi thesis, Universitas Tanjungpura.

	Text (Cover) Cover_H1011171009.pdf - Published Version Download (140kB)
	Text (Yuridis) Yuridis_H1011171009.pdf - Accepted Version Download (157kB)
	Text (Surat Pernyataan) SP_H1011171009.pdf - Published Version Download (38kB)
	Text (Abstrak) Abstrak_H1011171009.pdf - Published Version Download (215kB)
	Text (Kata Pengantar) Kapeng_H1011171009.pdf - Published Version Download (161kB)
	Text (Daftar Isi) Dafis_H1011171009.pdf - Published Version Download (101kB)
	Text (Daftar Lain) Daflain_H1011171009.pdf - Published Version Download (107kB)
	Text (Bab I) Bab1_H1011171009.pdf - Published Version Download (137kB)
	Text (Bab II) Bab2_H1011171009.pdf - Published Version Download (218kB)
	Text (Bab III) Bab3_H1011171009.pdf - Accepted Version Restricted to Repository staff only Download (452kB)
	Text (Bab IV) Bab4_H1011171009.pdf - Accepted Version Restricted to Repository staff only Download (100kB)
	Text (Daftar Pustaka) Dapus_H1011171009.pdf - Published Version Download (100kB)
	Text (Lampiran) Lamp_H1011171009.pdf - Accepted Version Restricted to Repository staff only Download (46kB)
	Text (H1011171009_ERLIANA) H1011171009_ERLIANA.pdf - Accepted Version Restricted to Repository staff only Download (1MB)

Abstract

Pohon perentang minimum pada graf berbobot G adalah pohon yang memuat semua simpul pada G dan memiliki jumlah bobot minimum. Salah satu algoritma yang digunakan untuk menentukan pohon perentang minimum dari G adalah algoritma Prim. Algoritma Prim hanya dapat menentukan satu pohon perentang minimum, sedangkan hasil yang diperoleh bisa jadi tidak dapat diterapkan. Hal ini dapat terjadi apabila terdapat kendala pada sisinya saat diaplikasikan pada permasalahan di kehidupan sehari-hari. Oleh karena itu, diperlukan suatu langkah lanjutan untuk memperoleh alternatif pohon perentang minimum kedua dan seterusnya. Pada skripsi ini, dibahas tentang penentuan pohon perentang minimum pertama pada suatu contoh graf dengan menggunakan algoritma Prim dan pohon perentang minimum ke-K dengan nilai K = 2,3, … menggunakan algoritma K-MST. Skripsi ini dimulai dengan menentukan pohon perentang minimum pertama, misalnya T1. Dari T1 yang diperoleh, dicari T2 dan seterusnya dengan cara mengganti satu per satu sisi pada T 1 dengan sisi lain pada G yang bukan merupakan sisi pada T. Kemudian bobot semua pohon perentang yang dihasilkan diurutkan berdasarkan bobot terkecil. Dengan mengulangi proses yang sama sampai diperoleh pohon perentang minimum ke-K. Hasil dari contoh graf pada skripsi ini, dimana contoh graf tersebut memiliki 5 simpul dan 6 sisi diperoleh 11 pohon perentang yang berbeda dengan bobot terkecil 11 dan bobot terbesar 18. Sedangkan pada contoh graf jaringan pipa distribusi air bersih dengan kendala salah satu sisinya tidak dapat dilewati, diperoleh pohon perentang minimum ke-1, 2 dan 3 tidak memenuhi kendala. Adapun pohon perentang minimum ke-4 sudah memenuhi kendala dengan bobot totalnya yaitu 22.

Actions (login required)

View Item