Drumuri și cicluri hamiltoniene explicate
Desenează cinci puncte în cerc, unește fiecare cu cei doi vecini ai săi, și poți face ocolul trecând o dată prin fiecare punct și ajungând acasă: un ciclu hamiltonian. Adaugă câteva muchii sau scoate câteva și întrebarea devine surprinzător de grea. Dacă un graf are un astfel de ciclu este una dintre cele mai cunoscute probleme la care niciun computer nu știe încă să răspundă repede pentru orice graf.
Fiecare vârf o dată
Un graf este o mulțime de puncte, vârfurile, unite prin linii, muchiile. Un drum hamiltonian merge pe muchii și trece prin fiecare vârf exact o dată; un ciclu hamiltonian se întoarce în plus acolo de unde a plecat, deci are tot atâtea muchii câte vârfuri. Un graf cu un ciclu hamiltonian se numește hamiltonian. A verifica un traseu propus e ușor: numără vârfurile și privește fiecare pas. A găsi unul, sau a dovedi că nu există niciunul, este partea grea, fiindcă numărul ordinilor în care pot fi vizitate vârfurile crește ca n!, deja 2,4 × 10¹⁸ pentru 20 de vârfuri.
Jocul icosian al lui Hamilton
William Rowan Hamilton, matematicianul irlandez care a descoperit cuaternionii, a inventat jocul icosian în 1857. Tabla lui arăta un dodecaedru turtit în plan, cu cele 20 de colțuri marcate cu consoane, iar sarcina principală era să așezi cuie numerotate de la 1 la 20 pe colțuri astfel încât numerele consecutive, precum și 20 și 1, să fie unite prin muchii. Hamilton a vândut drepturile cu 25 de lire producătorului londonez de jucării John Jaques and Son, care l-a scos în 1859; s-a vândut prost. Enigma are 30 de soluții, numărând un ciclu o dată, oricare ar fi punctul de plecare și sensul. Întrebarea însăși nu era nouă: Thomas Kirkman întrebase ce poliedre au un ciclu prin toate colțurile lor într-o lucrare trimisă la Royal Society în 1855 și arătase unul care nu are.
Tururile calului
Un tur al calului mută un cal de șah astfel încât să ajungă pe fiecare pătrat exact o dată: un drum hamiltonian în graful ale cărui vârfuri sunt pătratele și ale cărui muchii sunt mutările calului. Un tur închis se termină la o mutare de cal de punctul de plecare, adică un ciclu hamiltonian. Jucătorii de șah puneau astfel de probleme acum peste o mie de ani, iar Euler le-a studiat într-o lucrare din 1759. În 1823 H. C. von Warnsdorff a propus să mergi mereu pe pătratul cu cele mai puține mutări următoare; această regulă simplă termină de obicei un tur al unei table 8 × 8 fără să se întoarcă. Calul schimbă mereu culoarea pătratului, deci un tur închis are nevoie de tot atâtea pătrate deschise câte închise, ceea ce exclude tablele cu un număr impar de pătrate. Allen Schwenk a arătat în 1991 exact ce table dreptunghiulare au un tur închis; dintre cele pătrate, oricare cu o latură pară de 6 sau mai mult. Tabla obișnuită de șah are 13.267.364.410.532 de tururi închise, numărate de Brendan McKay în 1997.
Grafuri fără ciclu hamiltonian
Cele mai rapide dovezi că nu există ciclu sunt argumente de numărare. Dacă vârfurile pot fi colorate cu două culori astfel încât fiecare muchie să unească culori diferite, un ciclu alternează și are nevoie de tot atâtea vârfuri din fiecare culoare; o grilă 5 × 5 are 13 dintr-una și 12 din cealaltă, deci nu are ciclu hamiltonian. Un punct de articulație, a cărui scoatere rupe graful, ar trebui străbătut de două ori, iar un vârf de grad 1 nu poate fi străbătut deloc. Unele grafuri scapă tuturor acestor argumente. Graful lui Petersen, publicat de Julius Petersen în 1898, are 10 vârfuri de grad 3 și niciun ciclu hamiltonian, și totuși ștergerea oricărui vârf lasă un graf care are unul; este cel mai mic astfel de graf hipohamiltonian. Graful lui Herschel, numit după Alexander Stewart Herschel, care a scris despre jocul icosian în 1862, are 11 vârfuri și 18 muchii și este graful unui poliedru cu nouă fețe patrulatere. Niciun poliedru cu mai puține colțuri nu duce lipsă de ciclu hamiltonian. În 1884 Peter Guthrie Tait a presupus că orice poliedru cu trei muchii în fiecare colț are unul; W. T. Tutte a găsit în 1946 un contraexemplu cu 46 de vârfuri.
Condiții care garantează unul
Dacă un graf are multe muchii, un ciclu hamiltonian este sigur. Gabriel Dirac a demonstrat în 1952 că un graf cu n ≥ 3 vârfuri în care fiecare vârf are gradul cel puțin n/2 are unul, iar Øystein Ore a slăbit condiția în 1960: e de ajuns ca două vârfuri neunite să aibă întotdeauna grade cu suma cel puțin n. Ambele condiții merg doar într-un sens. Un simplu inel de 100 de vârfuri are peste tot gradul 2, mult sub 50, și totuși este un ciclu hamiltonian. Așa arată tabloul general: există condiții suficiente și există motive de eșec, iar între ele se întinde un teritoriu larg de grafuri pe care numai o căutare le poate decide.
De ce nu se cunoaște un test rapid
A decide dacă un graf are un ciclu hamiltonian este NP-complet; a fost una dintre cele 21 de probleme din lista lui Richard Karp din 1972. O metodă care l-ar rezolva repede pentru orice graf ar rezolva repede și mii de alte probleme și ar lămuri întrebarea P față de NP. Contrastul cu drumurile euleriene, care folosesc fiecare muchie o dată, este izbitor: Euler a arătat în 1736 că numărarea vârfurilor de grad impar lămurește acea întrebare pe loc. Cele mai bune metode exacte pentru ciclurile hamiltoniene cer în continuare timp exponențial. Programarea dinamică peste toate submulțimile de vârfuri, găsită de Richard Bellman și de Michael Held și Richard Karp în 1962, cere aproximativ n² × 2ⁿ pași, iar metoda aleatorizată a lui Andreas Björklund din 2010 aproximativ 1,657ⁿ. În practică, revenirea cu o tăiere bună se descurcă cu grafuri de câteva zeci de vârfuri, iar problema comis-voiajorului, care caută cel mai scurt ciclu hamiltonian, este versiunea cu ponderi a aceleiași întrebări.
Codurile Gray și hipercubul
Scrie numerele de la 0 la 7 ca niște coduri de 3 biți și unește două coduri când diferă exact printr-un bit: rezultatul este graful unui cub. Un ciclu hamiltonian prin el, de pildă 000, 001, 011, 010, 110, 111, 101, 100, înșiră toate cele opt coduri astfel încât fiecare diferă de cel dinainte printr-un singur bit. O asemenea listă este un cod Gray, numit după Frank Gray de la Bell Labs, care l-a descris într-un brevet depus în 1947. Orice hipercub are unul: scrie codurile cu un bit mai puțin, apoi aceeași listă invers, și pune un 0 înaintea primei jumătăți și un 1 înaintea celei de-a doua. Codificatoarele rotative folosesc coduri Gray pentru ca o citire luată între două poziții să nu greșească niciodată cu mai mult de un pas. Cubul are 6 cicluri hamiltoniene, iar hipercubul de 4 biți are 1.344.
Încearcă singur
Deschide exploratorul de drumuri hamiltoniene ca să încerci singur enigma lui Hamilton, cu inele punctate care arată unde poți merge, ori treci la Căutare și privește revenirea lucrând: drumul crește, liniuțe roșii marchează unde se întoarce, iar barele numără nodurile după lungimea drumului. Pornește și oprește verificarea fundăturilor, verificarea conexiunii și ordinea lui Warnsdorff, compară câte noduri cere fiecare, numără toate ciclurile unui graf mic sau desenează-ți propriul graf și vezi care dintre testele rapide se aplică.
Întrebări frecvente
Un graf cu un circuit eulerian este și hamiltonian, sau invers?
Niciunul nu decurge din celălalt. Papionul, două triunghiuri cu un vârf comun, are un circuit eulerian fiindcă orice grad este par, dar niciun ciclu hamiltonian, de vreme ce vârful comun ar trebui străbătut de două ori. Graful complet K₄ are cicluri hamiltoniene, dar toate cele patru vârfuri au gradul 3, deci nu are circuit eulerian.
Nu poate un computer să încerce pur și simplu toate ordinile?
Doar la grafuri mici. Există n! ordini ale n vârfuri, circa 2,4 × 10¹⁸ pentru 20. Revenirea se descurcă mult mai bine, fiindcă urmează doar muchii și abandonează un drum parțial de îndată ce se blochează: găsește toate cele 30 de cicluri ale dodecaedrului cu 20 de vârfuri în circa 1.400 de pași. Dar la unele grafuri numărul drumurilor parțiale crește oricum exponențial și nu se cunoaște nicio metodă care să evite asta pentru orice graf.
Este problema drumului hamiltonian mai ușoară decât cea a ciclului?
Nu, amândouă sunt NP-complete. Fiecare se transformă în cealaltă: adaugă un vârf nou unit cu fiecare vârf vechi, iar graful vechi are un drum hamiltonian exact atunci când cel nou are un ciclu hamiltonian. În celălalt sens, o problemă de ciclu devine una de drum adăugând o copie a unui vârf, cu aceiași vecini, și un vârf terminal nou legat de vârf și altul de copia lui.
De ce un tur al calului pe o tablă 5 × 5 trebuie să înceapă pe culoarea colțurilor?
Din cele 25 de pătrate, 13 au culoarea colțurilor și 12 cealaltă, iar calul schimbă culoarea la fiecare mutare. Un tur peste 25 de pătrate alternează culorile, deci începe și se sfârșește pe culoarea care are mai multe pătrate. Aplicația găsește toate cele 1.728 de tururi deschise ale tablei 5 × 5, adică 864 dacă un tur și inversul lui se numără ca unul, și fiecare începe și se sfârșește pe un pătrat în culoarea colțurilor.
Ești gata să încerci?
Deschide PictorX în browser – fără instalare și fără card de credit.
Deschide exploratorul de drumuri hamiltoniene