Lintasan dan sirkuit Euler dijelaskan

Sebagian gambar bisa digambar dalam satu goresan, tanpa mengangkat pensil dan tanpa melewati garis dua kali, dan sebagian lagi tidak bisa, selama apa pun Anda mencoba. Anda tak perlu mencoba: hitunglah garis di setiap sudut. Bila paling banyak dua sudut memiliki jumlah garis ganjil, gambar itu bisa digambar, dan di sudut-sudut itulah goresan harus mulai dan berakhir. Leonhard Euler menemukan aturan ini pada tahun 1736, dan dengannya ia mendirikan teori graf.

Tujuh jembatan Königsberg digambar sebagai graf: empat daratan sebagai simpul, keempatnya berjumlah jembatan ganjil, di kedua tepi sebuah sungai
Tujuh jembatan Königsberg digambar sebagai graf: empat daratan sebagai simpul, keempatnya berjumlah jembatan ganjil, di kedua tepi sebuah sungai

Tujuh jembatan Königsberg

Kota Prusia bernama Königsberg, kini Kaliningrad, terletak di kedua tepi Sungai Pregel dan di dua pulau di dalamnya, Kneiphof dan Lomse. Tujuh jembatan menghubungkan keempat bagian itu: dua dari Kneiphof ke masing-masing tepian, satu di antara kedua pulau, dan satu dari Lomse ke masing-masing tepian. Warga kota bertanya-tanya apakah sebuah perjalanan bisa melewati setiap jembatan tepat sekali. Euler menjawab dalam makalah yang ia sampaikan kepada akademi di St. Petersburg pada tahun 1735 dan dicetak pada tahun 1741: tidak bisa. Langkah kuncinya adalah membuang segalanya kecuali bagian-bagian kota dan jembatan di antaranya, dan itulah yang dilakukan sebuah graf: satu simpul untuk setiap daratan dan satu sisi untuk setiap jembatan, dengan dua sisi bila dua jembatan menghubungkan tempat yang sama.

Potret Leonhard Euler
Potret Leonhard Euler
Portrait of Leonhard Euler
Portrait of Leonhard Euler

Aturan derajat

Derajat sebuah simpul adalah banyaknya sisi padanya. Goresan yang melewati sebuah simpul masuk lewat satu sisi dan keluar lewat sisi lain, jadi ia memakai sisi-sisi simpul itu berpasangan. Hanya simpul pertama dan terakhir goresan yang bisa menyimpan sisi tanpa pasangan. Karena itu simpul berderajat ganjil harus menjadi awal atau akhir goresan. Kneiphof punya lima jembatan dan tiga bagian lain tiga masing-masing: empat simpul ganjil, dua terlalu banyak. Secara umum, graf terhubung memiliki sirkuit Euler, yakni goresan yang berakhir di tempat ia mulai, bila semua derajatnya genap, dan lintasan Euler bila tepat dua derajatnya ganjil, dari yang satu ke yang lain. Banyaknya simpul ganjil tak pernah satu, atau bilangan ganjil lain: setiap sisi menambah 2 pada jumlah semua derajat, jadi jumlah itu genap. Euler juga menyadari hal ini, dan kini disebut lema jabat tangan.

Mengapa aturan itu sudah cukup

Euler menunjukkan bahwa gambar dengan lebih dari dua simpul ganjil tidak bisa ditelusuri, dan menyatakan tanpa bukti bahwa setiap gambar terhubung lainnya bisa. Buktinya datang dari Carl Hierholzer, matematikawan Jerman yang wafat muda pada tahun 1871; makalahnya terbit pada tahun 1873. Mulailah di simpul ganjil bila ada, kalau tidak di mana saja, dan berjalanlah lewat sisi-sisi yang belum terpakai selama masih bisa. Karena setiap simpul lain berderajat genap, Anda hanya bisa buntu di simpul akhir. Bila masih ada sisi tersisa, sebagiannya menyentuh jalur yang sudah dilalui, sebab gambar itu terhubung. Dari simpul semacam itu berjalanlah lagi sampai buntu, yang kini terjadi kembali di simpul itu, lalu sisipkan lingkar itu ke dalam jalur di sana. Ulangi sampai tak ada sisi yang tersisa. Bukti itu sekaligus algoritma tercepat: setiap sisi dilihat sejumlah kali yang tetap.

Algoritma Fleury: jangan bakar jembatan Anda

Sebuah goresan bisa gagal bahkan pada gambar yang sebenarnya bisa digambar. Ambil dua segitiga yang dihubungkan satu sisi dan mulailah di sebuah sudut segitiga pertama: bila Anda menyeberang ke segitiga kedua sebelum yang pertama selesai, Anda takkan pernah kembali. Sisi penghubung itu adalah jembatan: membuangnya membelah gambar menjadi dua. Algoritma Fleury tahun 1883 memberi satu aturan: di setiap simpul ambil sisi yang bukan jembatan bagi sisi-sisi yang tersisa, kecuali tak ada yang lain. Dengan mengikutinya, Anda selalu sampai selesai. Memeriksa jembatan memakan waktu, jadi algoritma Fleury lebih lambat daripada Hierholzer, tetapi itulah yang bisa Anda ikuti dengan pensil, dan petunjuk dalam aplikasi ini memakainya.

Memperbaiki sebuah gambar

