Teka-Teki Jembatan Konigsberg

A.      Latar Belakang

Graf merupakan salah satu cabang ilmu matematika yang merepresentasikan objek – objek diskrit dan hubungan antara objek – objek tersebut. Representasi visual dari graf adalah dengan menyatakan obyek dengan noktah dan hubungan antara objeknya dengan garis. Untuk selanjutnya kita sebut noktah pada graf sebagai simpul (vertex) dan garis pada graf sebagai sisi (edge).

Konigsberg, sebuah kota di bagian utara Jerman, memiliki  sebuah  kisah  terkenal yang memberikan pengaruh besar pada kehidupan seorang  bernama  Euler  dan  sejarah perkembangan teori Graf. Sungai Pregel yang melalui Konigsberg membagi wilayah daratan pada kota tersebut menjadi empat bagian. Tujuh buah jembatan dibangun di atas sungai tersebut pada bagian yang memungkinkan untuk bepergian antar keempat wilayah tersebut. Pada abad ke-17, warga Konigsberg gemar berjalan di tepi sungai, hingga  akhirnya  beberapa  dari  mereka memikirkan apakah mungkin untuk berjalan di Konigsberg dan melalui setiap jembatan hanya sekali. Hal inilah yang kemudian disebut Teka-Teki Jembatan Konigsberg yang tidak dapat terselesaikan untuk waktu yang cukup lama dan menjadi terkenal di seluruh negeri.

Teka-teki tersebut menarik perhatian Euler, yang diyakini ketika itu berada di St. Petersburg.  Ia kemudian meneliti  bahwa  kasus  tersebut  dapat direpsersentasikan dalam sebuah diagram Gbr1. Setelah  sekian  banyak  kegagalan  warga Konigsberg untuk menemukan cara melalui seluruh jembatan hanya sekali, hingga akhirnya pada tahun 1736 masalah tersebut dijadikan sebuah kasus matematika dan kemustahilan untuk menyelesaikan teka-teki tersebut terbukti.

B.       Pembahasan

Dalam kasus jembatan Konigsberg huruf C akan muncul sebanyak tiga kali (BAC, DAC, BDC) karena terdapat lima jembatan yang menyusun jalan menuju C. Kemudian, karena tiga jembatan menyusun jalan menuju A, maka A akan muncul sebanyak dua kali (CDA, BDA). Dengan cara serupa kita dapatkan bahwa kemunculan B dan D juga dua kali. Maka dalam kombinasi delapan huruf sebagai solusi dengan kemunculan huruf ,C dan D sebanyak masing-masing dua kali, ternyata kombinasi seperti itu tidak mungkin ada, sehingga kesimpulannya adalah bahwa teka-teki Konigsberg adalah mustahil.

Tujuh jembatan di Königsberg adalah permasalahan matematika yang cukup terkenal yang diinspirasi oleh keadaan nyata pada masa itu. Kota Königsberg, Prussia (sekarang Kaliningrad,  Russia) dibagi oleh sungai Pregel menjadi 2 daratan utama yang dihubungkan oleh 7 buah jembatan satu sama lain. Pertanyaannya adalah apakah sauatu hal yang mungkin untuk berjalan melintasi setiap jembatan sebanyak satu kali dan kembali pada tempat semula. Pada 1736, Leonhard Euler menyatakan bahwa hal itu tidaklah mungkin.

1.    Solusi Euler

Untuk membuktikan hasilnya, Euler memformulakan masalah itu dalam teori graf, dengan menganalogikan pada kasus Königsberg. Pertama, dengan mengeliminasi  semua fitur kecuali daratan dan jembatan yang menghubungkannya; kedua, dengan mengganti daratan dengan titik, disebut simpul(vertex) dan tiap jembatan dengan garis. Disebut sisi (edge). Hasil struktur matematikanya disebut graf. Bentuk dari graf dapat diubah-ubah dalam berbagai cara tanpa mengubah graf itu sendiri, selama sisi dari simpul tidak diubah. Tidak bermasalah antara sisi yang berbentuk lurus atau lengkung, atau simpul yang terletak di sisi kiri atau kanan sisi lainnya. Euler menyadari bahwa masalah itu dapat diselesaikan berdasarkan derajat dari simpul–simpulnya. Derajat dari tiap simpul adalah jumlah sisi yang bersinggungan dengannya, pada graf jembatan Königsberg, tiga simpul mempunyai derajat 3 dan salah satu berderajat 5. Euler menunjukkan sirkuit yang kita inginkan hanya mungkin jika tidak ada simpul yang berderajat negatif. Cara perjalanan itu disebut sirkuit euler. Karena graf Königsberg ini mempunyai 4 simpul yang berderajat ganjil maka graf ini tidak mempunyai sirkuit euler.

Masalah ini dapat dikembangkan seperti beriku ini, ketika kita diminta untuk menyusun rute yang melintasi semua jembatan tapi tidak perlu punya titik mula dan akhir yang sama. Lintasan ini disebut lintasan Euler. Lintasan ini dimungkinkan ada jika dan hanya jika:

a)    Graf ini tidak punya simpul yang berderajat ganjil.

b)   Tepat ada 2 simpul yang berderajat ganjil, dan kedua simpul itu akan menjadi titil awal dan akhir. (ini juga hal yang mustahil untuk graf jembatan Königsberg).

2.  Signifikasi dalam sejarah matematika

Pada sejarah perkembangan matematika, solusi Euler tentang jembatan Königsberg dianggap sebagai teorema pertama dari teori graf, yang sekarang digeneralisasi sebagai cabang ilmu kombinatorial (meskipun masalah kombinatorial telah ditemukan sebelumnya). Sebagai tambahan, sesuai pengakuan Euler bahwa kuncinya  terletak pada jumlah jembatan dan daftar dari titik akhirnya (lebih dari posisi aslinya) ditandai dengan perkembangan tipologi. Perbedaan antara layout nyata dan skema graf adalah contoh yang bagus dari ide bahwa topologi tidak berpatokan pada bentuk asli benda.

3.  Keadaan jembatan itu sekarang

Dua dari tujuh jembatan asli hancur saat pengeboman sekutu ke Königsberg pada Perang Dunia II. Dua lainnya dirusak oleh Rusia dan diganti dengan jambatan modern.Tinggal 3 lainnya yang tersisa, meskipun hanya ada 2 yang berasal dari masa Euler (salah satu dibangun ulang oleh Jerman pada 1935). Menurut teori graf, dua dari simpul sekarang mempunyai derajat 2, dan 2 lainnya punya derajat 3. Karena itu, sekarang lintasan Euler mungkin dapat dibentuk, tapi karena harus dimulai dari sebuah pulau dan berakhir pada pulau yang berbeda.

C.      Kesimpulan

Teka-teki jembatan Konigsberg adalah mustahil. Teka-Teki Jembatan Konigsberg telah membuka jalan bagi terciptanya teorema baru yang disebut teorema graf. Aplikasi teorema graf menganalogikan setiap jembatan sebagai sisi dan setiap daratan sebagai simpul pada graf, sehingga terbentuk sebuah graf lengkap. Dan dengan memperhitungkan derajat dari setiap simpul yang terdapat dalam graf, menggunakan metode yang diungkapkan dalam pembuktian di atas, kita akan dapat  mengetahui  apakah  graf tersebut merupakan suatu lintasan di mana setiap sisi dilalui hanya satu kali saja. Fakta bahwa teorema graf lahir ketika Euler menyelesaikan masalah berdasarkan Teka-Teki Jembatan Konigsberg menyatakan hubungan tersendiri antara jaringan spasial (seperti jalur transportasi) dengan graf.