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

Video ini membahas graf sebagai model dalam Matematika Diskrit, terutama dalam konteks jaringan komunikasi dan transportasi. Graf digunakan untuk merepresentasikan panggilan telepon, jaringan internet, dan rute transportasi pesawat terbang. Selain itu, graf juga digunakan untuk memodelkan turnamen seperti turnamen round robin dan single elimination. Dalam sifat graf, terdapat handshaking theorem yang menyatakan jumlah derajat simpul sama dengan dua kali jumlah busur dalam graf tak berarah. Handshaking theorem mirip dengan konsep bersalaman, di mana setiap salaman melibatkan dua orang.

Model yang berikutnya adalah jaringan komunikasi, itu bisa digambarkan juga dalam bentuk graf.

Jadi misalnya kita lihat call graph atau graf yang merepresentasikan panggilan telpon.

Jadi kalau kita melakukan panggilan telpon itu kan biasanya dari saya menelpon seseorang.

Jadi satu arah kan, enggak terus bolak-balik.

Nah itu digambarkan dengan satu busur yang berarah.

Jadi ada berapa banyak panggilan telpon itu nanti bisa dilihat,

berapa banyak saya menelpon dalam satu hari misalnya,

berapa banyak saya terima telpon, itu bisa dilihat.

Tapi kalau kita memandangnya sebagai berapa kali kita berkomunikasi kan tidak peduli siapa yang telpon.

Saya yang telpon atau saya yang menerima telpon itu dianggap sebagai satu komunikasi.

Nah karena lihatnya komunikasi kita tidak memerlukan arah,

jadi itu selalu dua arah kalau komunikasi.

Sehingga gambarnya nanti grafnya itu akan berbentuk graf yang tak berarah.

Kalau kita lihat graf sebagai model untuk jaringan yang lain,

misalnya jaringan informasi, itu ada yang kita sebut sebagai web graf.

Jadi graf yang merepresentasikan jaringan internet.

Kita tahu bahwa makin hari orang-orang yang terkoneksi internet itu semakin banyak.

Nah itu kalau direpresentasikan jaringan yang ada itu akan sangat rapat sekali.

Kita sebut dia sebagai graf yang padat, dance graf.

Nah ini salah satu bentuk representasi dari web graf.

Yang contoh lain adalah contoh citation graf.

Nah kalau citation graf itu artinya itu adalah graf yang merepresentasikan

kalau kita menuliskan suatu artikel ilmiah itu biasanya kan harus ada rujukannya.

Jadi misalnya kita mau menjelaskan tentang graf.

Kita akan memberikan definisi graf itu, nanti harus disebutkan definisinya itu dari mana.

Kalau misalnya dari buku Rosen, ya kita sebutkan dari buku Rosen.

Itu artinya saya misalnya menuliskan artikel ilmiah tersebut, mensitasi Rosen.

Tapi Rosen kan tidak mensitasi saya, jadi grafnya itu adalah graf berarah.

Dan harusnya saya tidak mensitasi artikel yang saya tulis.

Dan kita juga tidak punya busur berganda.

Jadi untuk citation graf itu nanti grafnya adalah tak berarah dan juga graf sederhana.

Dan yang paling sering mungkin kita temukan adalah graf sebagai model dari jaringan transportasi.

Misalnya di sini menggambarkan rute pesawat dari satu maskapai tertentu.

Nah kita lihat di sini dari Jakarta ke Makassar, ada nggak rutenya?

Oh ternyata ada nih di sini rute dari Jakarta-Makassar langsung.

Kemudian kalau misalnya ke Menado, ke Menado ada nggak?

Beberapa tahun yang lalu kalau kita ke Menado harus mampir ke Makassar dulu, jadi nggak ada yang langsung.

Nah kalau di sini kita lihat saya mau ke Timur-Timur, ternyata nggak ada pesawat langsung ke sana.

Karena tidak ada busur yang menghubungkan dari Jakarta ke daerah Timur-Timur dimanapun.

Sehingga kalau kita mau ke sana kita harus cari lagi mungkin pakai maskapai yang berbeda.

Jaringan transportasi contoh yang berikutnya adalah rute jalan.

Kalau sekarang kita pakai Google Map, nggak usah lihat peta.

Saya mau dari tempat yang sekarang mau ke Bandung misalnya, kita tinggal klik aja Google Map nanti dia akan mengarahkan.

Tapi kalau zaman dulu itu sebelum Google Map itu secanggih sekarang kita harus lihat peta nih.

Kalau saya mau dari Jakarta ke Jogja lewat mana sih yang dimungkinkan?

Kemudian nanti ada informasi nih jalur ini padat, jalur ini tidak padat dan seterusnya.

Jadi kita akan memilih jalurnya yang mana.

Biasanya di peta ini juga ada keterangan tentang misalnya pembensin ada di mana aja.

Tapi sekarang bentuk peta ini tidak terlalu digunakan lagi karena kita menggunakan Google Map.

Tapi kalau Google Map suatu saat tiba-tiba crash atau down maka peta ini bisa kita gunakan.

Grafnya itu menggambarkan jalan mana yang ada dari satu kota ke kota yang lain.

Jadi bisa lewat mana saja itu direpresentasikan di peta ini.

Contoh yang berikutnya lagi adalah memodelkan turnamen.

Jadi turnamen ataupun pertandingan itu ada yang disebut turnamen round robin.

Misalnya disini ada 6 tim nanti aturan akan bertanding ke tim yang mana itu dilihat dari gerah berarah ini.

Jadi kalau menurut gerah berarah ini tim 1 nanti akan bertanding ke tim 2, tim 2 ke tim 3 dan seterusnya.

Misalnya dari semua tim itu kita lihat pasti ada hubungannya, ada busur yang berarah di situ.

Tapi ada juga yang istilahnya aturannya itu pakai single elimination, eliminasi tunggal.

Jadi misalnya disini Stanford sama Shafir itu nanti akan bertanding,

yang menang misalnya Stanford nanti ditandingkan dengan dari Oklahoma sama Kentucky.

Kalau yang menang Oklahoma berarti nanti Stanford itu akan melawan Oklahoma dan seterusnya.

Nanti kita lihat disini dari dua arah nanti finalnya ada kalau di gambar ini adalah antara Connecticut dan Stanford.

Itu adalah beberapa contoh di mana si grafnya itu bisa digunakan sebagai model.

Sekarang kalau sifatnya, jadi kalau kita lihat graf itu ada sifat yang sederhana yang kita sebut sebagai handshaking theorem.

Jadi kalau kita punya suatu graf tak berarah G sama dengan VE dan punya M busur,

maka kalau kita jumlahkan semua derajat dari simpul V,

jumlahnya akan sama dengan dua kali saiznya atau dua kali banyaknya busur.

Ini kita sebut handshaking theorem karena begitu kita punya, karena ini hitungnya pakai derajat ya.

Jadi kalau kita punya simpul X ke simpul Y dihubungkan dengan misalnya busur E,

maka busur E ini dihitung pada saat kita menghitung derajatnya X juga dihitung pada saat kita menghitung derajatnya Y.

Jadi E itu dihitung dua kali makanya disini keluarnya 2M.

Itu sama dengan kalau kita bersalaman, satu kali salaman itu melibatkan dua orang.

Jadi makanya disini teoremanya kita sebut sebagai teorem bersalaman atau handshaking theorem.