Struktur Data & Algoritma - Pohon Rentang

Pohon merentang adalah himpunan bagian dari Grafik G, yang memiliki semua simpul yang ditutupi dengan jumlah tepi seminimal mungkin. Karenanya, pohon rentang tidak memiliki siklus dan tidak dapat diputuskan ..

Dengan definisi ini, kita dapat menarik kesimpulan bahwa setiap Grafik G yang terhubung dan tidak diarahkan memiliki setidaknya satu pohon rentang. Grafik yang terputus tidak memiliki pohon rentang, karena tidak dapat direntang ke semua simpulnya.

Kami menemukan tiga pohon rentang dari satu grafik lengkap. Grafik tidak terarah lengkap dapat memiliki maksimumn^n-2 jumlah pohon merentang, di mana nadalah jumlah node. Dalam contoh yang dialamatkan di atas,n is 3, karenanya 3³⁻² = 3 rentang pohon dimungkinkan.

Properti Umum Spanning Tree

Kami sekarang memahami bahwa satu grafik dapat memiliki lebih dari satu pohon rentang. Berikut adalah beberapa properti dari pohon rentang yang terhubung ke grafik G -

Grafik terhubung G dapat memiliki lebih dari satu pohon rentang.
Semua pohon rentang yang mungkin dari grafik G, memiliki jumlah sisi dan simpul yang sama.
Pohon rentang tidak memiliki siklus apa pun (loop).
Menghapus satu sisi dari pohon rentang akan membuat grafik terputus, yaitu pohon rentang minimally connected.
Menambahkan satu tepi ke pohon rentang akan membuat sirkuit atau lingkaran, yaitu pohon rentang maximally acyclic.

Properti Matematika Pohon Rentang

Spanning tree memiliki n-1 tepi, dimana n adalah jumlah node (simpul).
Dari grafik lengkap, dengan menghapus maksimum e - n + 1 tepi, kita dapat membangun pohon rentang.
Grafik yang lengkap bisa maksimal n^n-2 jumlah pohon merentang.

Dengan demikian, kita dapat menyimpulkan bahwa pohon merentang adalah himpunan bagian dari Grafik G yang terhubung dan grafik yang terputus tidak memiliki pohon rentang.

Penerapan Spanning Tree

Spanning tree pada dasarnya digunakan untuk mencari jalur minimum untuk menghubungkan semua node dalam sebuah grafik. Penerapan umum pohon merentang adalah -

Civil Network Planning
Computer Network Routing Protocol
Cluster Analysis

Mari kita pahami ini melalui contoh kecil. Pertimbangkan, jaringan kota sebagai grafik yang sangat besar dan sekarang berencana untuk menggunakan saluran telepon sedemikian rupa sehingga dalam saluran minimum kita dapat terhubung ke semua node kota. Di sinilah pohon bentang muncul.

Minimum Spanning Tree (MST)

Dalam grafik berbobot, pohon bentang minimum adalah pohon bentang yang memiliki bobot minimum daripada semua pohon bentang lain dari grafik yang sama. Dalam situasi dunia nyata, bobot ini dapat diukur sebagai jarak, kemacetan, beban lalu lintas, atau nilai arbitrer apa pun yang ditunjukkan ke tepi.