Prof. Dra. Kiki Ariyanti Sugeng, M.Si., Ph.D.

Video ini membahas tentang konsep Spanning Tree atau pohon rentangan dalam Matematika Diskrit. Spanning Tree merupakan subgraf dari graf G yang berbentuk pohon, menghubungkan semua simpul dari G dengan menggunakan busur yang diperlukan saja. Terdapat beberapa cara untuk mengkonstruksi Spanning Tree, yaitu Building Up Method dengan memilih busur satu per satu tanpa membentuk sirkuit, dan Cutting Down dengan menghilangkan busur yang membentuk lingkaran hingga membentuk pohon. Konsep ini penting karena setiap graf terhubung jika memiliki pohon rentangan, dan dapat memiliki lebih dari satu pohon rentangan.

Nah, di dalam suatu masalah yang bisa digambarkan dalam bentuk graf itu seringkali kita tidak membutuhkan semua busur ya,

jadi contohnya kalau suatu graf itu menggambarkan aliran listrik dari setiap rumah,

jadi kalau kita misalkan rumahnya seperti yang digambarkan dalam graf G ini

jadi kita punya VW XYZ, jadi ada lima rumah.

Nah, aliran listrik itu kan harus dialirkan dari rumah ke rumah,

itu tidak perlu dari setiap rumah itu dihubungkan seperti ini,

atau misalnya aliran gas atau aliran air,

jadi kalau misalnya semuanya dipasang kabel, kabelnya kan makin panjang,

jadi supaya semua itu teraliri listrik atau teraliri air gitu ya,

itu kita berusaha untuk membuat jaringannya itu seoptimal mungkin gitu ya,

jadi misalnya kalau kita lihat gambar yang kedua, busur VW, VY dan BY itu kita hapus,

kita akan dapat bentuk seperti ini subgrafnya,

dan dari gambar yang kedua ini kita pastikan bahwa semua simpul itu bisa dihubungkan,

jadi antara dua simpul sembarang itu ada lintasannya,

kebetulan ini grafnya berbentuk lintasan.

Nah, bentuk yang seperti ini kita sebut sebagai spanning tree,

atau dalam bahasa Indonesia kita suka sebut sebagai pohon rentangan,

berbentuk pohon dan memuat semua simpul dari G,

jadi itu kita ambil busur-busur yang perlu saja,

dengan tujuan semua simpul itu terhubung satu dengan yang lain.

Nah, tapi spanning tree atau pohon rentangan ini tidak tunggal,

kita bisa mendapatkan misalnya di sini spanning tree yang kedua dan yang ketiga,

jadi tiga contoh spanning tree ini berbentuk tree,

menghubungkan semua simpul yang ada di graf G,

tapi tidak semua busur itu kita masukkan.

Nah, sifatnya itu dirangkum dalam satu teorema,

karena suatu graf sederhana itu terhubung jika dan hanya jika G mempunyai pohon rentangan,

jadi kita lihat pohon rentangan tadi kan menghubungkan semua simpul,

dan kalau grafnya terhubung kita bisa membuat pohon rentangannya,

misalnya dengan cara kita hilangkan busur-busur yang membentuk sirkuit atau lingkaran.

Nah, karena setiap graf terhubung itu memuat suatu spanning tree atau pohon berarah,

maka kita bisa mempunyai lebih dari satu kan tadi,

misalnya graf Peterson itu punya 2000 pohon rentangan itu tanpa labelnya,

Nah, sekarang bagaimana cara mengkonstruksi spanning tree tadi?

jadi yang kita lakukan adalah pilih busur dari graf satu per satu,

sehingga tidak ada sirkuit yang terbentuk,

yang WY ini tidak boleh saya ambil karena nanti akan membentuk lingkaran,

sehingga nanti kita akan dapat spanning tree yang pertama.

tapi dengan cara memilih busurnya itu berbeda,

Terus ada lagi yang kita sebut sebagai Cutting Down,

kalau Cutting Down ini kita cari di dalam grafnya itu,

ada subgraf yang berbentuk lingkaran tidak?

Kalau ada kita buang salah satu busurnya,

terus diulangi sampai kita nanti membentuk pohon,

misalnya ini kan VWY itu membentuk lingkaran,

terus saya lihat VZY itu juga membentuk lingkaran persegi tiga,

begitu juga VYX itu juga saya buang misalnya VY,

misalnya yang terakhir itu boleh WY, YX, XW,

jadi nanti kita akan dapat yang berbeda-beda.

Kalau dengan cara yang tadi saya sebutkan,

maka kita nanti akan punya Spanning Tree seperti ini,