De ce contează?
Un poștaș vrea să parcurgă fiecare stradă din cartier exact o dată și să se întoarcă acasă — fără să treacă de două ori pe aceeași stradă. E aceeași provocare ca desenatul unei figuri fără să ridici creionul de pe hârtie. În secolul XVIII, locuitorii din Königsberg și-au pus întrebarea despre cele șapte poduri ale orașului: poți să te plimbi traversând fiecare pod exact o dată? Euler a demonstrat că răspunsul depinde doar de câte poduri pleacă din fiecare mal — un criteriu pe care îl poți verifica dintr-o privire, fără să încerci niciun traseu.
Ce este
Un ciclu eulerian este un ciclu care folosește fiecare muchie a grafului exact o dată și se întoarce în nodul de start. Un lanț eulerian face același lucru, dar pornește și se termină în noduri diferite. Cheia e să gândești în muchii, nu în noduri: muchiile sunt străzi pe care trebuie să mergi, iar prin noduri poți trece de câte ori e nevoie.
Euler a descoperit un criteriu surprinzător de simplu:
- Ciclu eulerian există dacă și numai dacă graful e conex (mai exact: toate muchiile stau într-o singură componentă) și toate nodurile au grad par.
- Lanț eulerian (nu neapărat ciclu) există dacă și numai dacă graful e conex și are exact 2 noduri de grad impar — ele vor fi obligatoriu capetele lanțului.
De ce grad par? Pentru că fiecare trecere printr-un nod consumă exact 2 muchii: una pe care intri și una pe care ieși. Muchiile unui nod se împerechează deci două câte două — o pereche pentru fiecare vizită. Dacă un nod are un număr impar de muchii, la un moment dat rămâi blocat în el: ai intrat, dar nu mai ai pe unde ieși. Singura excepție permisă: capetele unui lanț, unde „pleci fără să te întorci" — de aceea exact ele pot avea grad impar.
Compară cu graful hamiltonian (ciclu prin fiecare nod exact o dată): pentru acela nu se cunoaște niciun criteriu rapid — verificarea e o problemă NP-completă. Graful eulerian, în schimb, se verifică în timp liniar: numeri gradele și testezi conexitatea. Două probleme care sună aproape la fel, dar una e ușoară și cealaltă e grea — o distincție pe care examinatorii o adoră.