Pemeriksa Jalur Hamilton

Tentang Pemeriksa Jalur Hamilton

Pemeriksa Jalur Hamilton memutuskan apakah suatu graf mengandung jalur Hamilton — urutan yang mengunjungi setiap verteks tepat satu kali — atau siklus Hamilton, yang selain mengunjungi setiap simpul juga kembali ke verteks awal. Alat ini menggabungkan pengecekan struktural cepat (konektivitas, prasyarat derajat, teorema Dirac, teorema Ore) dengan pencarian backtracking yang disesuaikan dengan heuristik Warnsdorff, dan memvisualisasikan jalur saksi dengan animasi langkah-demi-langkah.

Apa Itu Jalur Hamilton?

Diberikan graf G = (V, E) dengan n verteks, sebuah jalur Hamilton adalah urutan teratur v₁, v₂, …, v_n dari semua verteks sedemikian sehingga setiap pasangan berurutan (v_i, v_i+1) adalah sisi dari G, dan setiap verteks muncul tepat satu kali. Jika sebagai tambahan (v_n, v₁) adalah sisi, maka urutan tersebut adalah siklus Hamilton.

Masalah ini dinamai dari William Rowan Hamilton, yang pada tahun 1857 menemukan permainan Icosian — teka-teki yang meminta penyelesai untuk menemukan siklus yang mengunjungi setiap verteks dodekahedron reguler tepat satu kali.

Mengapa Ini Sulit: NP-Completeness

Baik masalah keputusan jalur Hamilton maupun masalah keputusan siklus Hamilton adalah NP-complete (Karp, 1972). Kecuali P = NP, tidak ada algoritma waktu polinomial yang ada yang dapat menyelesaikan setiap kasus. Dalam kasus terburuk, backtracking menjelajahi pohon pencarian dengan ukuran hingga (n−1)! untuk sebuah siklus. Inilah sebabnya mengapa kalkulator membatasi input pada 20 verteks — sedikit peningkatan polinomial pada n menghasilkan peningkatan eksplosif dalam waktu eksekusi.

