Lintasan dan siklus Hamilton dijelaskan

Gambar lima titik melingkar, hubungkan masing-masing dengan dua tetangganya, dan Anda bisa berjalan memutar melewati setiap titik satu kali lalu pulang: itulah siklus Hamilton. Tambahkan beberapa sisi atau buang beberapa, dan pertanyaannya menjadi sangat sulit. Apakah sebuah graf punya siklus seperti itu adalah salah satu masalah paling terkenal yang belum bisa dijawab cepat oleh komputer mana pun untuk setiap graf.

Sebuah dodekahedron yang dipipihkan dengan 20 sudutnya ditandai huruf konsonan dan satu siklus Hamilton yang melewati semuanya digambar dengan garis terang, dengan satu sisi merah putus-putus di tempat pencarian berbalik
Sebuah dodekahedron yang dipipihkan dengan 20 sudutnya ditandai huruf konsonan dan satu siklus Hamilton yang melewati semuanya digambar dengan garis terang, dengan satu sisi merah putus-putus di tempat pencarian berbalik

Setiap simpul satu kali

Graf adalah sekumpulan titik, yaitu simpul, yang dihubungkan oleh garis, yaitu sisi. Lintasan Hamilton berjalan menyusuri sisi dan melewati setiap simpul tepat satu kali; siklus Hamilton juga kembali ke tempat ia mulai, jadi jumlah sisinya sama dengan jumlah simpulnya. Graf dengan siklus Hamilton disebut graf Hamilton. Memeriksa rute yang diajukan itu mudah: hitung simpulnya dan lihat setiap langkahnya. Menemukan satu rute, atau membuktikan tidak ada satu pun, itulah bagian yang sulit, karena banyaknya urutan kunjungan simpul tumbuh seperti n!, sudah 2,4 × 10¹⁸ untuk 20 simpul.

Permainan icosian Hamilton

William Rowan Hamilton, matematikawan Irlandia yang menemukan kuaternion, menciptakan permainan icosian pada 1857. Papannya menampilkan dodekahedron yang dipipihkan ke bidang datar, dengan 20 sudutnya ditandai huruf konsonan, dan tugas utamanya adalah menancapkan pasak bernomor 1 sampai 20 pada sudut-sudut itu sehingga nomor berurutan, serta 20 dan 1, dihubungkan oleh sisi. Hamilton menjual haknya seharga 25 pound kepada pembuat mainan London, John Jaques and Son, yang menerbitkannya pada 1859; penjualannya buruk. Teka-teki itu punya 30 penyelesaian, dengan menghitung sebuah siklus satu kali apa pun titik awal dan arahnya. Pertanyaannya sendiri tidak baru: Thomas Kirkman telah menanyakan polihedron mana yang punya siklus melalui semua sudutnya dalam makalah yang dikirim ke Royal Society pada 1855, dan menunjukkan satu yang tidak punya.

Perjalanan kuda

Perjalanan kuda menggerakkan kuda catur sehingga ia mendarat di setiap petak tepat satu kali: sebuah lintasan Hamilton pada graf yang simpulnya adalah petak dan sisinya adalah langkah kuda. Perjalanan tertutup berakhir satu langkah kuda dari titik awalnya, yaitu sebuah siklus Hamilton. Pemain catur menyusun teka-teki semacam itu lebih dari seribu tahun lalu, dan Euler mempelajarinya dalam makalah tahun 1759. Pada 1823 H. C. von Warnsdorff mengusulkan agar selalu menuju petak dengan langkah lanjutan paling sedikit; aturan sederhana ini biasanya menyelesaikan perjalanan pada papan 8 × 8 tanpa mundur. Kuda selalu berganti warna petak, jadi perjalanan tertutup memerlukan petak terang sebanyak petak gelap, yang meniadakan papan dengan jumlah petak ganjil. Allen Schwenk menunjukkan pada 1991 dengan tepat papan persegi panjang mana yang punya perjalanan tertutup; di antara papan persegi, setiap papan dengan sisi genap 6 atau lebih punya. Papan catur biasa punya 13.267.364.410.532 perjalanan tertutup, dihitung oleh Brendan McKay pada 1997.

