| Pencarian | Simpul telusur | Hasil |
|---|---|---|
| Runut-balik biasa | – | – |
| Urutan Warnsdorff | – | – |
| Pemeriksaan jalan buntu dan keterhubungan | – | – |
| Ketiganya | – | – |
Penjelajah lintasan Hamilton
Pada 1857 William Rowan Hamilton menciptakan sebuah teka-teki: telusuri rusuk sebuah dodekahedron sehingga Anda melewati masing-masing dari 20 sudutnya tepat satu kali dan berakhir di tempat Anda mulai. Rute seperti itu kini disebut siklus Hamilton. Memeriksanya mudah, dan pada umumnya menemukannya sulit. Telusuri satu sendiri pada dodekahedron Hamilton, pada papan catur, atau pada graf yang Anda gambar, atau tonton pencarian runut-balik memburunya, hitung jalan buntu yang dimasukinya, dan lihat berapa banyak beberapa pemeriksaan sederhana memangkas pencarian. Pilih sebuah graf dan sebuah tujuan: siklus yang kembali ke titik awal, atau sebuah lintasan. Telusuri: klik satu simpul untuk mulai, lalu klik satu tetangga setiap kali; cincin putus-putus menunjukkan ke mana Anda bisa melangkah. Klik simpul terakhir, Mundur, atau Urungkan untuk mundur satu langkah, dan Petunjuk menyebutkan langkah berikutnya yang masih bisa diselesaikan. Pencarian: Jalankan atau Langkah menjalankan pencarian runut-balik, yang menambah simpul sampai buntu lalu mundur; garis putus merah menandai tempat ia berbalik, dan batang menghitung simpul telusur per panjang lintasan. Sebelum mulai, klik sebuah simpul untuk memilih titik awalnya. Kotak centang menyalakan dan mematikan pemangkasan, Bandingkan menjalankan pencarian yang sama dengan dan tanpa pemangkasan, dan Hitung semua menghitung setiap siklus atau lintasan pada graf kecil. Sunting: klik untuk menambah simpul, klik dua simpul untuk menghubungkan atau memisahkannya, seret untuk memindahkan satu simpul, dan Hapus membuang simpul yang dipilih.
Cara kerjanya
- Pilih sebuah graf, seperti dodekahedron Hamilton, graf Petersen, atau perjalanan kuda, atau gambar graf Anda sendiri di Sunting, lalu pilih siklus atau lintasan sebagai tujuan.
- Di Telusuri, klik sebuah simpul untuk mulai lalu klik tetangga satu per satu. Mundur dan Urungkan mundur satu langkah, dan Petunjuk menunjukkan langkah berikutnya yang masih bisa diselesaikan.
- Di Pencarian, tekan Jalankan atau Langkah untuk menonton runut-balik mencari rute, nyalakan dan matikan pemangkasan, lalu tekan Bandingkan untuk melihat berapa banyak simpul telusur yang dibutuhkan setiap versi.
Hamilton versus Euler
Lintasan Euler memakai setiap sisi satu kali; lintasan Hamilton melewati setiap simpul satu kali. Keduanya terdengar mirip tetapi berperilaku sangat berbeda. Apakah sebuah graf terhubung punya lintasan Euler ditentukan dengan menghitung simpul berderajat ganjil, seperti ditunjukkan Euler pada 1736: ada jika tidak ada simpul seperti itu atau ada dua. Untuk lintasan Hamilton tidak ada aturan semacam itu yang diketahui. Menentukan apakah sebuah graf punya siklus Hamilton bersifat NP-lengkap, salah satu dari 21 masalah dalam daftar Richard Karp tahun 1972, sehingga metode cepat untuknya akan memberi metode cepat bagi ribuan masalah sulit lain. Yang ada adalah syarat-syarat yang memutuskan sebagian graf. Teorema Dirac tahun 1952 menjamin siklus Hamilton bila setiap simpul berderajat sedikitnya n/2, dan teorema Ore tahun 1960 bila dua simpul yang tidak terhubung selalu punya jumlah derajat sedikitnya n; simpul berderajat 1, titik potong, atau dua kelas warna dengan ukuran berbeda meniadakannya.
Cara kerja pencarian
Runut-balik membangun lintasan satu simpul demi satu simpul dan, ketika buntu, menarik kembali langkah terakhir lalu mencoba tetangga berikutnya. Ia selalu menemukan siklus Hamilton bila ada, tetapi jumlah lintasan sebagian bisa tumbuh secara eksponensial. Pada kisi 5 × 5, yang tidak punya siklus Hamilton, runut-balik biasa menelusuri 153.745 simpul telusur sebelum yakin. Dua pemeriksaan menghentikan lintasan tanpa harapan lebih awal: simpul yang belum dikunjungi dengan kurang dari dua tetangga bebas tidak bisa lagi masuk ke dalam siklus, dan ketika simpul yang belum dikunjungi terpecah menjadi bagian-bagian terpisah, tidak ada satu lintasan pun yang bisa menutupinya. Dengan keduanya, pembuktian yang sama memakan 1.761 simpul telusur. Aturan Warnsdorff tahun 1823, yang mencoba lebih dulu tetangga dengan langkah lanjutan paling sedikit, menemukan perjalanan kuda 8 × 8 dari sebuah sudut dalam 64 langkah tanpa satu pun jalan buntu.
Pertanyaan yang sering diajukan
Apa beda lintasan Hamilton dan siklus Hamilton?
Lintasan Hamilton melewati setiap simpul sebuah graf tepat satu kali. Siklus Hamilton melakukan hal yang sama lalu kembali lewat satu sisi lagi ke tempat ia mulai, sehingga ia bisa mulai dari simpul mana pun miliknya. Setiap graf dengan siklus Hamilton punya lintasan Hamilton (buang satu sisi dari siklus itu), tetapi tidak sebaliknya: graf Petersen punya lintasan Hamilton dan tidak punya siklus Hamilton.
Apakah dodekahedron punya siklus Hamilton?
Ya, ada 30, dengan menghitung setiap siklus satu kali apa pun titik awal dan arahnya. Hamilton mengubah pertanyaan itu menjadi permainan icosian pada 1857, sebuah papan dengan 20 sudut dodekahedron yang dipipihkan dan ditandai huruf konsonan, lalu menjual haknya seharga 25 pound kepada pembuat mainan London, John Jaques and Son. Hitung semua di aplikasi ini menemukan 30 siklus itu dalam sekitar 1.400 simpul telusur.
Mengapa kisi 5 × 5 tidak punya siklus Hamilton?
Warnai 25 titik itu seperti papan catur: 13 mendapat satu warna dan 12 warna lainnya, dan setiap langkah menuju warna yang lain. Siklus berganti warna sepanjang putaran, jadi ia butuh warna yang satu sebanyak warna yang lain, dan 13 dan 12 tidak memberi itu. Alasan yang sama berlaku untuk setiap kisi dengan jumlah titik ganjil, untuk kuda pada papan 5 × 5 atau 7 × 7 (kuda selalu berganti warna petak), dan untuk graf Herschel, yang dua kelasnya berisi 6 dan 5 simpul. Lintasan Hamilton tetap mungkin: ia mulai dan berakhir pada warna yang lebih banyak.
Bagaimana aturan Warnsdorff menemukan perjalanan kuda?
H. C. von Warnsdorff mengusulkan pada 1823 agar kuda selalu dipindahkan ke petak yang darinya ia akan punya langkah lanjutan paling sedikit. Petak dekat tepi dan sudut, yang mudah terputus, karena itu dikunjungi lebih awal, selagi kuda masih bisa masuk. Aturan ini hanya patokan praktis, bukan jaminan, dan seri harus dipecahkan dengan cara tertentu, tetapi pada papan 8 × 8 ia biasanya menyelesaikan perjalanan tanpa mundur. Digabungkan dengan runut-balik, seperti pada aplikasi ini, ia menemukan perjalanan terbuka dari 5 × 5 ke atas dan perjalanan tertutup pada papan 6 × 6 dan 8 × 8.
Berapa banyak siklus Hamilton yang dimiliki graf lengkap?
(n − 1)!/2 untuk n ≥ 3. Tetapkan simpul awal; n − 1 simpul lainnya bisa menyusul dalam urutan apa pun, dan setiap siklus terhitung dua kali, satu kali untuk tiap arah. K₆ punya 5!/2 = 60 dan K₁₀ punya 181.440. Inilah perjalanan pulang pergi yang harus dipilih seorang pedagang keliling, dan itulah sebabnya mencoba semuanya begitu cepat menjadi mustahil.
Siap mencobanya?
Buka PictorX di browser Anda — tanpa instalasi, tanpa kartu kredit untuk memulai.
Ke Editor