Sebagai seorang "bekas" mahasiswa Matematika, saya tahu bagaimana rumitnya membuat rute paling efektif suatu jalan. Bagi mahasiswa Matematika yang menggeluti graph mungkin tahu jelas bagaimana hitungan-hitungannya. Graph adalah himpunan benda-benda yang disebut vertex yang dihubungkan oleh edge. Biasanya, graph digambarkan oleh kumpulan beberapa titik (disebut vertex) yang dihubungkan oleh garis-garis (disebut edge). Dari satu titik ke titik lain dihubungkan oleh garis yang memiliki nilai atau beban.
Membahas teori graph ini
butuh waktu yang lumayan menyita kegiatan penting semacam tidur. Untuk dasar
dari teori graph saja mesti mengambil kuliah Matematika Diskrit 3 sks, belum
lagi mata kuliah Teori Graph yang juga 3 sks. Namun tenang kawan, di sini akan
saya jelaskan aplikasi sederhana dari teori ini. Sebenarnya banyak sekali problem di kehidupan ini yang bisa
diselesaikan dengan teori graph. Satu contoh yang akan saya ambil adalah
pemilihan rute terpendek dari suatu graph (The shortest Path Problem).
Perhatikan peta di bawah
ini. Misalkan si A akan berangkat dari Kota Brebes (sebagai titik awal) menuju
Kota Wonogiri (sebagai titik akhir). Perhatikan bahwa antara dua kota tersebut
terdapat banyak kota yang antara satu kota ke kota lain dihubungkan dengan
garis (edge).