Seekor laba-laba berdiri pada salah satu sisi muka sebuah oktahedron (polihedron dengan delapan sisi muka berbentuk segitiga). Laba-laba itu ingin merayapi bangun tersebut dari satu sisi muka ke sisi muka lainnya sehingga melintasi setiap rusuk tepat satu kali. Mungkinkah hal ini dilakukan? Jika ya, bagaimana caranya?
Jika kita mulai dari suatu simpul dan menelusuri sisi-sisi untuk mencapai simpul lain, kita membentuk suatu jalan pada graf. Lebih tepatnya, jalan dalam graf adalah barisan simpul sedemikian sehingga setiap simpul dalam barisan bertetangga dengan simpul sebelum dan sesudahnya dalam barisan tersebut. Jika jalan itu melintasi setiap sisi tepat satu kali, jalan tersebut disebut jejak Euler (atau jalan Euler atau lintasan Euler). Jika, selain itu, simpul awal dan akhirnya sama (jadi Anda menelusuri setiap sisi tepat satu kali dan berakhir di tempat Anda memulai), jalan tersebut disebut sirkuit Euler (atau tur Euler). Tentu saja, jika suatu graf tidak terhubung, tidak mungkin ditemukan jejak atau sirkuit semacam itu. Sepanjang sisa bagian ini, anggap semua graf yang dibahas terhubung.
Masalah jembatan Königsberg sebenarnya merupakan pertanyaan tentang keberadaan jejak Euler. Akan ada rute yang melintasi setiap jembatan tepat satu kali jika dan hanya jika multigraf di bawah memiliki jejak Euler:
Graf ini cukup kecil sehingga kita dapat memeriksa setiap jalan yang mungkin tanpa menggunakan ulang sisi, dan dengan demikian meyakinkan diri bahwa tidak ada jejak Euler (apalagi sirkuit Euler). Pada graf kecil yang memiliki jejak Euler, biasanya tidak sulit untuk menemukannya. Tujuan kita adalah menemukan cara cepat untuk memeriksa apakah suatu graf memiliki jejak atau sirkuit Euler, bahkan jika graf tersebut cukup besar.
Salah satu cara menuliskan jejak atau sirkuit Euler adalah mencantumkan sisi-sisinya secara berurutan. Setiap sisi berupa pasangan simpul, dan untuk menunjukkan arah kita melintasi sisi tersebut, kita dapat menuliskannya sebagai pasangan terurut alih-alih sebagai himpunan. Sebagai contoh, perhatikan graf berikut:
Misalkan Anda memiliki graf dengan barisan derajat \((4,2,2,2,2)\) yang mempunyai jejak Euler. Berapa kali nama simpul berderajat 4 akan muncul dalam daftar sisi Anda?
Misalkan Anda memiliki graf dengan jejak Euler yang ditulis sebagai daftar sisi. Apa yang dapat Anda simpulkan tentang simpul yang muncul tepat 3 kali dalam daftar tersebut? Pilih semua pernyataan yang mungkin benar.
Simpul \(a\) berderajat 1, dan jika Anda mencoba membuat sirkuit Euler, Anda akan terhenti di simpul tersebut. Simpul itu merupakan jalan buntu, kecuali jika Anda memulai dari sana. Namun, dalam hal itu tidak ada cara untuk kembali, sehingga sirkuit Euler tidak mungkin ditemukan. Meskipun demikian, terdapat jejak Euler. Jejak itu dimulai pada simpul \(a\text{,}\) kemudian mengitari segitiga. Anda akan berakhir pada simpul berderajat 3.
Masalah serupa muncul setiap kali terdapat simpul dengan derajat ganjil. Jika Anda memulai pada simpul semacam itu, Anda tidak akan dapat berakhir di sana (setelah melintasi setiap sisi tepat satu kali). Setelah menggunakan satu sisi untuk meninggalkan simpul awal, akan tersisa sisi dalam jumlah genap yang memancar dari simpul tersebut. Separuh sisi ini dapat digunakan untuk kembali ke simpul itu, dan separuh lainnya untuk meninggalkannya. Jadi, Anda kembali, lalu pergi; kembali, lalu pergi. Satu-satunya cara menghabiskan semua sisi adalah menggunakan sisi terakhir untuk meninggalkan simpul tersebut. Di sisi lain, jika terdapat simpul berderajat ganjil yang bukan merupakan titik awal jejak, pada akhirnya Anda akan terhenti di simpul itu. Jejak tersebut akan menggunakan pasangan sisi yang bersisian dengan simpul untuk tiba dan pergi lagi. Pada akhirnya, semua sisi kecuali satu akan terpakai, sehingga hanya tersisa satu sisi untuk tiba dan tidak ada sisi untuk pergi lagi.
Semua ini menunjukkan bahwa jika suatu graf memiliki jejak Euler dan dua simpul berderajat ganjil, jejak Euler tersebut harus bermula pada salah satu simpul berderajat ganjil dan berakhir pada simpul lainnya. Dalam keadaan demikian, setiap simpul lain harus berderajat genap karena kita memerlukan jumlah sisi yang sama untuk tiba di simpul-simpul itu dan untuk meninggalkannya. Bagaimana suatu graf dapat memiliki sirkuit Euler? Graf tersebut tidak boleh memiliki simpul berderajat ganjil karena jejak Euler harus bermula atau berakhir di simpul itu, tetapi tidak keduanya. Jadi, agar suatu graf memiliki sirkuit Euler, semua simpulnya harus berderajat genap.
Kebalikannya juga benar: jika semua simpul suatu graf berderajat genap, graf tersebut memiliki sirkuit Euler; dan jika tepat dua simpul berderajat ganjil, graf tersebut memiliki jejak Euler. Membuktikan hal ini agak rumit, tetapi gagasan dasarnya adalah bahwa Anda tidak akan pernah terhenti karena pada setiap simpul terdapat sisi “keluar” untuk setiap sisi “masuk”. Jika Anda mencoba membuat jejak Euler dan melewatkan beberapa sisi, Anda selalu dapat “menyisipkan” suatu sirkuit yang menggunakan sisi-sisi yang sebelumnya terlewat.
Karena keempat simpul pada graf jembatan Königsberg berderajat ganjil, tidak ada jejak Euler pada graf tersebut. Jadi, warga kota tidak mungkin melintasi setiap jembatan tepat satu kali.
Misalkan Anda ingin berkeliling Königsberg sedemikian rupa sehingga mengunjungi setiap daratan (kedua pulau dan kedua tepi sungai) tepat satu kali. Hal ini dapat dilakukan. Dalam istilah teori graf, kita menanyakan apakah terdapat lintasan yang mengunjungi setiap simpul tepat satu kali. Lintasan semacam itu disebut lintasan Hamilton (atau lintasan Hamiltonian). Kita juga dapat mempertimbangkan siklus Hamilton, yaitu lintasan Hamilton yang berawal dan berakhir pada simpul yang sama.
Graf di kanan tidak memiliki lintasan Hamilton. Anda harus mengunjungi setiap simpul “luar”, tetapi begitu mengunjungi salah satunya, Anda akan terhenti. Perhatikan bahwa graf ini juga tidak memiliki jejak Euler, meskipun terdapat graf yang memiliki jejak Euler tetapi tidak memiliki lintasan Hamilton.
Menemukan lintasan Hamilton tampaknya lebih mudah karena graf sering kali memiliki lebih banyak sisi daripada simpul, sehingga lebih sedikit syarat yang harus dipenuhi. Namun, tidak seorang pun mengetahui apakah hal ini benar. Belum diketahui adanya uji sederhana untuk menentukan apakah suatu graf memiliki lintasan Hamilton. Untuk graf kecil, hal ini bukan masalah, tetapi seiring bertambahnya ukuran graf, pemeriksaan keberadaan lintasan Hamilton menjadi semakin sulit. Bahkan, sejauh yang kita ketahui, pertanyaan ini merupakan contoh masalah yang secara umum terlalu sulit diselesaikan oleh komputer karena merupakan contoh masalah NP-lengkap.
Pertanyaan apa yang Anda miliki setelah membaca bagian ini? Tuliskan setidaknya satu pertanyaan tentang isi bagian ini yang membuat Anda ingin tahu lebih lanjut.
Anda dan teman-teman ingin berkeliling wilayah barat daya Amerika Serikat dengan mobil. Anda akan mengunjungi sembilan negara bagian yang ditunjukkan di bawah, dengan aturan yang agak aneh berikut: Anda harus melintasi setiap perbatasan di antara negara bagian yang bertetangga tepat satu kali (jadi, misalnya, Anda harus melintasi perbatasan Colorado–Utah tepat satu kali). Dapatkah perjalanan ini dilakukan? Jika dapat, apakah tempat Anda memulai perjalanan darat tersebut berpengaruh? Fakta apa dalam teori graf yang menyelesaikan masalah ini?
Edward ingin mengajak seekor teman tikus betina berkeliling rumah barunya. Mungkinkah mereka melewati setiap pintu tepat satu kali? Jika mungkin, di ruangan mana mereka harus memulai dan mengakhiri tur? Jelaskan.
Setelah beberapa tahun dalam hitungan usia tikus, Edward memutuskan untuk merenovasi rumahnya. Ia ingin menambahkan beberapa pintu baru di antara ruangan-ruangan yang ada. Tentu saja, ia tidak dapat menambahkan pintu pada bagian luar rumah. Mungkinkah setiap ruangan memiliki banyak pintu yang ganjil? Jelaskan.
Soal ini lebih sulit daripada tiga soal sebelumnya. Pikirkan pada “bagian” graf yang mana lintasan Hamilton harus berada pada setiap langkah berselang-seling.
Seorang pembangun jembatan datang ke Königsberg dan ingin menambahkan jembatan agar perjalanan yang melintasi setiap jembatan tepat satu kali dapat dilakukan. Berapa banyak jembatan yang harus dibangun?
Di bawah ini terdapat graf yang merepresentasikan hubungan pertemanan di antara sekelompok mahasiswa (setiap simpul adalah seorang mahasiswa dan setiap sisi adalah suatu hubungan pertemanan). Mungkinkah para mahasiswa duduk mengelilingi meja bundar sedemikian sehingga setiap mahasiswa duduk di antara dua temannya? Apa kaitan pertanyaan ini dengan jejak?
Jika nama para mahasiswa dibaca menurut urutan tempat duduk, setiap nama harus dibaca tepat satu kali, dan nama terakhir harus merupakan mahasiswa yang berteman dengan mahasiswa pertama. Siklus jenis apakah ini?
Di atas meja terdapat 8 kartu domino seperti ditunjukkan di bawah ini. Jika semua kartu tersebut disusun dalam satu baris, sedemikian sehingga setiap dua sisi yang bersentuhan memiliki banyak titik yang sama, berapakah jumlah titik pada kedua ujung barisan?
Dapatkah kita menentukan keberadaan lintasan Hamilton pada suatu graf berdasarkan derajat simpul-simpulnya?
Misalkan suatu graf memiliki lintasan Hamilton. Paling banyak berapa simpul berderajat satu yang dapat dimiliki graf tersebut? Jelaskan mengapa jawaban Anda benar.
Temukan graf yang tidak memiliki lintasan Hamilton meskipun tidak satu pun simpulnya berderajat satu. Jelaskan mengapa contoh Anda memenuhi persyaratan.
Misalkan Anda memiliki graf bipartit \(G\) dengan salah satu bagian memiliki sedikitnya dua simpul lebih banyak daripada bagian lainnya. Buktikan bahwa \(G\) tidak memiliki lintasan Hamilton.
