Tujuh jambatan Königsberg

Pada abad ke-18, penduduk bandar Königsberg lama memikirkan satu teka-teki. Sungai Pregel mengalir melalui bandar itu dan membentuk dua pulau. Terdapat tujuh jambatan yang merentasi sungai ini ke pulau-pulau tersebut. Bolehkah kita melintasi semua jambatan itu dalam satu perjalanan santai pada hari Ahad, dengan setiap jambatan dilintasi sekali sahaja? Mari kita lihat kedudukan jambatan di atas sungai itu:

Bolehkah kita memulakan perjalanan di suatu tempat dan melintasi setiap jambatan sekali sahaja? Mari kita cuba. Kita bermula di kiri bawah, bergerak ke atas, kemudian ke kanan, seperti berikut:

Kita lihat bahawa kita telah melintasi enam daripada tujuh jambatan dan terlepas satu jambatan. Kita boleh mencuba laluan lain…

Sekali lagi, kita hanya melintasi enam daripada tujuh jambatan di Königsberg. Nampaknya mustahil untuk melintasi setiap jambatan sekali sahaja dalam satu perjalanan. Pada suatu hari, ahli matematik terkenal Leonhard Euler bertemu dengan masalah ini. Malah, Euler bukan sekadar terkenal — dia ialah legenda matematik, dan pemalar e (nombor Euler) dinamakan sempena namanya. Euler memutuskan untuk menyelesaikan teka-teki ini. Dia mula-mula melabel setiap pulau atau bahagian bandar yang dihubungkan oleh jambatan:

Euler kemudian membuat penaakulan berikut: jika bilangan jambatan yang menuju ke sesuatu pulau ialah nombor genap, kita boleh melintasi semua jambatan itu dalam satu perjalanan, tidak kira di mana kita bermula. Kita sampai ke pulau itu melalui satu jambatan dan meninggalkannya melalui jambatan lain — bilangan jambatan yang belum dilintasi berkurang sebanyak dua. Untuk sampai ke pulau melalui satu jambatan dan meninggalkannya melalui jambatan lain, kita memerlukan dua jambatan. Jika terdapat enam jambatan ke sesuatu pulau, kita akan mengunjungi pulau itu tiga kali. Sebagai contoh, bayangkan terdapat empat jambatan ke pulau B seperti berikut:

Maka, kita boleh melintasi semua jambatan dalam satu perjalanan pada hari Ahad, tidak kira di mana kita bermula. Cubalah! Dalam rajah, saya telah menandakan satu laluan. Sekarang bayangkan terdapat satu lagi jambatan ke pulau B dari pulau D:

Kita lihat bahawa laluan yang kita pilih tidak membolehkan kita melintasi setiap jambatan sekali sahaja. Kita terpaksa kembali ke pulau B melalui salah satu jambatan, kemudian pergi ke pulau D. Namun, kita boleh memilih laluan lain. Kita boleh memulakan perjalanan di pulau B, dan kemudian kita dapat melintasi setiap jambatan sekali sahaja:

Kita memulakan perjalanan di pulau B, bergerak ke atas ke kawasan A, kemudian melalui jambatan kembali ke B, ke kawasan C, kembali ke pulau B dan akhirnya ke pulau D. Jadi, jika kita bermula di pulau yang mempunyai bilangan jambatan ganjil, kita dapat melintasi setiap jambatannya sekali sahaja. Kita juga boleh melakukannya secara terbalik — bermula di pulau D dan berakhir di pulau B.

Oleh itu, Euler mendapati bahawa untuk melintasi setiap jambatan sekali sahaja, sama ada semua pulau mesti mempunyai bilangan jambatan genap, atau boleh terdapat dua pulau yang mempunyai bilangan jambatan ganjil — kita bermula di satu pulau dengan bilangan jambatan ganjil dan berakhir di pulau yang satu lagi. Semua pulau lain mesti mempunyai bilangan jambatan genap. Jika kita melihat tujuh jambatan asal di Königsberg:

kita dapati bahawa setiap pulau mempunyai bilangan jambatan ganjil! Pulau A mempunyai 3 jambatan, B mempunyai 5, C mempunyai 3 dan D juga mempunyai 3. Oleh itu, teka-teki ini tiada penyelesaian — kita tidak boleh melintasi ketujuh-tujuh jambatan itu, setiap satu sekali sahaja, dalam satu perjalanan pada hari Ahad. Jika mana-mana satu jambatan dirobohkan, teka-teki itu tiba-tiba mempunyai penyelesaian. Sebagai contoh, mari kita robohkan salah satu jambatan antara pulau B dengan pulau C:

Kita lihat bahawa kini pulau B mempunyai 4 jambatan dan pulau C mempunyai dua jambatan. Bilangan jambatan pulau A dan D tidak berubah. Tiba-tiba terdapat dua pulau dengan bilangan jambatan genap dan dua pulau dengan bilangan jambatan ganjil. Jika kita memulakan perjalanan di salah satu pulau yang mempunyai bilangan jambatan ganjil, kita dapat melintasi setiap jambatan sekali sahaja. Dalam rajah, kita bermula di pulau A dan berakhir di pulau D.

Jadi, Leonhard Euler menyelesaikan satu lagi masalah matematik yang terkenal dan boleh dikatakan telah meletakkan asas bagi bidang yang kini kita panggil teori graf. Sebagai penghormatan kepadanya, graf yang setiap tepinya boleh dilalui sekali sahaja dalam satu laluan dipanggil graf Euler dalam teori graf.