Graf tanpa siklus Hamilton

Bukti tercepat bahwa tidak ada siklus adalah argumen penghitungan. Jika simpul bisa diwarnai dengan dua warna sehingga setiap sisi menghubungkan warna berbeda, siklus berganti-ganti warna dan memerlukan simpul yang sama banyak untuk tiap warna; kisi 5 × 5 punya 13 dari satu warna dan 12 dari warna lain, jadi ia tidak punya siklus Hamilton. Titik potong, yang bila dibuang memecah graf, harus dilewati dua kali, dan simpul berderajat 1 tidak bisa dilewati sama sekali. Beberapa graf lolos dari semua argumen itu. Graf Petersen, yang diterbitkan oleh Julius Petersen pada 1898, punya 10 simpul berderajat 3 dan tidak punya siklus Hamilton, namun menghapus simpul mana pun menyisakan graf yang punya; itulah graf hipohamiltonan terkecil. Graf Herschel, dinamai menurut Alexander Stewart Herschel, yang menulis tentang permainan icosian pada 1862, punya 11 simpul dan 18 sisi dan merupakan graf sebuah polihedron dengan sembilan sisi berbentuk segi empat. Tidak ada polihedron dengan sudut lebih sedikit yang kekurangan siklus Hamilton. Pada 1884 Peter Guthrie Tait menduga bahwa setiap polihedron dengan tiga rusuk di tiap sudutnya punya satu; W. T. Tutte menemukan contoh penyangkal dengan 46 simpul pada 1946.

Syarat yang menjamin adanya siklus

Jika sebuah graf punya banyak sisi, siklus Hamilton pasti ada. Gabriel Dirac membuktikan pada 1952 bahwa graf dengan n ≥ 3 simpul yang setiap simpulnya berderajat sedikitnya n/2 punya satu, dan Øystein Ore melemahkan syarat itu pada 1960: cukup bila dua simpul yang tidak terhubung selalu punya jumlah derajat sedikitnya n. Kedua syarat hanya berlaku satu arah. Cincin sederhana berisi 100 simpul berderajat 2 di mana-mana, jauh di bawah 50, dan toh merupakan siklus Hamilton. Begitulah gambaran umumnya: ada syarat cukup dan ada alasan kegagalan, dan di antaranya terbentang wilayah luas berisi graf yang hanya bisa diputuskan oleh pencarian.

Mengapa tidak ada uji cepat yang diketahui

Menentukan apakah sebuah graf punya siklus Hamilton bersifat NP-lengkap; ia salah satu dari 21 masalah dalam daftar Richard Karp tahun 1972. Metode yang menyelesaikannya dengan cepat untuk setiap graf akan menyelesaikan ribuan masalah lain dengan cepat pula, dan akan menuntaskan pertanyaan P lawan NP. Kontrasnya dengan lintasan Euler, yang memakai setiap sisi satu kali, mencolok: Euler menunjukkan pada 1736 bahwa menghitung simpul berderajat ganjil menuntaskan pertanyaan itu seketika. Metode eksak terbaik untuk siklus Hamilton masih memakan waktu eksponensial. Pemrograman dinamis atas semua himpunan bagian simpul, ditemukan oleh Richard Bellman dan oleh Michael Held dan Richard Karp pada 1962, memerlukan sekitar n² × 2ⁿ langkah, dan metode acak Andreas Björklund tahun 2010 sekitar 1,657ⁿ. Dalam praktik, runut-balik dengan pemangkasan yang baik menangani graf berisi beberapa puluh simpul, dan masalah pedagang keliling, yang mencari siklus Hamilton terpendek, adalah versi berbobot dari pertanyaan yang sama.

Kode Gray dan hiperkubus

