PENENTUAN POHON PERENTANG MINIMUM KE-k DENGAN MENGGUNAKAN ALGORITMA k-MST

Abstract

Pohon perentang minimum (MST) pada graf berbobot  adalah pohon yang memuat semua simpul pada  dan memiliki bobot terkecil. Algoritma yang digunakan untuk menentukan MST adalah algoritma Prim. Secara umum, Algoritma Prim hanya menghasilkan satu MST, atau lebih dengan bobot yang sama, sedangkan hasil tersebut mungkin tidak dapat diterapkan. Hal ini terjadi apabila terdapat kendala pada salah satu sisi MST saat diaplikasikan pada permasalahan di kehidupan sehari-hari. Oleh karenanya, diperlukan langkah lanjutan untuk memperoleh alternatif MST berikutnya. Artikel ini membahas penentuan MST ke-1 menggunakan algoritma Prim dan MST ke-k  dengan  menggunakan algoritma k-MST. Artikel ini diawali dengan menentukan pohon perentang minimum pertama, misalnya . Dari , dicari  dan seterusnya dengan mengganti satu per satu sisi dengan sisi lain pada  yang bukan merupakan sisi pada . Kemudian bobot semua pohon perentang diurutkan berdasarkan bobot terkecil. Dengan mengulangi proses yang sama diperoleh pohon perentang minimum ke-k. Hasil pada graf yang dicontohkan dalam artikel ini, yaitu graf dengan  simpul dan  sisi, diperoleh  pohon perentang dengan bobot terkecil  11 dan bobot terbesar 18. Sedangkan pada contoh graf jaringan pipa dengan kendala satu sisi tidak dapat dilewati, diperoleh MST ke-4 yang memenuhi kendala dengan bobot total 22.