Desember 09, 2011

Tujuh Jembatan Königsberg


Mari kita sejenak berkunjung ke Russia. Ke sebuah kota kecil yang menjadi bagian dari sejarah dunia Matematika, khususnya Teori Graf. Kali ini kita akan berkunjung ke kota Königsberg di Prusia (sekarang bernama Kaliningrad, Rusia). Wilayah Königsberg dahulu adalah wilayah kerajaan Jerman, terletak kedua sisi Sungai Pregel, dan termasuk dua pulau besar yang dihubungkan satu sama lain dan daratan oleh tujuh jembatan.

Kota Königsberg saat ini.  Königsberg berganti nama menjadi  Kaliningrad sejak 1946, untuk menghormati Mikhail Ivanovich Kalinin (1875-1946).  Kaliningrad bearada diantara Polandia dan Lithuania, dihuni sekitar 430 ribu orang.

Tujuh Jembatan Königsberg adalah masalah historis penting dalam matematika. Karena, berkat teka-teki ini, muncul sebuah konsep baru dalam matematika yang tidak lagi menjadi ilmu tentang menghitung dan mengukur. Beginilah teka-teki yang terkenal itu.

Peta Königsberg Kuno. Daerah yang diberi warna biru adalah Sungai Pregel,
dan warna merah dalam gambar menunjukan  jembatan

Pada tahun 1255, Ksatria Teutonik mendirikan benteng di sebuah kota di mana sungai Pregel bercabang, dan memberi nama Königsberg.

Seiring berjalannya waktu, jembatan-jembatan dibangun melintasi berbagai cabang sungai seperti gambar di atas untuk memudahkan akses ke tiap-tiap daerah di Königsberg.

Suatu hari, warga Königsberg mengajukan pertanyaan: Apakah mungkin berjalan melintasi semua jembatan, tetapi hanya boleh melintasi jembatan-jembatan tersebut sekali saja?



Dapatkah kamu menemukan sebuah rute yang melewati semua jembatan,
tetapi setiap jembatan hanya boleh dilalui sekali saja, tidak boleh berulang?

Leonhard Euler

Masalahnya adalah menemukan sebuah rute perjalanan yang akan menyeberangi SEMUA JEMBATAN masing-masing hanya sekali. Jembatan yang sudah dilewati TIDAK BOLEH DILEWATI KEMBALI, dan pulau-pulau yang ada tidak bisa dicapai selain melalui jembatan.

Masing-masing jembatan menyeberangi pulau sepenuhnya setiap kali, tidak bisa berjalan setengah jalan di jembatan dan kemudian berbalik dan kemudian menyeberangi separuh lainnya dari sisi lain.


Sejarah mencatat, masalah ini telah diselesaikan oleh matematikawan berkebangsaan Jerman bernama Leonhard Euler pada tahun 1736, dan saat itulah lahir konsep matematika yang baru. Selamat datang, Teori Graf!