Drumuri și circuite euleriene explicate

Unele figuri se pot desena dintr-o singură trăsătură, fără să ridicați creionul și fără să treceți de două ori peste o linie, iar altele nu, oricât ați încerca. Nici nu trebuie să încercați: numărați liniile din fiecare colț. Dacă cel mult două colțuri au un număr impar de linii, figura poate fi desenată, iar în acele colțuri trebuie să înceapă și să se termine trăsătura. Leonhard Euler a găsit această regulă în 1736 și cu ea a întemeiat teoria grafurilor.

Cele șapte poduri din Königsberg desenate ca un graf: patru bucăți de uscat drept vârfuri, toate patru cu un număr impar de poduri, pe ambele maluri ale unui râu
Cele șapte poduri din Königsberg desenate ca un graf: patru bucăți de uscat drept vârfuri, toate patru cu un număr impar de poduri, pe ambele maluri ale unui râu

Cele șapte poduri din Königsberg

Orașul prusac Königsberg, azi Kaliningrad, se întindea pe ambele maluri ale râului Pregel și pe două insule din el, Kneiphof și Lomse. Șapte poduri legau cele patru părți: câte două de la Kneiphof spre fiecare mal, unul între cele două insule și câte unul de la Lomse spre fiecare mal. Locuitorii se întrebau dacă o plimbare poate trece peste fiecare pod exact o dată. Euler a răspuns într-o lucrare prezentată Academiei din Sankt Petersburg în 1735 și tipărită în 1741: nu poate. Pasul lui hotărâtor a fost să lase deoparte totul în afară de părțile orașului și podurile dintre ele, adică exact ce face un graf: un vârf pentru fiecare bucată de uscat și o muchie pentru fiecare pod, cu două muchii acolo unde două poduri leagă aceleași locuri.

Portretul lui Leonhard Euler
Portretul lui Leonhard Euler
Portrait of Leonhard Euler
Portrait of Leonhard Euler

Regula gradelor

Gradul unui vârf este numărul de muchii care ajung la el. O trăsătură care trece printr-un vârf intră pe o muchie și iese pe alta, deci folosește muchiile acelui vârf în perechi. Doar primul și ultimul vârf al trăsăturii pot păstra o muchie fără pereche. Așadar un vârf de grad impar trebuie să fie începutul sau sfârșitul trăsăturii. Kneiphof avea cinci poduri, iar celelalte trei părți câte trei: patru vârfuri impare, cu două prea multe. În general, un graf conex are un circuit eulerian, o trăsătură care se termină unde a început, când toate gradele sunt pare, și un drum eulerian când exact două grade sunt impare, de la unul la celălalt. Numărul vârfurilor impare nu este niciodată unu, nici alt număr impar: fiecare muchie adaugă 2 la suma tuturor gradelor, deci suma este pară. Și asta a observat-o Euler, iar astăzi se numește lema strângerilor de mână.

De ce regula este de ajuns

Euler a arătat că o figură cu mai mult de două vârfuri impare nu poate fi trasată și a spus, fără demonstrație, că orice altă figură conexă poate. Demonstrația a venit de la Carl Hierholzer, matematician german mort tânăr în 1871; lucrarea lui a apărut în 1873. Începeți dintr-un vârf impar, dacă există, altfel de oriunde, și mergeți pe muchii nefolosite cât puteți. Fiindcă orice alt vârf are grad par, vă puteți bloca doar în vârful final. Dacă rămân muchii, unele ating traseul de până atunci, pentru că figura este conexă. Dintr-un astfel de vârf mergeți din nou până vă blocați, ceea ce acum se întâmplă înapoi în acel vârf, și inserați acolo bucla în traseu. Repetați până nu mai rămâne nicio muchie. Demonstrația este totodată cel mai rapid algoritm: fiecare muchie este privită de un număr fix de ori.

Algoritmul lui Fleury: nu vă ardeți podurile

O trăsătură poate eșua chiar și pe o figură care poate fi desenată. Luați două triunghiuri legate printr-o singură muchie și începeți dintr-un colț al primului: dacă treceți la al doilea triunghi înainte de a-l termina pe primul, nu vă mai puteți întoarce. Muchia de legătură este un pod: îndepărtarea ei desparte figura în două. Algoritmul lui Fleury din 1883 dă o regulă: în fiecare vârf luați o muchie care nu este pod pentru muchiile rămase, dacă nu cumva nu există alta. Urmând-o, terminați întotdeauna. Verificarea podului cere timp, așa că algoritmul lui Fleury este mai lent decât al lui Hierholzer, dar este cel pe care îl puteți urma cu creionul, iar indiciul din aplicație îl folosește.

Repararea unei figuri

