Kumpulan Contoh Soal Pohon Rentang Minimum yang Sering Muncul di Ujian

Pohon Rentang Minimum atau Minimum Spanning Tree (MST) merupakan salah satu konsep fundamental dalam teori graf yang memiliki aplikasi luas di dunia nyata, mulai dari desain jaringan listrik, telekomunikasi, hingga perencanaan rute pipa air. Bagi mahasiswa teknik informatika atau matematika diskrit, menguasai MST adalah kewajiban karena materi ini hampir selalu muncul dalam ujian tengah maupun akhir semester.

Dalam artikel ini, kita akan mengupas tuntas konsep dasar, algoritma utama (Kruskal dan Prim), serta kumpulan contoh soal dan pembahasan yang dirancang mirip dengan tipe soal ujian pada umumnya.

Baca juga: Latihan Contoh Soal Tes Baum Beserta Tips Psikotes agar Lulus

Apa Itu Pohon Rentang Minimum (MST)?

Sebelum masuk ke contoh soal, kita perlu menyamakan persepsi. Spanning Tree (Pohon Rentang) adalah subgraf dari graf terhubung yang mencakup semua simpul (node) tanpa membentuk sirkuit atau cycle.

Minimum Spanning Tree adalah Spanning Tree yang memiliki total bobot sisi (edge weight) paling kecil di antara semua kemungkinan pohon rentang yang ada.

Karakteristik Utama MST:

• Jika graf memiliki $V$ buah simpul, maka MST akan memiliki tepat $V-1$ buah sisi.
• Tidak boleh ada cycle (sirkuit).
• Graf harus terhubung (connected).
• Jika bobot setiap sisi berbeda, maka MST-nya bersifat unik.

Algoritma Penyelesaian MST

Dua algoritma yang paling sering diujikan adalah Algoritma Kruskal dan Algoritma Prim. Keduanya bersifat greedy, namun memiliki pendekatan yang berbeda.

1. Algoritma Kruskal

Algoritma ini fokus pada sisi (edge).

• Urutkan semua sisi dari bobot terkecil ke terbesar.
• Pilih sisi dengan bobot terkecil satu per satu.
• Tambahkan sisi tersebut ke dalam MST asalkan tidak membentuk cycle.
• Berhenti jika sudah mencapai $V-1$ sisi.

2. Algoritma Prim

Algoritma ini fokus pada simpul (node).

• Mulai dari satu simpul sembarang.
• Lihat semua sisi yang terhubung ke simpul yang sudah terpilih.
• Pilih sisi dengan bobot terkecil yang menghubungkan ke simpul yang belum terpilih.
• Ulangi hingga semua simpul terhubung.

Kumpulan Contoh Soal dan Pembahasan

Berikut adalah beberapa variasi soal yang sering muncul di lembar ujian.

Contoh Soal 1: Dasar Algoritma Kruskal

Soal: Diketahui sebuah graf dengan simpul {A, B, C, D, E} dan bobot sisi sebagai berikut:

(A,B)=4, (A,C)=2, (B,C)=1, (B,D)=5, (C,D)=8, (C,E)=10, (D,E)=2.

Tentukan MST menggunakan algoritma Kruskal dan hitung total bobotnya!

Pembahasan:

Langkah 1: Urutkan sisi berdasarkan bobot:

1. (B,C) = 1
2. (A,C) = 2
3. (D,E) = 2
4. (A,B) = 4
5. (B,D) = 5
6. (C,D) = 8
7. (C,E) = 10

Langkah 2: Pilih sisi satu per satu:

• Pilih (B,C) bobot 1. (MST sementara: {B,C})
• Pilih (A,C) bobot 2. (MST sementara: {B,C, A})
• Pilih (D,E) bobot 2. (MST sementara: {B,C, A, D, E})
• Cek (A,B) bobot 4. Jika dipilih, akan membentuk cycle A-B-C-A. Maka Tolak.
• Pilih (B,D) bobot 5. (MST selesai karena sudah ada 4 sisi untuk 5 simpul).

Hasil Akhir: Sisi yang dipilih adalah (B,C), (A,C), (D,E), (B,D).

Total Bobot: $1 + 2 + 2 + 5 = 10$.

Contoh Soal 2: Dasar Algoritma Prim

Soal: Gunakan graf yang sama dengan Soal 1, namun selesaikan dengan Algoritma Prim mulai dari simpul A.

Pembahasan:

• Mulai dari A. Sisi yang terhubung: (A,B)=4, (A,C)=2. Pilih (A,C) karena terkecil.
• Simpul terpilih {A, C}. Sisi yang terhubung ke luar: (A,B)=4, (C,B)=1, (C,D)=8, (C,E)=10. Pilih (C,B) karena terkecil.
• Simpul terpilih {A, C, B}. Sisi yang terhubung ke luar: (B,D)=5, (C,D)=8, (C,E)=10. Pilih (B,D) karena terkecil.
• Simpul terpilih {A, C, B, D}. Sisi yang terhubung ke luar: (D,E)=2, (C,E)=10. Pilih (D,E) karena terkecil.
• Semua simpul sudah terhubung.