Dalam praktiknya, heuristik Warnsdorff (awalnya dirancang oleh Heinrich Warnsdorff pada tahun 1823 untuk masalah knight's tour) membuat pencarian jauh lebih cepat pada graf terstruktur: pada setiap langkah, algoritma memperluas jalur saat ini ke tetangga yang belum dikunjungi dengan jumlah tetangga yang belum dikunjungi paling sedikit. Aturan rakus ini menjaga pencarian agar tidak menemui jalan buntu dan sering kali menemukan tur Hamilton dengan nol backtracking pada graf yang berperilaku baik.

Kondisi Perlu — Penolakan Cepat

Sebelum menjalankan pencarian yang mahal, kalkulator menolak graf yang mustahil mengandung jalur Hamilton:

• Konektivitas. Jalur Hamilton harus mengunjungi setiap verteks, sehingga graf harus memiliki tepat satu komponen terhubung. Untuk graf berarah, diperlukan konektivitas lemah (mengabaikan arah panah).
• Derajat (tidak berarah). Maksimal dua verteks yang boleh memiliki derajat 1 — verteks tersebut adalah satu-satunya kandidat untuk titik ujung jalur. Untuk siklus Hamilton, setiap verteks harus memiliki derajat setidaknya 2.
• Derajat (berarah). Untuk jalur Hamilton, maksimal satu verteks boleh memiliki derajat-masuk 0 (awal) dan maksimal satu boleh memiliki derajat-keluar 0 (akhir). Untuk siklus Hamilton, setiap verteks harus memiliki derajat-masuk ≥ 1 dan derajat-keluar ≥ 1.

Aturan-aturan ini menolak banyak input yang sia-sia dalam waktu linear, menghindari upaya backtracking yang terbuang.

Kondisi Cukup — Teorema Klasik

Beberapa teorema klasik memberikan kondisi cukup (tetapi bukan perlu) yang menjamin adanya siklus Hamilton pada graf sederhana tidak berarah. Jika salah satu dari ini berlaku, kalkulator menandai hasilnya sebagai "MENJAMIN" bahkan tanpa menjalankan pencarian — meskipun ia tetap menunjukkan siklus saksi.

Teorema Dirac (1952)

Jika G adalah graf sederhana tidak berarah pada n ≥ 3 verteks dan setiap verteks memiliki derajat setidaknya n / 2, maka G memiliki siklus Hamilton.

Teorema Ore (1960)

Jika untuk setiap pasang verteks yang tidak bertetangga u dan v kita memiliki deg(u) + deg(v) ≥ n, maka G memiliki siklus Hamilton. Kondisi Ore secara ketat lebih lemah daripada Dirac, sehingga Ore mengimplikasikan Dirac.

Kegagalan kondisi Dirac atau Ore tidak berarti graf tersebut tidak memiliki siklus Hamilton — banyak graf yang tidak memenuhi keduanya tetapi tetap mengandung siklus Hamilton (misalnya, n-siklus sederhana memiliki derajat minimum 2, jauh di bawah n/2 untuk n yang besar).

Algoritma Pencarian di Dalamnya

Ketika pengecekan awal tidak menyelesaikan masalah, kalkulator menjalankan pencarian backtracking pada representasi ketetanggaan graf. Taktik utama:

1. Bitmask visited-set. Verteks yang dikunjungi disimpan sebagai bitmask (pengujian keanggotaan O(1) yang cepat hingga 20 verteks).
2. Heuristik Warnsdorff. Pada setiap ekstensi, tetangga dicoba berdasarkan urutan derajat belum dikunjungi yang tersisa (terkecil lebih dulu), meniru urutan "percabangan rendah".
3. Pemilihan akar. Untuk siklus Hamilton, hanya satu verteks awal yang diperlukan (siklus bersifat rotasi-invariant). Untuk jalur Hamilton, awal dicoba dalam urutan derajat-keluar yang meningkat — posisi yang paling jarang lebih dulu.
4. Anggaran langkah. Batas keras mencegah kasus patologis berjalan tanpa henti; UI melaporkan keputusan sebagai "habis waktu" jika anggaran habis.

Hamiltonian vs Eulerian

Sangat mudah untuk bingung antara masalah Hamilton dan Euler — mereka terdengar mirip tetapi secara mendasar berbeda:

Format Input yang Didukung

Daftar sisi

Satu sisi per baris, atau dipisahkan koma. Pemisah yang didukung: A-B, A B, A,B, A--B, A->B, A<-B. Gunakan -> untuk memaksakan interpretasi berarah.

Matriks ketetanggaan

Matriks persegi berisi nilai 0/1, satu baris per baris, dipisahkan spasi atau koma. Berikan label opsional di bidang Label matriks; jika tidak, A, B, C… akan digunakan secara otomatis.

Cara Menggunakan Pemeriksa Ini

1. Pilih format input — Daftar sisi untuk graf kecil yang ditulis tangan, Matriks ketetanggaan untuk tempelan dari kode atau buku teks.
2. Tempel graf Anda di area teks. Untuk input matriks, berikan label verteks jika diinginkan.
3. Pilih apa yang akan diperiksa: Jalur saja, Siklus saja, atau Keduanya dalam satu kali jalan.
4. Pilih tipe graf — Deteksi otomatis menyimpulkan keterarahan dari gaya panah (->) atau simetri matriks.
5. Klik Periksa Hamilton. Halaman hasil menunjukkan headline keputusan, pengecekan awal kondisi perlu, pengujian kondisi cukup Dirac / Ore, jalur saksi (jika ada), dan visualisasi interaktif.
6. Putar ulang saksi menggunakan kontrol Putar / Langkah. Perhatikan jalur yang menyala sisi demi sisi pada graf.

Contoh Pengerjaan — Graf Petersen

Graf Petersen yang terkenal (10 verteks, 15 sisi, reguler-3) adalah contoh buku teks dari graf dengan jalur Hamilton tetapi tidak ada siklus Hamilton. Tempelkan ini ke bidang daftar sisi dan klik Periksa:

Pemeriksa mengonfirmasi: Jalur Hamilton ditemukan (misal, 1 — 2 — 7 — 10 — 5 — 4 — 9 — 6 — 8 — 3), tetapi pencarian mendalam tidak menemukan cara untuk menutup loop kembali — hasil yang pertama kali dibuktikan pada tahun 1890-an.

Aplikasi Umum

• Perutean dan Traveling Salesman Problem (TSP) — setiap tur TSP adalah siklus Hamilton dalam graf berbobot lengkap.
• Perakitan genom — merekonstruksi urutan DNA dari pembacaan yang tumpang tindih dapat dimodelkan sebagai jalur Hamilton dalam graf tumpang tindih.
• Tata letak sirkuit — mengurutkan pin pada PCB untuk kabel dengan panjang minimum.
• AI Game dan penyelesaian teka-teki — knight's tour pada papan catur, permainan Icosian.
• Penjadwalan — mengurutkan tugas sedemikian rupa sehingga setiap tugas bertransisi secara layak ke tugas berikutnya.
• Pengajaran kombinatorik — mengilustrasikan NP-completeness dengan contoh kecil yang dapat diselesaikan secara manual.

Pertanyaan yang Sering Diajukan

Apa itu jalur Hamilton?

Jalur Hamilton adalah lintasan dalam graf yang mengunjungi setiap verteks tepat satu kali. Namanya diambil dari William Rowan Hamilton, yang mempelajari masalah ini pada graf dodekahedron pada tahun 1857. Memutuskan apakah jalur tersebut ada adalah masalah NP-complete, sehingga tidak ada algoritma yang diketahui dapat menyelesaikannya dalam waktu polinomial untuk semua graf.

Apa perbedaan antara siklus Hamilton dan jalur Hamilton?

Siklus Hamilton adalah jalur Hamilton yang kembali ke verteks awalnya, membentuk loop tertutup yang mengunjungi setiap verteks tepat satu kali. Setiap siklus Hamilton mengandung jalur Hamilton (cukup hilangkan sisi penutupnya), tetapi kebalikannya tidak berlaku: banyak graf memiliki jalur Hamilton tetapi tidak memiliki siklus Hamilton.

Apa yang dinyatakan oleh teorema Dirac?

Teorema Dirac (1952) menyatakan bahwa setiap graf sederhana tidak berarah pada n ≥ 3 verteks di mana setiap verteks memiliki derajat setidaknya n/2 mengandung siklus Hamilton. Ini adalah kondisi cukup tetapi bukan perlu: banyak graf yang gagal memenuhi ambang batas Dirac tetap memiliki siklus Hamilton.

Apa yang dinyatakan oleh teorema Ore?

Teorema Ore (1960) menyatakan bahwa jika, untuk setiap pasang verteks yang tidak bertetangga u dan v dalam graf sederhana pada n ≥ 3 verteks, jumlah derajat mereka setidaknya n, maka graf tersebut memiliki siklus Hamilton. Kondisi Ore lebih lemah dari Dirac, sehingga teorema Ore berlaku setiap kali teorema Dirac berlaku.

Mengapa pencarian dibatasi hingga 20 verteks?

Masalah keputusan jalur dan siklus Hamilton adalah NP-complete. Waktu eksekusi terburuk meningkat secara eksponensial dengan jumlah verteks. Dengan pruning dan heuristik Warnsdorff, kalkulator ini menangani banyak graf kecil hingga 20 verteks dengan cepat, tetapi contoh yang lebih sulit mungkin mengalami batas waktu. Di atas 20 verteks, Anda harus menggunakan penyelesai khusus seperti Concorde atau formulasi pemrograman integer.

Apa itu heuristik Warnsdorff?

Aturan Warnsdorff, diusulkan pada tahun 1823 untuk masalah knight's tour, mengatakan bahwa pada setiap langkah Anda harus mengunjungi verteks berikutnya yang memiliki tetangga belum dikunjungi paling sedikit. Aturan yang tampak rakus ini secara drastis memangkas pohon backtracking dalam praktiknya dan sering kali menemukan jalur Hamilton tanpa backtracking sama sekali pada graf reguler.

Apakah alat ini menemukan semua jalur Hamilton?

Tidak — alat ini menemukan satu jalur saksi atau siklus ketika ada. Menghitung jumlah total jalur Hamilton itu sendiri adalah masalah #P-complete dan jauh lebih sulit daripada masalah keputusan. Untuk enumerasi, alat khusus atau penyelesai pemrograman integer lebih tepat digunakan.

Bacaan Lebih Lanjut

• Jalur Hamilton — Wikipedia
• Masalah jalur Hamilton — Wikipedia
• Teorema Dirac pada siklus Hamilton — Wikipedia
• Teorema Ore — Wikipedia
• Aturan Warnsdorff — Wikipedia

Alat terkait lainnya:

Operasi matematika tingkat lanjut:

• Kalkulator Antilog
• Kalkulator Fungsi Beta
• Kalkulator Koefisien Binomial
• Kalkulator Distribusi Binomial
• Kalkulator Bitwise
• Kalkulator Teorema Limit Tengah
• Kalkulator Kombinasi
• Kalkulator Fungsi Kesalahan Pelengkap
• Kalkulator Bilangan Kompleks Unggulan
• Kalkulator Entropi Unggulan
• Kalkulator fungsi kesalahan
• Kalkulator Peluruhan Eksponensial
• Kalkulator Pertumbuhan Eksponensial Presisi Tinggi
• Kalkulator Integral Eksponensial
• kalkulator-eksponen-presisi-tinggi
• Kalkulator Faktorial
• Kalkulator Fungsi Gamma
• Kalkulator Rasio Emas
• Kalkulator Setengah Hidup
• Kalkulator Pertumbuhan Persentase
• Kalkulator Permutasi
• Kalkulator Distribusi Poisson
• Kalkulator Akar Polinomial dengan Langkah-Langkah Terperinci
• Kalkulator Probabilitas
• Kalkulator Distribusi Probabilitas
• Kalkulator Proporsi
• Kalkulator Rumus Kuadrat
• Kalkulator Ilmiah Unggulan
• Kalkulator Notasi Ilmiah
• Kalkulator Angka Penting Baru
• Kalkulator Jumlah Kubik
• Kalkulator Jumlah Angka Berurutan
• Kalkulator Jumlah Kuadrat
• Generator Tabel Kebenaran Baru
• Kalkulator Teori Himpunan Baru
• Generator Diagram Venn (3 Himpunan) Baru
• Kalkulator Teorema Sisa Cina Baru
• Kalkulator Fungsi Totien Euler Baru
• Kalkulator Algoritma Euklides Diperluas Baru
• Kalkulator Invers Multiplikatif Modular Baru
• Kalkulator Pecahan Lanjutan Baru
• Kalkulator Jalur Terpendek Dijkstra Baru
• Kalkulator Pohon Rentang Minimum Baru
• Validator Urutan Derajat Graf Baru
• Kalkulator Derangement Subfaktorial Baru
• Kalkulator Bilangan Stirling Baru
• Kalkulator Prinsip Sarang Merpati Baru
• Kalkulator Distribusi Stasioner Rantai Markov Baru
• Kalkulator Pembulatan Baru
• Kalkulator Distribusi Binomial Negatif Baru
• Kalkulator Permutasi dengan Pengulangan Baru
• Kalkulator Eksponensial Modular Baru
• Kalkulator Akar Primitif Baru
• Penyederhana Aljabar Boolean Baru
• Pemecah Peta Karnaugh (K-Map) Baru
• Kalkulator Pewarnaan Graf Baru
• Kalkulator Pengurutan Topologi Baru
• Kalkulator Matriks Ketetanggaan Baru
• Kalkulator Inklusi-Eksklusi Baru
• Pemecah Pemrograman Linear Baru
• Pemecah Masalah Penjual Keliling (TSP) Baru
• Pemeriksa Jalur Hamilton Baru