Grafuri orientate și teorema lui Dirac

Lecția continuă „Lanțuri și cicluri euleriene și hamiltoniene” cu două rezultate din afara programei: condițiile euleriene pentru grafuri orientate și teorema lui Dirac. Într-un graf orientat, fiecare vârf $v$ are gradul exterior $d^{+}(v)$ (arcele care ies din $v$) și gradul interior $d^{-}(v)$ (arcele care intră în $v$). Un graf orientat are circuit eulerian (un drum închis care folosește fiecare arc o singură dată) dacă și numai dacă $d^{+}(v)=d^{-}(v)$ pentru fiecare vârf și toate vârfurile cu arce sunt legate între ele atunci când ignori orientarea. Teorema lui Dirac spune că un graf neorientat simplu cu $n\ge 3$ vârfuri în care fiecare vârf are gradul cel puțin $\frac{n}{2}$ are un ciclu hamiltonian. Condiția este suficientă, nu necesară.

Grafuri orientate echilibrate. Fiecare arc iese dintr-un vârf și intră în altul, deci ${\sum }_v{d}^{+}(v)={\sum }_v{d}^{-}(v)=m$, unde $m$ este numărul arcelor. Un drum eulerian trece prin fiecare vârf intermediar intrând și ieșind, adică folosind câte un arc de intrare și unul de ieșire de fiecare dată. Prin urmare, la un circuit eulerian (drum închis) fiecare vârf trebuie să aibă $d^{+}=d^{-}$. Invers, dacă toate vârfurile sunt echilibrate și graful este conex, circuitul există. Se pornește dintr-un vârf $s$ și se merge fără a repeta arce; deoarece fiecare vârf $v\ne s$ are la fiecare intrare câte o ieșire disponibilă, drumul se poate bloca numai în $s$, deci se închide. Dacă circuitul nu a epuizat arcele, conexitatea dă un vârf al lui cu arce neparcurse; arcele rămase sunt tot echilibrate, deci formează un nou circuit din acel vârf, pe care îl intercalezi în primul. Procedeul se repetă până se epuizează arcele.

Pentru un drum eulerian deschis de la $s$ la $t$ (cu $s\ne t$), condiția este: $d^{+}(s)-d^{-}(s)=1$, $d^{-}(t)-d^{+}(t)=1$ și $d^{+}(v)=d^{-}(v)$ pentru celelalte vârfuri, plus conexitatea. Dacă adaugi arcul $t\to s$, obții un graf echilibrat, deci problema se reduce la cazul precedent. Atenție: gradele pare ale grafului neorientat asociat nu sunt suficiente, orientarea contează.

Exemplu rezolvat. Graful orientat are arcele $1\to 2$, $2\to 3$, $3\to 1$, $1\to 4$, $4\to 1$. Are circuit eulerian?

1. Gradele exterioare sunt $d^{+}(1)=2$, $d^{+}(2)=1$, $d^{+}(3)=1$, $d^{+}(4)=1$; cele interioare sunt $d^{-}(1)=2$, $d^{-}(2)=1$, $d^{-}(3)=1$, $d^{-}(4)=1$.
2. Toate vârfurile sunt echilibrate și graful este conex, deci circuitul există.
3. Un circuit este $1\to 2\to 3\to 1\to 4\to 1$ și folosește cele $5$ arce.

Exemplu rezolvat. Graful are arcele $A\to B$, $B\to C$, $C\to A$, $A\to D$, $D\to B$. Stabilește dacă are drum eulerian.

1. $d^{+}(A)=2$ și $d^{-}(A)=1$, deci $d^{+}(A)-d^{-}(A)=1$; $d^{+}(B)=1$ și $d^{-}(B)=2$, deci $d^{-}(B)-d^{+}(B)=1$. Vârfurile $C$ și $D$ sunt echilibrate.
2. Drumul trebuie să înceapă în $A$ și să se termine în $B$. Nu există circuit eulerian.
3. Un astfel de drum este $A\to D\to B\to C\to A\to B$, care folosește cele $5$ arce o singură dată.

Exemplu rezolvat (orientarea contează). Graful neorientat cu muchiile $12$, $23$, $34$, $41$ are toate gradele $2$, deci are ciclu eulerian. Orientezi muchiile ca arcele $1\to 2$, $3\to 2$, $3\to 4$, $1\to 4$. Atunci $d^{+}(1)=2$ și $d^{-}(1)=0$, deci vârful $1$ nu este echilibrat și graful orientat nu are nici circuit, nici drum eulerian.

Teorema lui Dirac (1952). Fie $G$ un graf simplu cu $n\ge 3$ vârfuri și $\delta (G)\ge \frac{n}{2}$, unde $\delta (G)$ este cel mai mic grad. Atunci $G$ are un ciclu hamiltonian.

