Tujuh Jembatan Königsberg

Tujuh Jembatan Königsberg adalah suatu masalah penting dalam Matematika. Pembuktian ketidakmungkinan atas masalah ini oleh Leonhard Euler pada tahun 1736 meletakkan dasar-dasar teori graf dan menjadi awal mula ide topologi.

Peta jembatan Königsberg saat zaman Leonhard Euler di mana terdapat tata keteraturan tujuh jembatan yang sesungguhnya serta menyoroti sungai Pregel beserta jembatan-jembatannya.

Kota Königsberg yang termasuk dalam kekuasaan Prussia (sekarang bernama Kaliningrad, Rusia) telah dibangun di antara kedua sisi sungai Pregel dan meliputi dua pulau yang luas yang dapat tersambung antara satu dengan yang lain serta tujuh jembatan tersebut mampu mencakup satu tanah daratan. Persoalannya yakni bagaimana cara menciptakan rangka dari tempat untuk berjalan melalui kota dengan bermaksud menyeberangi tiap-tiap jembatan sekaligus dalam satu kali saja dengan syarat apabila suatu pulau itu dapat dijangkau dengan jembatan-jembatan tersebut serta saat menuju jalan masuk dari setiap jembatan tersebut harus diseberangi dalam satu kali sampai ke titik ujung jembatan yang lain. Tempat jalan masuk dan jalan keluar dari tujuh jembatan tersebut tidak usah tampak seperti itu juga.

Euler telah membuktikan bahwa tak ada pemecahan perkara atas persoalan tersebut. Hal yang merumitkannya ialah bagaimana untuk mengembangkan suatu cara untuk melakukan penelaahan serta melakukan pengujian selanjutnya atas hal tersebut sehingga dapat diperlihatkannya pernyataan yang tegas ini serta dibarengi oleh kecermatan yang didasari dengan ilmu pasti.

Pendekatan Euler

Leonhard Euler mengajukan pertanyaan yang lebih umum: Apakah mungkin bagi seseorang untuk memulai di titik mana pun dalam sebuah graf, melewati setiap tepi tepat satu kali, dan kembali ke titik awal (yang kemudian dikenal dengan Jalur Euler atau Sirkuit Euler)?

Untuk menjawab pertanyaan ini, Euler merepresentasikan setiap daerah sebagai sebauh titik (vertex) dan setiap jembatan sebagai sebuah garis penghubung (edge) di antara titik-titik tersebut. Dia menyadari bahwa kunci untuk memecahkan masalah ini adalah memahami derajat dari setiap titik, yaitu jumlah garis yang menghubungkannya. Euler mereduksi masalah ini menjadi penelitian tentang jalur yang melintasi setiap garis tepat satu kali. Sebagai gambaran setiap daerah yang dihubungkan jembatan menjadi sebuah titik, dikarenakan kota ini memiliki empat daerah maka ada 4 titik, dan setiap 4 titik ini dihubungkan oleh jembatan yang dipresentasikan dengan derajat simpul atau garis penghubung. Seperti terlihat pada gambar dibawah ini.

Euler menemukan bahwa untuk dapat melintasi setiap jembatan tepat satu kali dan kembali ke titik awal, setiap titik dalam graf harus memiliki derajat genap. Jika hanya dua titik yang memiliki derajat ganjil, maka perjalanan bisa dimulai di salah satu dari titik tersebut dan berakhir di yang lain.

Euler menemukan bahwa kunci untuk menjawab masalah ini adalah memahami derajat (jumlah garis yang terhubung) dari setiap titik. Dia menyadari bahwa jika sebuah graf memiliki lebih dari dua ttik dengan derajat ganjil, maka tidak mungkin untuk melakukan perjalanan melintasi setiap garis tepat satu kali dan kembali ke titik awal. Dalam kasus königsberg, terdapat empat titik dengan derajat ganjil. Oleh karena itu, tidak mungkin untuk melakukan perjalanan yang melintasi setiap jembatan tepat satu kali.

Solusi Euler untuk masalah Tujuh Jembatan Königsberg bukan hanya memcahkan teka-teki lokal, tetapi juga menandai kelahiran teori graf. Penemuan Euler ini memperkenalkan konsep Jalur Euler dan Sirkuit Euler, yang menjadi dasar bagi perkembangan teori graf modern. Selain itu, solusi ini mengilhami penelitian lebih lanjut dalam berbagai bidang seperti matematika, ilmu komputer, dan teknik.

Bacaan Lanjutan

• Euler,L.(1736). "Solutio problematis ad gometriam situs pertinentis." Commentarii Academiae Scientiarum Imperialis Petropolitanae.
• Biggs, N., Lloyd, E.K., & Wilson, R.J. (1986). Graph Theory, 1736-1936. Oxford University Press