Drum
Noduri explorate
Ciclu hamiltonian
Drum hamiltonian

Mod

    Scop

    Mai multe despre drumurile și ciclurile hamiltoniene

    Explorator de drumuri hamiltoniene

    În 1857 William Rowan Hamilton a inventat o enigmă: să mergi pe muchiile unui dodecaedru astfel încât să treci prin fiecare dintre cele 20 de colțuri exact o dată și să termini de unde ai plecat. Un astfel de traseu se numește azi ciclu hamiltonian. Este ușor de verificat și, în general, greu de găsit. Trasează unul chiar tu pe dodecaedrul lui Hamilton, pe o tablă de șah sau pe un graf pe care îl desenezi, ori privește o căutare cu revenire cum îl vânează, numără fundăturile în care intră și vezi cât de mult scurtează căutarea câteva verificări simple. Alege un graf și un scop: un ciclu care revine la punctul de plecare sau un drum. Trasare: dă clic pe un vârf ca să începi, apoi pe câte un vecin; inelele punctate arată unde poți merge. Un clic pe ultimul vârf, Înapoi sau Anulează face un pas înapoi, iar Indiciu arată un pas următor care încă poate fi dus la capăt. Căutare: cu Pornește sau Pas rulează o căutare cu revenire, care adaugă vârfuri până se blochează și apoi se întoarce; liniuțele roșii arată revenirile, iar barele numără nodurile după lungimea drumului. Înainte de pornire, un clic pe un vârf alege de unde începe. Casetele pornesc și opresc tăierea, Compară rulează aceeași căutare cu ea și fără ea, iar Numără toate numără fiecare ciclu sau drum al unui graf mic. Editare: dă clic pentru a adăuga un vârf, dă clic pe două vârfuri pentru a le uni sau despărți, trage pentru a muta unul, iar Șterge înlătură vârful selectat.

    Cum funcționează

    1. Alege un graf, de pildă dodecaedrul lui Hamilton, graful lui Petersen sau un tur al calului, ori desenează-l pe al tău în Editare, și alege drept scop un ciclu sau un drum.
    2. În Trasare, dă clic pe un vârf ca să începi, apoi pe câte un vecin. Înapoi și Anulează fac un pas înapoi, iar Indiciu arată un pas următor care încă poate fi dus la capăt.
    3. În Căutare, apasă Pornește sau Pas ca să privești revenirea căutând un traseu, pornește și oprește tăierea și apasă Compară pentru a vedea câte noduri cere fiecare variantă.

    Hamilton față de Euler

    Un drum eulerian folosește fiecare muchie o dată; un drum hamiltonian trece prin fiecare vârf o dată. Sună asemănător, dar se poartă foarte diferit. Dacă un graf conex are un drum eulerian se decide numărând vârfurile de grad impar, cum a arătat Euler în 1736: are unul când nu există niciunul sau există două. Pentru drumurile hamiltoniene nu se cunoaște o asemenea regulă. A decide dacă un graf are un ciclu hamiltonian este NP-complet, una dintre cele 21 de probleme din lista lui Richard Karp din 1972, așa că o metodă rapidă pentru el ar da metode rapide pentru mii de alte probleme grele. Ceea ce există sunt condiții care decid unele grafuri. Teorema lui Dirac din 1952 garantează un ciclu hamiltonian când fiecare vârf are gradul cel puțin n/2, iar cea a lui Ore din 1960 când două vârfuri neunite au întotdeauna grade cu suma cel puțin n; un vârf de grad 1, un punct de articulație sau două clase de culoare de mărimi diferite îl exclud.

    Cum lucrează căutarea

    Revenirea construiește drumul câte un vârf o dată și, când se blochează, retrage ultimul pas și încearcă vecinul următor. Găsește întotdeauna un ciclu hamiltonian dacă există unul, dar numărul drumurilor parțiale poate crește exponențial. Pe grila 5 × 5, care nu are ciclu hamiltonian, revenirea simplă explorează 153.745 de noduri până să fie sigură. Două verificări opresc devreme drumurile fără speranță: un vârf nevizitat cu mai puțin de doi vecini liberi nu mai încape într-un ciclu, iar când vârfurile nevizitate se desfac în părți separate, niciun drum singur nu le poate acoperi. Cu amândouă, aceeași demonstrație ia 1.761 de noduri. Regula lui Warnsdorff din 1823, care încearcă întâi vecinul cu cele mai puține mutări următoare, găsește un tur al calului pe 8 × 8 dintr-un colț în 64 de mutări fără nicio fundătură.

    Întrebări frecvente

    Care este diferența dintre un drum hamiltonian și un ciclu hamiltonian?

    Un drum hamiltonian trece prin fiecare vârf al unui graf exact o dată. Un ciclu hamiltonian face același lucru și apoi se întoarce printr-o muchie în plus acolo de unde a plecat, deci poate începe în oricare dintre vârfurile sale. Orice graf cu un ciclu hamiltonian are un drum hamiltonian (scoate o muchie a ciclului), dar nu și invers: graful lui Petersen are drumuri hamiltoniene și niciun ciclu hamiltonian.

    Are dodecaedrul un ciclu hamiltonian?

    Da, 30, numărând fiecare ciclu o dată, oricare ar fi punctul de plecare și sensul. Hamilton a făcut din asta jocul icosian în 1857, o tablă cu cele 20 de colțuri ale unui dodecaedru turtit marcate cu consoane, și a vândut drepturile cu 25 de lire producătorului londonez de jucării John Jaques and Son. Numără toate găsește cele 30 de cicluri în circa 1.400 de noduri.

    De ce o grilă 5 × 5 nu are ciclu hamiltonian?

    Colorează cele 25 de puncte ca o tablă de șah: 13 primesc o culoare și 12 cealaltă, iar fiecare pas merge la cealaltă culoare. Un ciclu alternează culorile pe tot ocolul, deci are nevoie de tot atâtea dintr-o culoare cât din cealaltă, ceea ce 13 și 12 nu dau. Același argument merge pentru orice grilă cu un număr impar de puncte, pentru un cal pe o tablă 5 × 5 sau 7 × 7 (calul schimbă mereu culoarea pătratului) și pentru graful lui Herschel, ale cărui două clase au 6 și 5 vârfuri. Un drum hamiltonian rămâne posibil: începe și se sfârșește pe culoarea mai numeroasă.

    Cum găsește regula lui Warnsdorff un tur al calului?

    H. C. von Warnsdorff a propus în 1823 ca mereu calul să fie mutat pe pătratul din care va avea cele mai puține mutări următoare. Pătratele de lângă margini și colțuri, ușor de izolat, sunt astfel vizitate devreme, cât calul mai poate ajunge la ele. Regula este una practică, nu o garanție, iar egalitățile trebuie rupte cumva, dar pe o tablă 8 × 8 de obicei termină un tur fără să se întoarcă. Împreună cu revenirea, ca în această aplicație, găsește tururi deschise de la 5 × 5 în sus și tururi închise pe tablele 6 × 6 și 8 × 8.

    Câte cicluri hamiltoniene are un graf complet?

    (n − 1)!/2 pentru n ≥ 3. Fixează vârful de plecare; celelalte n − 1 pot urma în orice ordine, iar fiecare ciclu este numărat de două ori, o dată pentru fiecare sens. K₆ are 5!/2 = 60, iar K₁₀ are 181.440. Acestea sunt tururile dintre care trebuie să aleagă un comis-voiajor, și de aceea încercarea tuturor încetează atât de repede să fie posibilă.

    Ești gata să încerci?

    Deschide PictorX în browser – fără instalare și fără card de credit.

    Mergi la editor