Pohon Rentang dan Pohon Rentang Minimum

Dalam tutorial ini, Anda akan belajar tentang spanning tree dan minimum spanning tree dengan bantuan contoh dan gambar.

Sebelum kita belajar tentang merentang pohon, kita perlu memahami dua grafik: grafik tidak berarah dan grafik terhubung.

Sebuah grafik diarahkan adalah grafik di mana tepi tidak menunjuk dalam arah (yaitu. Ujung-ujungnya dua arah).

Grafik Tidak Berarah

Sebuah graf terhubung adalah grafik yang selalu ada jalur dari simpul untuk setiap vertex lainnya.

Grafik Terhubung

Pohon merentang

Pohon rentang adalah sub-grafik dari grafik terhubung yang tidak diarahkan, yang mencakup semua simpul grafik dengan jumlah sisi minimum yang memungkinkan. Jika sebuah simpul terlewatkan, maka itu bukan pohon rentang.

Tepi mungkin atau mungkin tidak memiliki bobot yang ditetapkan padanya.

Jumlah total pohon merentang dengan nsimpul yang dapat dibuat dari grafik lengkap sama dengan .n(n-2)

Jika kita punya n = 4, jumlah maksimum pohon yang merentang adalah sama dengan . Dengan demikian, 16 pohon merentang dapat dibentuk dari grafik lengkap dengan 4 simpul.44-2 = 16

Contoh Pohon Rentang

Mari kita pahami spanning tree dengan contoh di bawah ini:

Biarkan grafik aslinya menjadi:

Grafik normal

Beberapa pohon merentang yang mungkin dapat dibuat dari grafik di atas adalah:

Pohon bentang Pohon bentang Pohon bentang Pohon bentang Pohon bentang Pohon bentang pohon bentang

Pohon Rentang Minimum

Pohon bentang minimum adalah pohon bentang yang jumlah bobot tepinya serendah mungkin.

Contoh Pohon Rentang

Mari kita pahami definisi di atas dengan bantuan contoh di bawah ini.

Grafik awalnya adalah:

Grafik berbobot

Pohon merentang yang mungkin dari grafik di atas adalah:

Pohon merentang minimum - 1 Pohon bentang minimum - 2 Pohon bentang minimum - 3 Pohon bentang minimum - 4

Pohon bentang minimum dari pohon bentang di atas adalah:

Pohon rentang minimum

Pohon rentang minimum dari grafik ditemukan menggunakan algoritme berikut:

1. Algoritma Prim
2. Algoritma Kruskal

Merentang Aplikasi Pohon

• Protokol Perutean Jaringan Komputer
• Analisis Cluster
• Perencanaan Jaringan Sipil

Aplikasi Pohon Rentang Minimum

• Untuk menemukan jalur di peta
• Merancang jaringan seperti jaringan telekomunikasi, jaringan air bersih, dan jaringan listrik.