Tulis bilangan 0 sampai 7 sebagai kode 3 bit dan hubungkan dua kode bila keduanya berbeda tepat satu bit: hasilnya adalah graf sebuah kubus. Sebuah siklus Hamilton melewatinya, misalnya 000, 001, 011, 010, 110, 111, 101, 100, mendaftar kedelapan kode sehingga masing-masing berbeda satu bit dari kode sebelumnya. Daftar semacam itu adalah kode Gray, dinamai menurut Frank Gray dari Bell Labs, yang menjelaskannya dalam paten yang diajukan pada 1947. Setiap hiperkubus punya satu: tulis kode dengan satu bit lebih sedikit, lalu daftar yang sama secara terbalik, dan letakkan 0 di depan paruh pertama dan 1 di depan paruh kedua. Pengenkode putar memakai kode Gray agar pembacaan yang diambil di antara dua posisi tidak pernah meleset lebih dari satu langkah. Kubus punya 6 siklus Hamilton dan hiperkubus 4 bit punya 1.344.

Jelajahi sendiri

Buka penjelajah lintasan Hamilton untuk mencoba sendiri teka-teki Hamilton, dengan cincin putus-putus yang menunjukkan ke mana Anda bisa melangkah, atau beralihlah ke Pencarian dan tonton runut-balik bekerja: lintasan tumbuh, garis putus merah menandai tempat ia berbalik, dan batang menghitung simpul telusur per panjang lintasan. Nyalakan dan matikan pemeriksaan jalan buntu, pemeriksaan keterhubungan, dan urutan Warnsdorff, bandingkan berapa banyak simpul telusur yang dibutuhkan masing-masing, hitung semua siklus sebuah graf kecil, atau gambar graf Anda sendiri dan lihat uji cepat mana yang berlaku.

Pertanyaan yang sering diajukan

Apakah graf dengan sirkuit Euler juga graf Hamilton, atau sebaliknya?

Tidak ada yang mengikuti dari yang lain. Dasi kupu-kupu, dua segitiga yang berbagi satu simpul, punya sirkuit Euler karena setiap derajatnya genap, tetapi tidak punya siklus Hamilton, sebab simpul bersama itu harus dilewati dua kali. Graf lengkap K₄ punya siklus Hamilton, tetapi keempat simpulnya berderajat 3, jadi ia tidak punya sirkuit Euler.

Tidak bisakah komputer mencoba saja semua urutan?

Hanya untuk graf kecil. Ada n! urutan dari n simpul, sekitar 2,4 × 10¹⁸ untuk 20. Runut-balik jauh lebih baik, karena ia hanya menyusuri sisi dan menyerah pada lintasan sebagian begitu buntu: ia menemukan seluruh 30 siklus dodekahedron bersimpul 20 dalam sekitar 1.400 langkah. Namun pada sebagian graf jumlah lintasan sebagian tetap tumbuh eksponensial, dan tidak ada metode yang diketahui bisa menghindarinya untuk setiap graf.

Apakah masalah lintasan Hamilton lebih mudah daripada masalah siklus?

Tidak, keduanya NP-lengkap. Masing-masing bisa diubah menjadi yang lain: tambahkan satu simpul baru yang terhubung ke setiap simpul lama, dan graf lama punya lintasan Hamilton tepat ketika graf baru punya siklus Hamilton. Sebaliknya, masalah siklus menjadi masalah lintasan dengan menambahkan salinan satu simpul, dengan tetangga yang sama, lalu memasang satu simpul ujung baru pada simpul itu dan satu lagi pada salinannya.

Mengapa perjalanan kuda pada papan 5 × 5 harus mulai pada warna sudut?

Dari 25 petak, 13 berwarna seperti sudut dan 12 berwarna lain, dan kuda berganti warna pada setiap langkah. Perjalanan melewati 25 petak berganti-ganti warna, jadi ia mulai dan berakhir pada warna yang petaknya lebih banyak. Aplikasi ini menemukan seluruh 1.728 perjalanan terbuka papan 5 × 5, atau 864 bila sebuah perjalanan dan kebalikannya dihitung satu, dan setiap perjalanan mulai dan berakhir pada petak berwarna sudut.

Siap mencobanya?

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

Buka penjelajah lintasan Hamilton