Spanning Tree dan Link Download File Referensi
https://eu2.contabostorage.com/00f3241116844f24b628f46d81abb929:st1/folder6/6678/1656177361_pohon_-_Matematika.ppt
2026-05-30 19:15:08 - Admin
<style> body { font-family: Arial, Helvetica, sans-serif; line-height: 1.6; margin: 0; padding: 20px; background-color: #f9f9f9; color: #333; } h1, h2, h3 { color: #2c3e50; } a { color: #2980b9; text-decoration: none; } a:hover { text-decoration: underline; } ul { margin-left: 20px; } .section { margin-bottom: 30px; } .image { max-width: 100%; height: auto; display: block; margin: 10px auto; } table { border-collapse: collapse; width: 100%; margin-top: 10px; } th, td { border: 1px solid #bbb; padding: 8px; text-align: left; } th { background-color: #ecf0f1; } </style> <header class="section"> <h1>Spanning Tree: Konsep, Algoritma, dan Aplikasinya</h1> <p>Spanning tree (pohon rentang) adalah struktur penting dalam teori graf yang memiliki banyak aplikasi praktis, mulai dari jaringan komputer hingga optimasi transportasi.</p> </header> <section class="section"> <h2>Apa Itu Spanning Tree?</h2> <p>Dalam sebuah graf tak berarah yang terhubung, sebuah <strong>spanning tree</strong> adalah subgraf yang mencakup semua simpul (vertex) graf asal, namun tidak mengandung siklus. Dengan kata lain, ia merupakan pohon yang merentang ke seluruh vertex.</p> <ul> <li><strong>Simpul</strong> titik atau node dalam graf.</li> <li><strong>Edge</strong> garis yang menghubungkan dua simpul.</li> <li><strong>Pohon</strong> graf terhubung tanpa siklus.</li> </ul> <p>Karena tidak ada siklus, sebuah spanning tree pada graf dengan <em>n</em> simpul selalu memiliki tepat <em>n1</em> edge.</p> </section> <section class="section"> <h2>Properti Penting</h2> <ul> <li>Setiap graf terhubung memiliki paling sedikit satu spanning tree.</li> <li>Jika graf memiliki <em>m</em> edge, jumlah semua spanning tree dapat dihitung dengan <em>determinant</em> dari matriks Laplacian (teorema Kirchhoff).</li> <li>Spanning tree tidak bersifat unik; graf dapat memiliki banyak spanning tree berbeda.</li> </ul> </section> <section class="section"> <h2>Algoritma Pencarian Spanning Tree</h2> <h3>1. Algoritma Kruskal</h3> <p>Kruskal membangun Minimum Spanning Tree (MST) dengan cara menambahkan edge terkecil yang tidak membentuk siklus, menggunakan struktur UnionFind.</p> <ol> <li>Urutkan semua edge berdasarkan bobot naik.</li> <li>Iterasi, tambahkan edge ke pohon jika kedua ujungnya berada di komponen yang berbeda.</li> <li>Hentikan setelah <em>n1</em> edge dipilih.</li> </ol> <h3>2. Algoritma Prim</h3> <p>Prim memulai dari satu simpul dan secara bertahap menambahkan edge terkecil yang menghubungkan vertex yang sudah termasuk ke yang belum.</p> <ol> <li>Pilih simpul asal (biasanya 0).</li> <li>Gunakan priority queue untuk menyimpan edge paling ringan yang keluar dari himpunan terpilih.</li> <li>Tambahkan edge dengan bobot minimum ke MST sampai semua vertex termasuk.</li> </ol> <h3>3. Algoritma Borvka (atau Sollin)</h3> <p>Setiap komponen secara paralel memilih edge teringan yang keluar darinya, kemudian menggabungkan komponen-komponen tersebut. Proses diulang sampai satu komponen tersisa.</p> <h3>4. Algoritma DepthFirst Search (DFS) / BreadthFirst Search (BFS)</h3> <p>Jika hanya diperlukan sebuah spanning tree tanpa mempedulikan bobot, DFS atau BFS dapat menghasilkan pohon rentang dengan mudah.</p> <pre>function dfsSpanningTree(g, start): stack [start] visited {} treeEdges [] while stack not empty: v stack.pop() if v not in visited: visited.add(v) for each neighbor u of v: if u not in visited: treeEdges.append((v,u)) stack.push(u) return treeEdges </pre> </section> <section class="section"> <h2>Minimum Spanning Tree (MST)</h2> <p>Ketika setiap edge memiliki bobot, <em>minimum spanning tree</em> adalah spanning tree dengan total bobot paling kecil. MST sangat berguna dalam:</p> <ul> <li>Desain jaringan telekomunikasi (meminimalkan biaya kabel).</li> <li>Perancangan jaringan listrik.</li> <li>Clustering data (algoritma singlelink).</li> </ul> <p>Contoh klasik: graf berikut mempunyai tiga MST dengan total bobot 8.</p> <img src="https://i.imgur.com/0cT3XQZ.png" alt="Contoh MST" class="image"> </section> <section class="section"> <h2>Aplikasi Spanning Tree dalam Jaringan Komputer</h2> <p>Protokol <strong>Spanning Tree Protocol (STP)</strong> dikembangkan oleh IEEE 802.1D untuk mencegah looping pada jaringan Ethernet yang memiliki banyak bridge atau switch.</p> <table> <thead> <tr><th>Fitur</th><th>Deskripsi</th></tr> </thead> <tbody> <tr><td>Root Bridge</td><td>Pemilih utama yang menjadi pusat spanning tree.</td></tr> <tr><td>Port States</td><td>Port dapat berada dalam status blocking, listening, learning, atau forwarding.</td></tr> <tr><td>BPDU</td><td>Bridge Protocol Data Unit, paket yang dipertukarkan untuk membangun tree.</td></tr> <tr><td>Rapid STP (RSTP)</td><td>Versi lebih cepat (IEEE 802.1w) yang mengkonvergensi dalam hitungan milidetik.</td></tr> </tbody> </table> <p>Dengan STP, jaringan tetap dapat beroperasi meski terdapat banyak jalur redundan, karena hanya satu jalur yang diaktifkan secara logis.</p> </section> <section class="section"> <h2>Spanning Tree dalam Algoritma Lain</h2> <ul> <li><strong>Graf Planar</strong> Dual graph dari spanning tree membantu menemukan facecovering.</li> <li><strong>Algoritma Approximation</strong> Dalam masalah Traveling Salesman, MST memberikan batas bawah (1/2) untuk jarak optimal.</li> <li><strong>Network Reliability</strong> Menghitung jumlah spanning tree membantu menilai keandalan jaringan.</li> </ul> </section> <section class="section"> <h2>Contoh Implementasi Sederhana (JavaScript)</h2> <p>Berikut contoh kode yang menghasilkan sebuah spanning tree menggunakan BFS pada graf tak berarah.</p> <pre>function bfsSpanningTree(adjList, start) { const visited = new Set(); const queue = [start]; const treeEdges = []; while (queue.length) { const v = queue.shift(); visited.add(v); for (const u of adjList[v]) { if (!visited.has(u)) { visited.add(u); treeEdges.push([v, u]); queue.push(u); } } } return treeEdges;}// contoh penggunaanconst graph = { A: ['B','C'], B: ['A','D','E'], C: ['A','F'], D: ['B'], E: ['B','F'], F: ['C','E']};console.log(bfsSpanningTree(graph,'A')); </pre> </section> <section class="section"> <h2>Kesimpulan</h2> <p>Spanning tree merupakan konsep fundamental dalam teori graf yang menghubungkan semua simpul tanpa membentuk siklus. Dengan beragam algoritma dari Kruskal, Prim, hingga BFS/DFS kita dapat menghasilkan spanning tree yang memenuhi kebutuhan khusus, seperti minimisasi bobot atau kecepatan eksekusi. Aplikasi praktisnya meliputi desain jaringan, perencanaan infrastruktur, dan banyak bidang ilmu komputer lainnya. Memahami cara kerja dan pemilihan algoritma yang tepat adalah kunci untuk menyelesaikan masalah optimasi yang melibatkan graf besar.</p> </section>