Drum eulerian

În teoria grafurilor, un drum eulerian (sau lanț eulerian) este un drum într-un graf finit, care vizitează fiecare muchie exact o dată. În mod similar, un „ciclu eulerian” sau „circuit  eulerian” este un drum eulerian traseu care începe și se termină cu același nod. Ele au fost discutate în premieră de către Leonhard Euler în timp ce rezolva celebra problemă a celor șapte poduri din Königsberg în 1736. Problema poate fi formulată matematic astfel:

Podurile din Königsberg multigraf. Acest multigraf nu este eulerian, deci nu există nicio soluție.

Fiecare nod din acest graf are un grad par. Prin urmare, aceasta este un graf eulerian. Urmând muchiile în ordine alfabetică, se poate găsi un ciclu eulerian.

Dat fiind graful din imagine, se poate construi un drum (sau un ciclu, adică un drum care începe și se încheie în același nod) care vizitează fiecare muchie exact o dată?

Euler a demonstrat că o condiție necesară pentru existența ciclurilor euleriene este ca toate nodurile din graf să aibă grad par, și a afirmat fără a demonstra, că grafurile conexe care au toate nodurile pare au un ciclu eulerian. Prima demonstrație completă a acestei din urmă afirmații a fost publicată postum în anul 1873 de către Carl Hierholzer^⁠(d).

Termenul de graf eulerian are două sensuri comune în teoria grafurilor. Un sens este acela de graf care are un „ciclu eulerian”, iar celălalt este acela de graf care are toate nodurile de grad par. Aceste definiții coincid pentru grafurile conexe.

Pentru existența drumurilor euleriene este necesar ca zero sau două noduri să aibă grad impar; acest lucru înseamnă că graful podurilor din Königsberg nu este eulerian. Dacă nu există noduri de grad impar, atunci toate drumurile euleriene sunt cicluri. Dacă există exact două noduri de grad impar, atunci toate drumurile euleriene încep într-unul dintre ele și se termină în celălalt. Un graf care are un drum eulerian, dar nu și un „ciclu eulerian” se numește semi-eulerian.

Definiție

Un drum eulerian, sau lanț eulerian într-un graf neorientat este un drum care traversează fiecare muchie exact o dată. Dacă un astfel de drum există, graficul este numit traversabil sau semi-eulerian.

Un ciclu eulerian, sau „circuit eulerian” într-un graf neorientat este un ciclu care parcurge fiecare muchie exact o dată. Dacă un astfel de ciclu există, graficul este numit eulerian sau unicursal. Termenul de „graf eulerian” este folosit uneori și într-un sens mai slab, cu referire la un graf în care fiecare nod are grad par. Pentru grafuri conexe^⁠(d) finite, cele două definiții sunt echivalente, în timp ce un graf posibil neconex este eulerian într-un sens mai slab dacă și numai dacă fiecare componentă conexă are un ciclu eulerian.

Pentru grafurile orientate, noțiunea de „drum” este luată în sensul de drum orientat și cea de „ciclu”, cu sensul de ciclu orientat.

Definiția și proprietățile drumurilor, ciclurilor și grafurilor  euleriene sunt valabile și pentru multigrafuri.

O orientare euleriană a unui graf neorientat G este atribuirea unei direcții pentru fiecare muchie din G astfel încât, la fiecare nod v, gradul interior al lui v să fie egal cu gradul exterior al lui v. O astfel de orientare există pentru orice graf neorientat în care fiecare nod are grad par, și poate fi găsită prin construirea unui ciclu eulerian în fiecare componentă conexă a lui G și apoi orientarea muchiilor potrivit drumului. Fiecare orientare euleriană a unui graf conex este o orientare tare^⁠(d), adică o orientare care face graful orientat rezultat să fie tare conex^⁠(d).

Proprietăți

• Un graf neorientat are un ciclu eulerian dacă și numai dacă fiecare nod are grad par, și toate nodurile cu grad nenul aparțin unei singure componente conexe.
• Un graf neorientat poate fi descompus în cicluri cu muchii disjuncte, dacă și numai dacă toate nodurile sale au grad par. Deci, un graf are un ciclu eulerian dacă și numai dacă el poate fi descompus în cicluri cu muchii disjuncte și nodurile sale de grad nenul aparțin unei singure componente conexe.
• Un graf neorientat are un drum eulerian dacă și numai dacă exact zero sau două noduri au grad impar, și toate nodurile cu grad nenul aparțin unei singure componente conexe.
• Un graf orientat are un ciclu eulerian dacă și numai dacă fiecare nod are gradul interior și gradul exterior egale, și toate nodurile cu grad nenul aparțin unei singure componente tare conexe. Echivalent, un graf orientat are un ciclu eulerian dacă și numai dacă el poate fi descompus în cicluri orientate cu muchii disjuncte și toate nodurile cu grad nenul aparțin unei singure componente tare conexe.
• Un graf orientat are un drum eulerian dacă și numai dacă cel mult un nod are (gradul exterior) − (gradul interior) = 1, cel mult un nod are (gradul interior) − (gradul exterior) = 1, iar celelalte noduri au toate gradul exterior și gradul interior egale, iar toate nodurile cu grad nenul aparțin unei singure componente conexe a grafului neorientat de bază.