Demonstrație. (1) $G$ este conex: dacă $u,v$ nu sunt adiacente, vecinii lor se află printre celelalte $n-2$ vârfuri, iar $\mathrm{deg}u+\mathrm{deg}v\ge n>n-2$, deci au un vecin comun. (2) Fie $P=v_0{v}_1\dots v_k$ un lanț de lungime maximă. Toți vecinii lui $v_0$ și $v_k$ sunt pe $P$, altfel lanțul ar putea fi prelungit. (3) Mulțimile $A=\{i:v_0{v}_{i+1}\in E\}$ și $B=\{i:v_k{v}_i\in E\}$ sunt incluse în $\{0;1;\dots ;k-1\}$, au fiecare cel puțin $\frac{n}{2}$ elemente, iar $k\le n-1$. Cum $|A|+|B|\ge n>k$, există un indice $i\in A\cap B$. (4) Atunci $v_0{v}_{i+1}\dots v_k{v}_i{v}_{i-1}\dots v_0$ este un ciclu care trece prin toate vârfurile lui $P$. (5) Dacă ar exista un vârf în afara lui $P$, conexitatea ar da unul adiacent cu ciclul; plecând de la el și parcurgând ciclul s-ar obține un lanț mai lung decât $P$, contradicție. Deci ciclul este hamiltonian.

Cât de bună este condiția. Pragul $\frac{n}{2}$ nu poate fi coborât: graful bipartit complet $K_{k,k+1}$ are $n=2k+1$ vârfuri și $\delta =k=\frac{n-1}{2}$, dar nu are ciclu hamiltonian, deoarece un ciclu alternează între cele două mulțimi, care au dimensiuni diferite. În schimb, condiția nu este necesară: ciclul $C_6$ este hamiltonian cu toate gradele $2<3$. Teorema lui Ore (1960) o întărește: dacă $\mathrm{deg}u+\mathrm{deg}v\ge n$ pentru oricare două vârfuri neadiacente $u,v$, graful este hamiltonian. Dirac este cazul particular în care toate gradele sunt cel puțin $\frac{n}{2}$. Pentru grafuri orientate, teorema lui Ghouila-Houri (1960) spune că un graf orientat tare conex cu $n$ vârfuri în care $d^{+}(v)+d^{-}(v)\ge n$ pentru fiecare $v$ are circuit hamiltonian. Un graf neorientat, văzut ca graf orientat cu două arce (câte unul pe fiecare sens) pentru fiecare muchie, are $d^{+}+d^{-}=2\mathrm{deg}$, deci Dirac este cazul particular al acestei teoreme (un graf cu $\delta \ge \frac{n}{2}$ este conex).

Exemplu rezolvat. La o masă rotundă stau $8$ persoane și fiecare cunoaște cel puțin $4$ dintre celelalte. Se pot așeza astfel încât fiecare să aibă ca vecini două cunoscuți?

1. Persoanele sunt vârfuri, iar cunoștințele sunt muchii; $n=8$ și $\delta \ge 4=\frac{n}{2}$.
2. Conform teoremei lui Dirac, graful are un ciclu hamiltonian.
3. Persoanele se așază în ordinea ciclului, deci da, așezarea există.

Exemplu rezolvat. Graful $K_{3,3}$ ($n=6$, toate gradele $3=\frac{n}{2}$) este hamiltonian, deoarece verifică teorema lui Dirac; un ciclu este $a_1{b}_1{a}_2{b}_2{a}_3{b}_3{a}_1$. Roata cu $5$ vârfuri (un centru legat de un ciclu cu $4$ vârfuri) are gradele $4,3,3,3,3$ și $n=5$; cum $3\ge 2,5$, este hamiltoniană: centrul, apoi cele patru vârfuri ale ciclului în ordine, apoi înapoi la centru. Graful $K_{2,3}$ are $n=5$ și gradele $3,3,2,2,2$; teorema nu se aplică, fiindcă $2<2,5$, și într-adevăr nu are ciclu hamiltonian.

Exemplu rezolvat (Ore, dar nu Dirac). Graful cu vârfurile $A,B,C,D,E,F$ și muchiile $AC,AD,AE,AF,BC,BD,BE,BF,CD,CE,DE$ are gradele $4,4,4,4,4,2$. Cum $2<3$, teorema lui Dirac nu se aplică. Perechile neadiacente sunt $AB$ (suma $8$), $CF$, $DF$, $EF$ (suma $4+2=6\ge n=6$); deci teorema lui Ore se aplică și există ciclu hamiltonian: $A-C-D-E-B-F-A$.

Greșeli frecvente

• Greșit: dacă graful neorientat asociat are toate gradele pare, orice orientare a lui are circuit eulerian.
  Corect: în graful orientat trebuie $d^{+}(v)=d^{-}(v)$ în fiecare vârf; patrulaterul orientat $1\to 2$, $3\to 2$, $3\to 4$, $1\to 4$ are gradele pare, dar niciun circuit eulerian.
• Greșit: la un drum eulerian deschis într-un graf orientat toate vârfurile sunt echilibrate.
  Corect: vârful de început are $d^{+}-d^{-}=1$ și cel de sfârșit are $d^{-}-d^{+}=1$.
• Greșit: dacă un graf are un vârf de grad mai mic decât $\frac{n}{2}$, el nu este hamiltonian.
  Corect: condiția lui Dirac este doar suficientă; ciclul $C_6$ este hamiltonian deși toate gradele sunt $2<3$.
• Greșit: teorema lui Dirac se aplică la orice graf cu gradele cel puțin $\frac{n}{2}$, chiar și cu muchii multiple sau bucle.
  Corect: graful trebuie să fie simplu, cu $n\ge 3$ vârfuri.
• Greșit: teorema lui Dirac dă și un ciclu eulerian.
  Corect: $K_4$ are $\delta =3\ge 2$, deci este hamiltonian, dar toate gradele sunt impare și nu are ciclu eulerian.

Înainte și după