Ini merupakan kisah nyata. Pada abad ke-18, di Prussia, terdapat sebuah kota yang bernama Königsberg. Kota ini sekarang bernama Kaliningrad, Russia. Beberapa area kota Königsberg dipisahkan oleh sungai Pregel sehingga untuk mencapai area kota yang lainnya penduduk harus berjalan melalui jembatan yang jumlahnya ada tujuh.
Bertahun-tahun kemudian, timbul sebuah pertanyaan pada penduduk Königsberg. Apakah bisa melalui semua jembatan hanya dengan satu kali jalan? Seorang matematikawan asal Swiss, Leonhard Euler, berhasil memecahkan teka-teki ini dengan menggunakan teori graf. Sebelum kita memecahkannya, mari kita belajar sedikit mengenai teori graf dan istilah-istilahnya.
Teori graf adalah studi tentang grafik yang digunakan untuk memodelkan hubungan antarobjek. Pada teori graf, terdapat titik, garis, dan banyaknya garis yang berhubungan dengan titik, yang disebut sebagai derajat.
Untuk lebih jelasnya, perhatikan contoh berikut ini.
Graf di atas memiliki:
- 5 titik, yaitu A, B, C, D dan E.
- 8 garis, yaitu AB, BC, CD, DA, AE, BE, AC dan BD.
- Titik A dan B memiliki derajat 4.
- Titik C dan D memiliki derajat 3.
- Titik E memiliki derajat 2.
Salah satu konsep penting dalam teori graf adalah mengenai lintasan Euler. Sebuah graf disebut memiliki lintasan Euler apabila graf tersebut mempunyai titik dengan derajat ganjil yang banyaknya kurang dari tiga. Pada contoh graf A hingga E, kita bisa analisis mana graf yang memiliki lintasan Euler dan mana yang tidak.
Silakan untuk graf D dan graf E dikerjakan sendiri ya! :)
Sekarang mungkin ada yang bertanya-tanya, sebenarnya untuk apa mempelajari lintasan Euler ini? Jawabannya, apabila sebuah graf memiliki lintasan Euler, graf tersebut ternyata dapat digambar hanya dalam satu kali tarikan pensil! Wow! Benarkah? Contohnya adalah graf A, kita dapat menggambar graf A dengan satu kali tarikan pensil menggunakan lintasan a-c-b-d-c-b-a-d. Lintasannya sendiri dapat bermacam-macam. Cobalah sekarang temukan lintasan satu kali tarikan pensil untuk graf B! Nah, dengan pengetahuan ini kita sudah siap untuk memecahkan teka-teki ini sebagaimana Euler memecahkannya 300 tahun yang lalu.
Let’s start!
Pertama-tama, kita sederhanakan gambar jembatan Königsberg.
Kedua, gambar jembatan Königsberg dapat disederhanakan lagi menjadi bentuk graf.
Ketiga, setelah disederhanakan menjadi bentuk graf, dapat dengan mudah diketahui terdapat:
- 4 titik, yaitu A, B, C, dan D,
- 4 titik berderajat ganjil, yaitu A, B, C, dan D,
- tidak ada titik yang berderajat genap.
Dengan demikian, dapat diambil sebuah kesimpulan bahwa jembatan Königsberg ini bukanlah lintasan Euler sehingga tidak dapat dilintasi hanya dengan satu kali jalan. Riddle solved!
Bahan bacaan:
- http://www.mathsisfun.com/activity/seven-bridges-konigsberg.html
- http://en.wikipedia.org/wiki/Graph_theory
- http://www.ctl.ua.edu/math103/euler/howcanwe.htm
- http://www.contracosta.edu/legacycontent/math/konig.htm
- http://www.ctl.ua.edu/math103/euler/historic.htm
Penulis:
Reyna Marsya Quita, mahasiswa master di Jurusan Matematika, Universitas Brawijaya, Malang.
Kontak: reynaquita2905(at)gmail.com
