Pokok Spanning dan Pokok Spanning Minimum

Dalam tutorial ini, anda akan belajar mengenai pokok rentang dan pokok rentang minimum dengan bantuan contoh dan angka.

Sebelum kita belajar mengenai merangkumi pokok, kita perlu memahami dua graf: grafik tidak langsung dan graf bersambung.

Sebuah graf tak berarah adalah graf di mana tepi tidak menunjukkan mana-mana arah (iaitu. Tepi adalah dwiarah).

Graf Tidak Terarah

A graf berkait adalah graf di mana sentiasa ada laluan dari mercu untuk sebarang mercu lain.

Graf Bersambung

Pokok rentang

Pohon yang merangkumi adalah sub-grafik dari grafik yang dihubungkan yang tidak diarahkan, yang merangkumi semua bucu grafik dengan bilangan tepi minimum yang mungkin. Sekiranya bucu terlepas, maka itu bukan pokok rentang.

Tepi mungkin atau tidak mempunyai bobot yang diberikan kepadanya.

Jumlah pokok rentang dengan nbucu yang dapat dibuat dari graf lengkap adalah sama dengan .n(n-2)

Sekiranya ada n = 4, bilangan maksimum pokok merangkumi adalah sama dengan . Oleh itu, 16 pokok rentang dapat dibentuk dari graf lengkap dengan 4 bucu.44-2 = 16

Contoh Pokok Spanning

Mari fahami pokok rentang dengan contoh di bawah:

Biarkan graf asal:

Graf biasa

Beberapa kemungkinan pokok rentang yang dapat dibuat dari grafik di atas adalah:

Pokok rentang A pokok rentang A pokok rentang A pokok rentang A pokok rentang A pokok rentang

Pokok Rentang Minimum

Pokok rentang minimum adalah pokok rentang di mana jumlah berat tepinya minimum mungkin.

Contoh Pokok Spanning

Mari kita fahami definisi di atas dengan bantuan contoh di bawah.

Grafik awal adalah:

Graf berwajaran

Pokok yang mungkin merangkumi dari graf di atas adalah:

Pokok rentang minimum - 1 Pohon rentang minimum - 2 Pohon rentang minimum - 3 Pohon rentang minimum - 4

Pokok rentang minimum dari pokok rentang di atas adalah:

Pokok rentang minimum

Pokok rentang minimum dari grafik dijumpai menggunakan algoritma berikut:

1. Algoritma Prim
2. Algoritma Kruskal

Aplikasi Pokok Spanning

• Protokol Penghalaan Rangkaian Komputer
• Analisis Kluster
• Perancangan Rangkaian Awam

Aplikasi Pokok Spanning Minimum

• Untuk mencari jalan di peta
• Untuk merancang rangkaian seperti rangkaian telekomunikasi, rangkaian bekalan air, dan grid elektrik.