O figură cu k vârfuri impare cere k/2 trăsături. Ca să o desenați dintr-una singură, adăugați muchii care împerechează vârfurile impare: fiecare muchie nouă face pare două vârfuri impare. Cu k/2 − 1 muchii rămân două vârfuri impare și iese un drum; cu k/2 nu rămâne niciunul și iese un circuit. Un pod în plus la Königsberg, între oricare două dintre cele patru părți, ar fi făcut plimbarea posibilă, iar două ar fi îngăduit un tur complet. Istoria a făcut ceva asemănător: două poduri s-au pierdut în al Doilea Război Mondial, iar două au fost înlocuite de o șosea modernă, iar cele cinci poduri care stau azi în locurile vechi pot fi trecute câte o dată fiecare, de pe o insulă pe cealaltă.

Numărarea modurilor

Casa lui Moș Nicolae, un pătrat cu ambele diagonale și un acoperiș, este varianta germană pentru copii a jocului: „Das ist das Haus vom Ni-ko-laus” are opt silabe, câte una pentru fiecare linie. Cele două colțuri de jos sunt singurele vârfuri impare, iar din fiecare există exact 44 de moduri de a o desena, 88 în total. Pentru grafuri orientate, numărul circuitelor euleriene are o formulă, teorema BEST, după numele lui de Bruijn, van Aardenne-Ehrenfest, Smith și Tutte. Pentru grafuri obișnuite nu se cunoaște o astfel de formulă, iar numărarea este socotită grea în general, așa că aplicația numără figurile mici încercând fiecare mod și sărind peste pașii care ar tăia figura în două.

Unde se folosesc drumurile euleriene

Un plug de zăpadă, o mașină de măturat sau un poștaș vrea să parcurgă fiecare stradă o dată și să se întoarcă. Dacă fiecare intersecție are un număr par de străzi, un circuit eulerian rezolvă problema; altfel, unele străzi trebuie parcurse de două ori, iar alegerea celor mai ieftine este problema poștașului chinez, pusă de Meigu Guan în 1962. Un plotter cu peniță sau o mașină de tăiat cu laser câștigă timp trasând cât mai multe linii fără ridicare. În secvențierea genomului, milioane de fragmente scurte de ADN sunt îmbinate căutând un drum eulerian într-un graf de Bruijn, în care fiecare fragment este o muchie. Iar aceeași regulă spune ce desene dintr-o carte de jocuri merită încercate.

Încercați

Deschideți căutătorul de drumuri euleriene ca să trasați singur douăsprezece figuri, de la Königsberg în 1736 și astăzi până la stele, pătrate unul în altul și un cub, sau desenați-le pe ale dumneavoastră cu muchii paralele. Vârfurile impare sunt pline, fiecare vârf își arată gradul, iar regula gradelor de sub figură spune ce este posibil și ce muchii ar repara figura. Dacă vă blocați, aplicația spune dacă ați început din vârful greșit sau ați trecut un pod prea devreme, și la ce pas. Indiciu dă o muchie sigură, iar Rezolvă desenează figura cu algoritmul lui Fleury, arătând verificarea podului, sau cu al lui Hierholzer, arătând fiecare inserare.

Întrebări frecvente

Un drum eulerian este același lucru cu un drum hamiltonian?

Nu. Un drum eulerian folosește fiecare muchie o dată și poate trece de mai multe ori printr-un vârf; un drum hamiltonian trece o dată prin fiecare vârf și nu trebuie să folosească fiecare muchie. Dacă un graf are drum eulerian se află imediat numărând vârfurile impare, dar pentru drumurile hamiltoniene nu se cunoaște niciun test rapid, iar găsirea unuia este una dintre problemele grele clasice ale informaticii.

Regula gradelor rămâne valabilă când două vârfuri sunt legate prin mai multe muchii?

Da. Fiecare muchie contează la gradul ambelor capete, fie că o altă muchie leagă aceleași două vârfuri, fie că nu. Königsberg este un astfel de multigraf, cu două poduri de la Kneiphof spre fiecare mal. O muchie de la un vârf la el însuși, o buclă, adaugă 2 la gradul lui și nu schimbă niciodată paritatea.

Dar cu străzile cu sens unic?

Într-un graf orientat fiecare muchie are un sens, iar regula compară muchiile care intră în fiecare vârf cu cele care ies. Există un circuit eulerian când fiecare vârf are tot atâtea muchii care intră câte ies și muchiile stau împreună, și un drum eulerian când un vârf are o muchie în plus la ieșire, altul una în plus la intrare, iar toate celelalte sunt echilibrate. Drumul merge atunci de la primul la al doilea.

Poate exista o figură cu exact un vârf impar?

Nu. Gradele tuturor vârfurilor adunate dau dublul numărului de muchii, fiindcă fiecare muchie are două capete. Suma aceasta este pară, deci și numărul gradelor impare din ea trebuie să fie par: 0, 2, 4 și așa mai departe, niciodată 1 sau 3.

Ești gata să încerci?

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

Deschideți căutătorul de drumuri euleriene