Dalam dunia ilmu komputer dan optimasi jaringan, konsep Pohon Rentang Minimum atau Minimum Spanning Tree (MST) merupakan salah satu fondasi penting. Baik Anda seorang mahasiswa informatika maupun penghobi pemrograman, memahami cara menentukan jalur paling efisien dalam sebuah graf adalah keterampilan yang sangat berharga. Artikel ini akan membimbing Anda memahami konsep dasar hingga mengerjakan latihan soal secara mandiri.
Baca juga: Kumpulan Contoh Soal Primordialisme Dan Jawabannya Untuk SMA
Apa Itu Pohon Rentang Minimum (MST)?
Sebelum masuk ke latihan soal, mari kita bedah definisinya secara sederhana. Bayangkan Anda ingin menghubungkan beberapa rumah di sebuah desa dengan kabel internet. Anda ingin semua rumah terhubung satu sama lain, tetapi Anda ingin menggunakan kabel sesedikit mungkin (biaya terendah).
Secara teknis, MST adalah bagian dari graf (subgraf) yang memenuhi kriteria berikut:
- Menghubungkan semua simpul (node) tanpa kecuali.
- Tidak membentuk sirkuit atau loop (sehingga disebut “pohon”).
- Memiliki total bobot sisi (edge weight) paling minimum dibandingkan semua kemungkinan pohon rentang lainnya.
Dua Algoritma Utama: Prim dan Kruskal
Untuk menyelesaikan soal-soal MST, ada dua algoritma populer yang sering digunakan:
1. Algoritma Kruskal
Algoritma ini bekerja dengan cara mengurutkan semua sisi dari bobot terkecil ke terbesar. Kita mengambil sisi satu per satu, asalkan sisi tersebut tidak membentuk siklus, sampai semua simpul terhubung.
2. Algoritma Prim
Algoritma ini bekerja secara “tumbuh” dari satu simpul awal. Kita memilih sisi dengan bobot terkecil yang menghubungkan simpul yang sudah terpilih dengan simpul yang belum terpilih.
Latihan Soal 1: Memahami Dasar Graf
Perhatikan graf sederhana berikut yang terdiri dari 4 simpul (A, B, C, D) dengan bobot sisi sebagai berikut:
- A – B: 4
- A – C: 1
- B – C: 2
- B – D: 5
- C – D: 3
Pertanyaan: Tentukan Pohon Rentang Minimum dan total bobotnya menggunakan Algoritma Kruskal!
Pembahasan Soal 1:
Langkah demi langkah menggunakan Kruskal:
- Urutkan semua sisi berdasarkan bobot:
- A – C (1)
- B – C (2)
- C – D (3)
- A – B (4)
- B – D (5)
- Pilih sisi tanpa membentuk siklus:
- Pilih A – C (1). (Total Bobot = 1)
- Pilih B – C (2). (Total Bobot = 3)
- Pilih C – D (3). (Total Bobot = 6)
- Cek A – B (4): Jika kita mengambil A-B, maka akan terbentuk siklus (A-C-B-A). Jadi, A-B ditolak.
- Cek B – D (5): Semua simpul sudah terhubung (A, B, C, D), jadi pencarian selesai.
Jawaban: MST terdiri dari sisi {A-C, B-C, C-D} dengan Total Bobot = 6.
Latihan Soal 2: Kasus Jaringan Listrik Desa
Sebuah perusahaan listrik ingin membangun jalur kabel di 5 desa (V1, V2, V3, V4, V5). Berikut adalah daftar jarak antar desa:
- V1 – V2: 10 km
- V1 – V3: 6 km
- V1 – V4: 5 km
- V2 – V4: 15 km
- V3 – V4: 4 km
- V3 – V5: 8 km
- V4 – V5: 9 km
Pertanyaan: Gunakan Algoritma Prim (dimulai dari V1) untuk menentukan jalur kabel terpendek!
Pembahasan Soal 2:
Langkah demi langkah menggunakan Prim:
- Mulai dari V1: Sisi yang terhubung adalah V1-V2 (10), V1-V3 (6), V1-V4 (5). Pilih yang terkecil: V1-V4 (5).
- Sekarang dari {V1, V4}: Sisi yang tersedia adalah V1-V2 (10), V1-V3 (6), V4-V2 (15), V4-V3 (4), V4-V5 (9). Pilih yang terkecil: V4-V3 (4).
- Sekarang dari {V1, V4, V3}: Sisi yang tersedia adalah V1-V2 (10), V3-V5 (8), V4-V5 (9). (V1-V3 tidak dipilih karena sudah terhubung secara internal). Pilih yang terkecil: V3-V5 (8).
- Sekarang dari {V1, V4, V3, V5}: Sisi yang tersedia adalah V1-V2 (10) atau V4-V2 (15). Pilih yang terkecil: V1-V2 (10).
- Selesai: Semua desa terhubung.
Jawaban: Jalur MST adalah (V1-V4), (V4-V3), (V3-V5), (V1-V2) dengan Total Bobot = 5 + 4 + 8 + 10 = 27 km.
Pentingnya Mempelajari MST bagi Pemula
Banyak yang bertanya, “Mengapa saya harus belajar ini?”. Berikut adalah beberapa penerapan nyata MST:
- Pembangunan Infrastruktur: Merancang jaringan pipa air, kabel listrik, atau serat optik dengan biaya material paling rendah.
- Protokol Jaringan Komputer: Spanning Tree Protocol (STP) digunakan pada switch jaringan untuk mencegah “broadcast storm” yang dapat melumpuhkan internet.
- Analisis Cluster: Dalam data science, MST digunakan untuk mengelompokkan data berdasarkan kedekatannya.
Tips Mengerjakan Soal Pohon Rentang Minimum
- Gambar Graf Terlebih Dahulu: Jangan hanya mengandalkan daftar angka. Visualisasi membantu Anda melihat apakah ada siklus yang terbentuk.
- Cek Jumlah Sisi: Jika jumlah simpul adalah $n$, maka jumlah sisi pada MST haruslah $n – 1$. Jika simpul ada 5, sisi MST harus ada 4.
- Hati-hati dengan Bobot yang Sama: Jika ada dua sisi dengan bobot yang sama, Anda bisa memilih salah satunya secara bebas, kecuali soal menentukan aturan khusus. Hasil MST mungkin berbeda bentuknya, tetapi total bobotnya pasti akan tetap sama (minimum).
Latihan Mandiri untuk Anda
Coba kerjakan soal berikut untuk menguji pemahaman Anda:
Graf:
- P – Q: 7
- P – R: 8
- Q – R: 3
- Q – S: 6
- R – S: 4
- R – T: 3
- S – T: 2
- S – U: 5
- T – U: 2
Pertanyaan: Hitunglah MST menggunakan algoritma pilihan Anda dan tentukan total bobot akhirnya. (Petunjuk: Mulailah dari sisi dengan bobot terkecil).
Kunci Jawaban Latihan Mandiri:
Jika Anda mengerjakan dengan benar, Anda akan mendapatkan sisi-sisi berikut:
- T – U (2)
- S – T (2)
- Q – R (3)
- R – T (3)
- R – S (4) – Ditolak karena membentuk siklus
- S – U (5) – Ditolak karena membentuk siklus
- Q – S (6) – Ditolak karena membentuk siklus
- P – Q (7)
Total Bobot Akhir: 17.
Kesimpulan
Pohon Rentang Minimum adalah konsep yang elegan namun sederhana jika kita memahami logika dasarnya. Baik Algoritma Kruskal maupun Prim akan memberikan hasil yang sama dalam hal efisiensi total. Kuncinya adalah ketelitian dalam memilih sisi dan memastikan tidak ada simpul yang membentuk jalur tertutup (siklus).
Teruslah berlatih dengan variasi graf yang lebih kompleks untuk mengasah intuisi Anda dalam optimasi jaringan. Semakin sering Anda berlatih, semakin cepat Anda bisa melihat jalur efisien tanpa harus menghitung satu per satu.
Penulis: Aripin
Post Comment