Gambar dengan k simpul ganjil membutuhkan k/2 goresan. Untuk menggambarnya dalam satu goresan, tambahkan sisi yang memasangkan simpul-simpul ganjil: setiap sisi baru membuat dua simpul ganjil menjadi genap. Dengan k/2 − 1 sisi tersisa dua simpul ganjil dan terbentuklah lintasan; dengan k/2 tak ada yang tersisa dan terbentuklah sirkuit. Satu jembatan tambahan di Königsberg, di antara dua mana pun dari keempat bagian, akan membuat perjalanan itu mungkin, dan dua akan memungkinkan perjalanan pulang pergi. Sejarah melakukan hal serupa: dua jembatan hilang dalam Perang Dunia II dan dua digantikan jalan raya modern, dan kelima jembatan yang kini berdiri di tempat lama bisa dilewati sekali masing-masing, dari pulau yang satu ke pulau yang lain.

Menghitung caranya

Rumah Santo Nikolaus, sebuah persegi dengan kedua diagonal dan sebuah atap, adalah versi anak-anak Jerman dari teka-teki ini: „Das ist das Haus vom Ni-ko-laus” terdiri atas delapan suku kata, satu untuk setiap garis. Kedua sudut bawahnya adalah satu-satunya simpul ganjil, dan dari masing-masing ada tepat 44 cara menggambarnya, 88 seluruhnya. Untuk graf berarah, banyaknya sirkuit Euler punya rumus, yaitu teorema BEST, dinamai menurut de Bruijn, van Aardenne-Ehrenfest, Smith, dan Tutte. Untuk graf biasa rumus seperti itu belum dikenal, dan menghitungnya secara umum dianggap sulit, jadi aplikasi ini menghitung gambar kecil dengan mencoba setiap cara dan melewati langkah yang akan membelah gambar menjadi dua.

Tempat lintasan Euler dipakai

Kendaraan pembajak salju, mesin penyapu, atau tukang pos ingin melewati setiap jalan sekali lalu kembali. Bila setiap persimpangan punya jumlah jalan genap, sebuah sirkuit Euler sudah cukup; kalau tidak, sebagian jalan harus dilalui dua kali, dan memilih yang paling murah adalah masalah tukang pos Cina, yang diajukan Meigu Guan pada tahun 1962. Plotter pena atau mesin pemotong laser menghemat waktu dengan menarik sebanyak mungkin garis tanpa mengangkat alatnya. Dalam penguraian genom, jutaan potongan pendek DNA disusun dengan mencari lintasan Euler pada graf de Bruijn, yang di dalamnya setiap potongan adalah sebuah sisi. Dan aturan yang sama memberi tahu gambar garis mana di buku teka-teki yang layak dicoba.

Cobalah

Buka Pencari Lintasan Euler untuk menelusuri sendiri dua belas gambar, dari Königsberg pada tahun 1736 dan hari ini sampai bintang, persegi bersarang, dan sebuah kubus, atau gambarlah milik Anda sendiri dengan sisi sejajar. Simpul ganjil digambar penuh, setiap simpul menampilkan derajatnya, dan aturan derajat di bawah gambar menyebutkan apa yang mungkin dan sisi mana yang akan memperbaiki gambar itu. Bila Anda buntu, aplikasi ini menyebutkan apakah Anda mulai di simpul yang keliru atau melewati jembatan terlalu dini, dan pada langkah keberapa. Petunjuk memberi sebuah sisi yang aman, dan Selesaikan menggambar gambar itu dengan algoritma Fleury, memperlihatkan uji jembatannya, atau dengan algoritma Hierholzer, memperlihatkan setiap penyisipan.

Pertanyaan yang sering diajukan

Apakah lintasan Euler sama dengan lintasan Hamilton?

Tidak. Lintasan Euler memakai setiap sisi sekali dan boleh melewati sebuah simpul berkali-kali; lintasan Hamilton melewati setiap simpul sekali dan tak harus memakai setiap sisi. Apakah sebuah graf punya lintasan Euler langsung terjawab dengan menghitung simpul ganjil, tetapi untuk lintasan Hamilton tak ada uji cepat yang dikenal, dan menemukan satu adalah salah satu masalah sulit klasik dalam ilmu komputer.

Apakah aturan derajat berlaku bila dua simpul dihubungkan lebih dari satu sisi?

Berlaku. Setiap sisi dihitung pada derajat kedua ujungnya, ada atau tidak ada sisi lain yang menghubungkan dua simpul yang sama. Königsberg adalah multigraf semacam itu, dengan dua jembatan dari Kneiphof ke masing-masing tepian. Sebuah sisi dari simpul ke dirinya sendiri, yaitu gelung, menambah 2 pada derajatnya dan tak pernah mengubah keganjilannya.

Bagaimana dengan jalan satu arah?

Dalam graf berarah setiap sisi punya arah, dan aturannya membandingkan sisi yang masuk ke setiap simpul dengan yang keluar. Ada sirkuit Euler bila setiap simpul punya sisi masuk sebanyak sisi keluarnya dan sisi-sisinya menyatu, dan ada lintasan Euler bila satu simpul punya satu sisi keluar lebih banyak, satu simpul punya satu sisi masuk lebih banyak, dan semua simpul lain seimbang. Lintasan itu lalu berjalan dari simpul pertama ke simpul kedua.

Mungkinkah ada gambar dengan tepat satu simpul ganjil?

Tidak. Jumlah derajat semua simpul sama dengan dua kali banyaknya sisi, karena setiap sisi punya dua ujung. Jumlah itu genap, jadi banyaknya derajat ganjil di dalamnya juga harus genap: 0, 2, 4, dan seterusnya, tak pernah 1 atau 3.

Siap mencobanya?

Buka PictorX di browser Anda — tanpa instalasi, tanpa kartu kredit untuk memulai.

Buka Pencari Lintasan Euler