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

Video ini membahas tentang masalah Spanning Tree Minimal dalam Matematika Diskrit dengan fokus pada konsep pohon. Graf berbobot digunakan untuk mencari pohon rentangan minimum dengan panjang kabel atau biaya seminimal mungkin. Konsep subgraf dan bobot busur juga dijelaskan sebagai faktor penentu dalam mencari solusi optimal. Melalui contoh kasus pengiriman barang, penyelesaian masalah spanning tree minimal dilakukan dengan memilih busur terhubung dengan biaya seminimal mungkin, menghasilkan pohon rentangan dengan total biaya pengiriman $3.600.

Kalau grafnya itu merepresentasikan, misalnya busurnya itu adalah tadi ya kabel listrik.

Nah kabel listrik itu kan kalau kita mau bikin dia optimal kan bisa dicari supaya kabel listriknya itu panjangnya seminimal mungkin.

Untuk menentukan si kabel listrik itu, si busurnya kita kasih angka, makanya itu kita sebut sebagai graf berbobot.

Jadi busurnya diberi bobot itu biasanya biayanya, panjang kabel, panjang pipa dan seterusnya.

Kalau kita misalnya mempunyai subgraf H, bobot dari subgraf itu adalah banyaknya atau jumlah bobot-bobot dari busur yang ada di graf H tersebut.

Kalau kita bicarakan pohon rentangan, kita juga bisa mencari pohon rentangan minimum.

Jadi artinya kalau tadi penamanya menggambarkan aliran listrik, kita cari pohon rentangannya itu yang panjang kabelnya seminimal mungkin.

Kalau biaya berarti biaya seminimal mungkin, tapi ada kalanya juga kalau dia menyatakan sesuatu yang positif keuntungan kita mengambilnya yang sebanyak mungkin.

Jadi masalah spanning tree minimal ini kita mencari spanning tree atau pohon rentangan yang minimal dari graf yang terhubung dan berbobot.

Kita lihat contohnya di sini ada setiap busurnya dikasih biaya pengiriman barang mungkin.

Dan kalau kita cari di sini busurnya itu kita cari yang terhubung tapi seminimal mungkin.

Jadi kalau kita lihat misalnya pilihannya diambil yang paling kecil di sini $700 itu antara Chicago dan Atlanta itu kita pilih dulu.

Yang berikutnya lagi dari Atlanta ke New York yang $800 itu kita pilih.

Setelah itu kita tidak bisa milih angka berikutnya itu adalah Chicago New York yang $1.000 tapi kita tidak perlu milih itu karena Chicago dan New York itu sudah terhubung melalui Atlanta.

Kemudian kita teruskan pemilih untuk supaya menghubungkan ke kota-kota yang lain misalnya kita ambil Chicago dan San Francisco di sini $1.200.

Dan yang terakhir San Francisco ke Denver jadi nanti kita akan mendapat suatu pohon rentangan dengan total biaya pengirimannya itu $3.600.