Lanțuri și cicluri euleriene și hamiltoniene

Într-un graf neorientat, un lanț eulerian parcurge fiecare muchie exact o dată; un ciclu eulerian revine la vârful de plecare. Un lanț hamiltonian vizitează fiecare vârf exact o dată; ciclul hamiltonian revine la început. Într-un graf orientat, traseul se numește drum, iar direcția arcelor trebuie respectată. Euler privește muchiile sau arcele, Hamilton privește vârfurile. Lungimea unui lanț sau drum neponderat este numărul de muchii sau arce parcurse.

Pentru un graf neorientat, vârfurile care au muchii trebuie să fie în aceeași componentă conexă. Există ciclu eulerian dacă și numai dacă toate gradele sunt pare; există lanț eulerian deschis dacă și numai dacă exact două grade sunt impare, iar acele vârfuri sunt capetele lanțului.

Exemplu construit: ia muchiile $AB,BC,CD,DA,CE$. (1) Gradele sunt $\mathrm{deg}A=2$, $\mathrm{deg}B=2$, $\mathrm{deg}C=3$, $\mathrm{deg}D=2$, $\mathrm{deg}E=1$. (2) Doar $C$ și $E$ au grad impar, deci pornești dintr-unul și termini în celălalt. (3) Lanțul $E-C-B-A-D-C$ folosește fiecare dintre cele cinci muchii o singură dată; lungimea lui este $5$. Nu există ciclu eulerian, deoarece două grade sunt impare. Există însă lanț hamiltonian $E-C-B-A-D$, care vizitează cele cinci vârfuri o dată; nu există ciclu hamiltonian fiindcă $E$ are gradul $1$.

Criteriul gradelor, dat de Euler, a apărut în $1736$, din problema podurilor din Königsberg, și este considerată începutul teoriei grafurilor. Exemplu rezolvat. Problema podurilor din Königsberg: cele patru zone de uscat sunt vârfuri, iar cele șapte poduri sunt muchii; gradele sunt $3,3,3,5$.

1. Toate cele patru grade sunt impare, deci sunt patru vârfuri de grad impar.
2. Un lanț eulerian cere cel mult două vârfuri de grad impar.
3. Deci nu se poate trece o singură dată peste fiecare pod, nici cu întoarcere, nici fără.

Exemplu rezolvat. Graful complet $K_5$ are $5$ vârfuri, fiecare de grad $4$. Este eulerian? Dar hamiltonian?

1. Gradele sunt toate pare și graful este conex, deci are ciclu eulerian, care folosește cele $\frac{5\cdot 4}{2}=10$ muchii.
2. Un ciclu hamiltonian vizitează fiecare vârf o dată și revine; $A-B-C-D-E-A$ este unul, deci $K_5$ este și hamiltonian.
3. Pentru $K_4$, gradele sunt $3,3,3,3$, impare, deci nu are ciclu eulerian, dar are ciclu hamiltonian $A-B-C-D-A$.

Exemplu rezolvat. Graful are vârfurile $1,2,3,4,5$ și muchiile $12,23,34,45,51,13$. Stabilește dacă are lanț sau ciclu eulerian și dacă are ciclu hamiltonian.

1. Gradele sunt $\mathrm{deg}1=3$, $\mathrm{deg}2=2$, $\mathrm{deg}3=3$, $\mathrm{deg}4=2$, $\mathrm{deg}5=2$.
2. Exact două vârfuri, $1$ și $3$, au grad impar, deci există lanț eulerian cu capetele $1$ și $3$, dar nu există ciclu eulerian.
3. Lanțul $1-2-3-4-5-1-3$ folosește fiecare dintre cele $6$ muchii o singură dată; lungimea lui este $6$.
4. Ciclul $1-2-3-4-5-1$ trece o singură dată prin fiecare vârf, deci graful are ciclu hamiltonian, de lungime $5$.

Exemplu rezolvat. Graful cu muchiile $AB,BC,CD$ are gradele $1,2,2,1$. Lanțul $A-B-C-D$ este eulerian, fiindcă parcurge cele $3$ muchii o dată, și hamiltonian, fiindcă vizitează cele $4$ vârfuri o dată; lungimea lui este $3$. Nu are niciun ciclu, deci nici eulerian, nici hamiltonian.

Caz invers. Două triunghiuri $ABC$ și $CDE$ cu vârful comun $C$ au gradele $2,2,4,2,2$, deci ciclul eulerian $C-A-B-C-D-E-C$ există. Ciclu hamiltonian nu există, fiindcă ar trece de două ori prin $C$.

Greșeli frecvente

• Greșit: dacă un graf are ciclu eulerian, are și ciclu hamiltonian.
  Corect: sunt probleme independente; $K_4$ are ciclu hamiltonian, dar nu eulerian (grade impare).
• Greșit: un lanț eulerian trebuie să viziteze fiecare vârf o singură dată.
  Corect: parcurge fiecare muchie o singură dată și poate reveni într-un vârf.
• Greșit: gradele pare garantează un ciclu hamiltonian.
  Corect: regula gradelor pare, împreună cu conexitatea, caracterizează ciclul eulerian.

Înainte și după