Construirea de drumuri și cicluri euleriene

Algoritmul lui Fleury

Algoritmul lui Fleury este un algoritm elegant, dar ineficient, care datează din 1883. Se dă un graf despre care se știe că are toate muchiile în aceeași componentă și cel mult două noduri de grad impar. Algoritmul pornește de la un nod de grad impar, sau, dacă graficul nu are niciunul, începe cu un nod arbitrar ales. La fiecare pas se alege următoarea muchie din drum ca fiind una a cărei ștergere nu ar face graful să își piardă conexitatea, iar dacă nu există nicio astfel de muchie, se alege muchia rămasă pentru nodul curent. Apoi se trece la celălalt capăt al muchiei, iar muchia aleasă anterior se șterge. La sfârșitul algoritmului nu mai există muchii, și secvența în care au fost alese muchiile formează un ciclu eulerian unde graful nu are noduri de grad impar, sau un drum eulerian, dacă există exact două noduri de grad impar.

În timp ce parcurgerea grafului în algoritmul lui Fleury este în timp liniar în raport cu numărul de muchii, adică O(|E|), trebuie luată în calcul și complexitatea detectării de punți. Dacă se rulează din nou algoritmul în timp liniar de detecție a punților al lui Tarjan după ștergerea fiecărei muchii, algoritmul lui Fleury va avea o complexitate în timp O(|E|²). Un algoritm dinamic de detecție a punților al lui Thorup (2000) permite ca acest timp să fie îmbunătățit până la $O(|E|(\log |E|)^{3}\log \log |E|)$ dar chiar și acesta este semnificativ mai lent decât algoritmii alternativi.

Algoritmul lui Hierholzer

Articolul lui Hierholzer din 1873 oferă o metodă diferită pentru a găsi cicluri euleriene, mult mai eficientă decât algoritmul lui Fleury:

• Se alege orice nod v, și se urmează drumul muchiilor de la acel nod până la revenirea la v. Nu se poate ajunge la blocaj la orice alt nod decât v, deoarece faptul că toate nodurile au grad par asigură că, atunci când traseul intră în alt nod w trebuie să existe o muchie neutilizată care pleacă din w. Drumul astfel format este închis, dar se poate să nu acopere toate nodurile și muchiile grafului inițial.
• Dacă există un nod u, care aparține drumului actual, dar care are muchii adiacente care nu fac parte din drum, se începe un alt traseu de la u și se urmează muchiile neutilizate până la revenirea la u, și drumul astfel format se atașează la drumul anterior.

Folosind structuri de date cum ar fi listele dublu înlănțuite pentru a reține mulțimea muchiilor neutilizate incidente la fiecare nod, pentru a reține lista nodurilor de pe actualul drum cu muchii neutilizate, și pentru a reține drumul în sine, operațiunile individuale ale algoritmului (găsirea de muchii neutilizate care ies din fiecare nod, găsirea unui nou nod inițial pentru un drum, și conectarea a două drumuri care au un nod în comun) poate fi efectuată fiecare în timp constant, deci în general algoritmul are timp liniar, $O(|E|)$.

Numărarea ciclurilor euleriene

Chestiuni de complexitate

Numărul ciclurilor euleriene în digrafuri poate fi calculat folosind așa-numita teoremă BEST^⁠(d), după numele lui de Bruijn^⁠(d), van Aardenne-Ehrenfest, Smith^⁠(d) și Tutte^⁠(d). Formula afirmă că numărul de cicluri euleriene într-un digraf este produsul dintre anumiți factoriali ai gradelor și numărul de arborescențe^⁠(d) cu rădăcini. Aceasta din urmă poate fi calculat ca determinant, prin teorema lui Kirchhoff^⁠(d) (matrix-tree), de unde rezultă un algoritm în timp polinomial.

Teorema BEST a fost enunțată pentru prima dată în această formă într-o „notă de adăugire la demonstrație” în articolul lui Aardenne-Ehrenfest și de Bruijn (1951). Demonstrația inițială era bijectivă^⁠(d) și generaliza șirurile de Bruijn^⁠(d). Este o variație a unui rezultat al lui Smith și Tutte (1941).