Hasil Akhir: Sisi yang dipilih (A,C), (C,B), (B,D), (D,E).

Total Bobot: $2 + 1 + 5 + 2 = 10$.

Contoh Soal 3: MST pada Graf Matriks Adjasensi

Dalam ujian yang lebih teknis, soal sering disajikan dalam bentuk matriks, bukan gambar graf.

Soal: Tentukan bobot MST dari matriks berikut:

      A   B   C   D
A [ 0,  5,  10, 0 ]
B [ 5,  0,  3,  11]
C [ 10, 3,  0,  2 ]
D [ 0,  11, 2,  0 ]

(Catatan: 0 berarti tidak ada jalur langsung)

Pembahasan:

Sisi-sisi yang tersedia: (A,B)=5, (A,C)=10, (B,C)=3, (B,D)=11, (C,D)=2.

Urutan sisi (Kruskal):

1. (C,D) = 2 -> Ambil
2. (B,C) = 3 -> Ambil
3. (A,B) = 5 -> Ambil
4. (A,C) = 10 -> Cycle (A-B-C-A) -> Tolak
5. (B,D) = 11 -> Cycle (B-C-D-B) -> Tolak

Total Bobot: $2 + 3 + 5 = 10$.

Strategi Menghadapi Soal Ujian MST

Agar Anda mendapatkan nilai sempurna saat ujian, perhatikan beberapa tips berikut:

1. Perhatikan Jumlah Simpul

Selalu ingat rumus $n-1$. Jika graf memiliki 10 simpul, jawaban Anda harus memiliki tepat 9 garis. Jika kurang, berarti graf belum terhubung; jika lebih, pasti ada cycle.

2. Cek Cycle Secara Teliti

Pada algoritma Kruskal, kesalahan paling umum adalah tetap memasukkan sisi kecil padahal ia membentuk sirkuit. Selalu gambar ulang sketsa MST Anda setiap kali menambah sisi baru.

3. Penanganan Bobot Kembar

Jika ada dua sisi dengan bobot yang sama (misal ada dua sisi berbobot 5), Anda bebas memilih yang mana saja terlebih dahulu. Hal ini sering menghasilkan bentuk pohon yang berbeda, tetapi total bobotnya akan tetap sama (minimum).

4. Gunakan Tabel untuk Algoritma Prim

Jika soal meminta langkah-langkah eksplisit (trace), buatlah tabel yang mencatat:

• Simpul yang sudah dikunjungi (Visited set).
• Kandidat sisi berikutnya.
• Sisi yang akhirnya dipilih.

Aplikasi MST dalam Kehidupan Nyata

Memahami contoh soal saja tidak cukup tanpa tahu tujuannya. Dosen sering memberikan soal bonus mengenai aplikasi MST:

• Jaringan Kabel: Menghubungkan beberapa rumah ke satu sumber listrik dengan total panjang kabel paling pendek.
• Protokol Routing: Digunakan dalam protokol OSPF (Open Shortest Path First) di jaringan komputer.
• Analisis Klaster: Dalam data science untuk mendeteksi kelompok data yang saling berhubungan.

Latihan Mandiri (Challenge)

Cobalah selesaikan soal berikut untuk menguji pemahaman Anda:

Graf G memiliki simpul {P, Q, R, S, T, U}

Sisi: (P,Q)=7, (P,R)=8, (Q,R)=5, (Q,S)=9, (R,S)=6, (R,T)=10, (S,T)=11, (S,U)=12, (T,U)=4.

Pertanyaan: Berapakah total bobot MST-nya? (Jawaban: 30)

Baca juga: Mahasiswa Universitas Teknokrat Indonesia Laksanakan Kunjungan Proyek Untuk Mata Kuliah K3 di Pembangunan New WTP Krenceng Tahap 2, Cilegon

Kesimpulan

Pohon Rentang Minimum adalah materi yang logis dan sistematis. Algoritma Kruskal sangat cocok digunakan jika Anda lebih suka mengurutkan data, sedangkan Algoritma Prim sangat efisien jika Anda bekerja langsung pada visualisasi graf. Dengan memperbanyak latihan pada berbagai variasi soal di atas, Anda akan lebih siap menghadapi ujian matematika diskrit atau struktur data.

Kunci utama dalam mengerjakan soal MST adalah ketelitian. Jangan sampai melewatkan satu sisi kecil atau secara tidak sengaja membentuk jalur tertutup (cycle).

Penulis: Aripin