n·Nalartanpa titik
Jelajahi Simu ↗
MATEMATIKA · 2:12 MENIT

Jembatan Königsberg

Tujuh jembatan, satu gagasan besar.

Tayang
Video oleh Simu · Subtitle Indonesia

Teka-teki Königsberg meminta satu perjalanan melewati setiap jembatan tepat sekali. Daratan menjadi simpul dan jembatan menjadi sisi pada graf tak berarah. Bentuk jalan dan panjang jembatan tidak memengaruhi pertanyaan ini.

Graf terhubung: lintasan Euler ada jika 0 atau 2 simpul berderajat ganjil

Pasangan masuk dan keluar

Derajat simpul menghitung banyaknya ujung sisi yang menempel padanya. Di simpul perantara, setiap kedatangan perlu dipasangkan dengan keberangkatan. Jika semua derajat genap, perjalanan dapat kembali ke awal. Jika tepat dua simpul ganjil, keduanya menjadi awal dan akhir yang berbeda. Syarat ini berlaku bila semua simpul yang memiliki sisi berada dalam satu komponen terhubung.

Mengapa tujuh jembatan tidak bisa?

Graf jembatan Königsberg memiliki derajat 5, 3, 3, dan 3: empat simpul ganjil. Maka tidak ada lintasan yang memakai seluruh tujuh jembatan tepat sekali. Aturan ini mengatur pemakaian sisi, bukan melarang mengunjungi daratan yang sama lagi. Dalam perencanaan rute nyata, pengulangan jalan bisa tak terhindarkan; optimasinya dapat mencari total pengulangan yang paling kecil.