Numărarea ciclurilor euleriene pe grafuri neorientate este mult mai dificilă. Această problemă este cunoscută a fi #P-completă^⁠(d). Într-o direcție pozitivă, se consideră că o abordare  Monte Carlo cu lanțuri Markov^⁠(d), prin intermediul transformării Kotzig (introdusă de Anton Kotzig^⁠(d) în 1968) oferă o aproximare bună pentru numărul de cicluri euleriene într-un graf, deși încă nu există nicio demonstrație a acestui fapt (chiar și pentru grafurile cu grad mărginit).

Cazuri speciale

Formula asimptotică^⁠(d) pentru numărul de cicluri euleriene în grafuri complete fost determinată de McKay^⁠(d) și Robinson (1995):

$ec(K_{n})=2^{(n+1)/2}\pi ^{1/2}e^{-n^{2}/2+11/12}n^{(n-2)(n+1)/2}{\bigl (}1+O(n^{-1/2+\epsilon }){\bigr )}.$

O formulă similară a fost obținută mai târziu de M. I. Isaev (2009) pentru grafurile complete bipartite^⁠(d):

$ec(K_{n,n})=(n/2-1)!^{2n}2^{n^{2}-n+1/2}\pi ^{-n+1/2}n^{n-1}{\bigl (}1+O(n^{-1/2+\epsilon }){\bigr )}.$

Aplicații

Drumurile euleriene sunt utilizate în bioinformatică pentru a reconstrui secvențe de ADN^⁠(d) din fragmente. Ele sunt utilizate și în proiectarea circuitelor CMOS pentru a găsi ordonări optime ale porților logice. Există unii algoritmi pentru prelucrarea arborilor care se bazează pe un drum eulerian al arborelui (unde fiecare muchie este tratată ca o pereche de arce).

În grafuri infinite

Un graf infinit cu toate gradele egale cu patru, dar fără șiruri euleriene

Într-un graf infinit, conceptul corespunzător celui de la o Euleriene traseu sau ciclu eulerian este cel de șir eulerian, un drum dublu-infinit care acoperă toate muchiile din graf. Condiția ca graful să fie conex și cu toate nodurile de grad par nu este suficientă pentru existența unui astfel de drum; de exemplu, graful infinit Cayley^⁠(d) ilustrat, conex și cu toate nodurile de grad patru, nu are șiruri euleriene. Grafurile infinite care conțin șiruri euleriene au fost caracterizate de Erdős, Grünwald & Weiszfeld (1936). Pentru ca un graf sau multigraf G să aibă un șir eulerian, este necesar și suficient ca toate condițiile următoare să fie îndeplinite:

• G este conex.
• G are mulțimi numărabile de noduri și muchii.
• G nu are noduri de grad impar finit.
• Eliminarea oricărui subgraf finit S din G lasă cel mult două componente conexe infinite în graful rămas, și dacă S are toate nodurile de grad par, atunci înlăturarea lui S lasă cel mult o componentă conexă infinită.

Bibliografie

• Erdős, Pál; Grünwald, Tibor; Weiszfeld, Endre (1936), „Végtelen gráfok Euler vonalairól” [Despre linii euleriene în grafuri infinite] (PDF), Mat. Fix. Lapok (în maghiară), 43: 129–140 . Tradus ca Erdős, P.; Grünwald, T.; Vázsonyi, E. (1938), „Über Euler-Linien unendlicher Graphen” [Despre linii euleriene în grafuri infinite] (PDF), J. Math. Phys. (în germană), 17: 59–75 .
• Euler, L., "Solutio problematis ad geometriam situs pertinentis", Comment. Academiae Sci. I. Petropolitanae 8 (1736), 128–140.
• Hierholzer, Carl (1873), „Ueber die Möglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu umfahren”, Mathematische Annalen^⁠(d) (în germană), 6 (1): 30–32, doi:10.1007/BF01442866 
• Lucas, E., Récréations Mathématiques IV, Paris, 1921.
• Fleury, "Deux problemes de geometrie de situation", Journal de mathematiques elementaires (1883), 257–261.
• T. van Aardenne-Ehrenfest și N. G. de Bruijn (1951) "Circuits and trees in oriented linear graphs", Simon Stevin 28: 203–217.
• Thorup, Mikkel (2000), „Near-optimal fullydynamic graph connectivity”, Proc. 32nd ACM Symposium on Theory of Computing^⁠(d), pp. 343–350, doi:10.1145/335305.335345 
• W. T. Tutte și C. A. B. Smith (1941) "On Unicursal Paths in a Network of Degree 4", American Mathematical Monthly 48: 233–237.