Tujuh jembatan Königsberg

Pada abad ke-18, penduduk kota Königsberg lama memikirkan sebuah teka-teki. Kota itu dilalui Sungai Pregel, yang membentuk dua pulau. Untuk mencapai pulau-pulau itu, di atas sungai dibangun tujuh jembatan. Mungkinkah dalam satu kali jalan-jalan hari Minggu kita melewati semua jembatan, tetapi setiap jembatan tepat satu kali? Mari kita lihat bagaimana letak jembatan-jembatan di atas sungai itu:

Mungkinkah kita memulai jalan-jalan dari suatu tempat dan melewati semua jembatan masing-masing tepat satu kali? Kita bisa mencobanya. Kita mulai dari kiri bawah, bergerak ke atas, lalu sedikit demi sedikit ke kanan, seperti ini:

Terlihat bahwa kita melewati enam dari tujuh jembatan; satu jembatan terlewatkan. Kita bisa mencoba rute lain…

Lagi-lagi kita hanya melewati enam dari tujuh jembatan Königsberg. Sepertinya memang tidak mungkin melewati setiap jembatan tepat satu kali dalam satu kali jalan-jalan. Suatu hari, masalah ini sampai ke matematikawan terkenal Leonhard Euler. Bukan sekadar terkenal: Euler benar-benar legenda matematika, bahkan bilangan Euler dinamai menurut namanya. Euler bertekad memecahkan teka-teki ini. Ia memulai dengan menandai setiap pulau atau bagian kota yang dihubungkan oleh jembatan:

Kemudian Euler bernalar sebagai berikut: jika banyaknya jembatan yang menuju suatu pulau genap, semua jembatan itu dapat kita lewati dalam satu kali jalan-jalan, dari mana pun kita memulai. Sederhananya, kita datang ke pulau lewat satu jembatan dan pergi lewat jembatan lain, sehingga banyaknya jembatan yang belum dilewati berkurang dua. Agar bisa datang ke pulau lewat satu jembatan dan pergi lewat jembatan lain, kita membutuhkan dua jembatan. Jika ada enam jembatan yang menuju suatu pulau, kita akan mengunjungi pulau itu tiga kali. Misalnya, bayangkan ada empat jembatan yang menuju pulau B seperti ini:

Maka kita dapat melewati semua jembatan dalam satu kali jalan-jalan hari Minggu, dari mana pun kita memulai. Cobalah sendiri! Pada gambar, saya menandai salah satu rutenya. Sekarang bayangkan ada satu jembatan lagi dari pulau D ke pulau B:

Terlihat bahwa rute yang kita pilih tidak memungkinkan kita melewati semua jembatan masing-masing tepat satu kali. Kita harus kembali ke pulau B melalui salah satu jembatan, lalu menyeberang ke pulau D. Namun, kita bisa memilih rute lain. Jika kita memulai jalan-jalan di pulau B, kita dapat melewati semua jembatan masing-masing tepat satu kali:

Kita memulai jalan-jalan di pulau B, naik ke daerah A, kembali ke B lewat jembatan, lalu ke daerah C, kembali lagi ke pulau B, dan akhirnya ke pulau D. Jadi, jika kita memulai di pulau yang banyak jembatannya ganjil, kita dapat melewati semua jembatannya masing-masing tepat satu kali. Atau kita bisa berjalan dengan arah sebaliknya: memulai di pulau D dan berakhir di pulau B.

Jadi, Euler menyadari bahwa agar semua jembatan dapat dilewati masing-masing tepat satu kali, harus berlaku salah satu dari dua hal: semua pulau mempunyai jembatan yang banyaknya genap, atau ada dua pulau yang banyak jembatannya ganjil. Di salah satu pulau dengan jembatan berjumlah ganjil kita memulai, dan di pulau yang lain kita berakhir. Semua pulau lainnya harus mempunyai jembatan yang banyaknya genap. Jika kita perhatikan tujuh jembatan asli di Königsberg:

terlihat bahwa setiap pulau mempunyai jembatan yang banyaknya ganjil! Pulau A mempunyai 3, B mempunyai 5, C mempunyai 3, dan D juga mempunyai 3. Karena itu, teka-teki ini tidak mempunyai penyelesaian: kita tidak mungkin melewati ketujuh jembatan masing-masing tepat satu kali dalam satu kali jalan-jalan hari Minggu. Jika salah satu jembatan, yang mana pun, kita robohkan, teka-tekinya tiba-tiba mempunyai penyelesaian. Misalnya, mari kita robohkan salah satu jembatan antara pulau B dan C:

Terlihat bahwa sekarang pulau B mempunyai 4 jembatan dan pulau C dua jembatan. Banyaknya jembatan pulau A dan D tidak berubah. Tiba-tiba kita mempunyai dua pulau dengan jembatan berjumlah genap dan dua pulau dengan jembatan berjumlah ganjil. Jika kita memulai jalan-jalan di salah satu pulau yang banyak jembatannya ganjil, kita dapat melewati semua jembatan masing-masing tepat satu kali. Pada gambar, kita memulai di pulau A dan berakhir di pulau D.

Jadi, Leonhard Euler memecahkan satu lagi masalah matematika yang terkenal. Kurang lebih, ia meletakkan dasar bagi apa yang sekarang kita sebut teori graf. Untuk menghormatinya, dalam teori graf, graf yang semua sisinya dapat dilewati masing-masing tepat satu kali disebut graf Euler.