Sejarah Graf

Menurut catatan sejarah, masalah jembatan Königsberg adalah masalah yang pertama kali menggunakan graf (tahun 1736). Di kota Königsberg (sebelah timur Prussia, Jerman sekarang), sekarang bernama kota Kaliningrad, terdapat sungai Pregal yang mengalir mengitari pulau Kneiphof lalu bercabang menjadi dua buah anak sungai.

Ada tujuh buah jembatan yang menghubungkan daratan yang dibelah oleh sungai tersebut (Gambar 8.2(a)). Masalah jembatan Königsberg adalah: apakah mungkin melalui ketujuh buah jembatan itu masing-masingtepat satu kali, dan kembali lagi ke tempat semula? Sebagian penduduk kota sepakat bahwa memang tidakmungkin melalui setiap jembatan itu hanya sekali dan kembali lagi ke tempat asal mula keberangkatan, tetapi mereka tidak dapat menjelaskan mengapa demikian jawabannya, kecuali dengan cara coba-coba. Tahun 1736, seorang matematikawan Swiss, L.Euler, adalah orang pertama yang berhasil menemukan jawaban masalah itu dengan pembuktian yang sederhana. Ia memodelkan masalah ini ke dalam graf. Daratan (titiktitik yang dihubungkan oleh jembatan) dinyatakannya sebagai titik (noktah) –yang disebut simpul (vertex)- dan jembatan dinyatakan sebagai garis –yang disebut sisi (edge). Setiap titik diberi label huruf A, B, C, dan D. Graf yang dibuat oleh Euler diperlihatkan pada Gambar 8.2(b). Jawaban yang dikemukakan oleh Euler adalah: orang tidak mungkin melalui ketujuh jembatan itu masingmasing satu kali dan kembali lagi ke tempat asal keberangkatan jika derajat setiap simpul tidak seluruhnya genap. Yang dimaksud dengan derajat adalah banyaknya garis yang bersisian dengan noktah. Sebagai contoh, simpul C memiliki derajat 3 karena ada tiga buah garis yang bersisian dengannya, simpul B dan D juga berderajat dua, sedangkan simpul A berderajat 5. Karena tidak semua simpul berderajat genap, maka tidak mungkin dilakukan perjalananan berupa sirkuit (yang dinamakan dengan sirkuit Euler) pada graf tersebut. Kelak kita akan membahas lebih mendalam mengenai derajat dan sirkuit pada upabab selanjutnya.