miniatura|165x165px|Podurile din Königsberg multigraf. Acest multigraf nu este eulerian, deci nu există nicio soluție. miniatura|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. Î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: 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 .N. L. Biggs, E. K. Lloyd and R. J. Wilson, Graph Theory 1736–1936, Clarendon Press, Oxford, 1976, 8–9, .
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,Unii rezervă termenii de drum și ciclu pentru drumurile și ciclurile care nu se autointersectează, adică drumuri și cicluri elementare. Pentru cele care se autointersectează (sau se pot autointersecta) se face de obicei precizarea că este vorba de drumuri sau cicluri neelementare. 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.Jun-ichi Yamaguchi, Introduction of Graph Theory .
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.V. K. Balakrishnan, . 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 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 , adică o orientare care face graful orientat rezultat să fie .
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|2). Un algoritm dinamic de detecție a punților al lui permite ca acest timp să fie îmbunătățit până la 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, .
Numărarea ciclurilor euleriene
Chestiuni de complexitate Numărul ciclurilor euleriene în digrafuri poate fi calculat folosind așa-numita , după numele lui , van Aardenne-Ehrenfest, și . Formula afirmă că numărul de cicluri euleriene într-un digraf este produsul dintre anumiți factoriali ai gradelor și numărul de cu rădăcini. Aceasta din urmă poate fi calculat ca determinant, prin (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 și generaliza . 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 .Brightwell și , "Note on Counting Eulerian Circuits", 2004. Într-o direcție pozitivă, se consideră că o abordare , prin intermediul transformării Kotzig (introdusă de î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 pentru numărul de cicluri euleriene în grafuri complete fost determinată de și Robinson (1995): and Robert W. Robinson, Asymptotic enumeration of eulerian circuits in the complete graph, , 10 (1995), no. 4, 367–377.
O formulă similară a fost obținută mai târziu de M. I. Isaev (2009) pentru :
Aplicații Drumurile euleriene sunt utilizate în bioinformatică pentru a reconstrui 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 miniatura|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, ilustrat, conex și cu toate nodurile de grad patru, nu are șiruri euleriene. Grafurile infinite care conțin șiruri euleriene au fost caracterizate de . 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 . Tradus ca . Euler, L., "Solutio problematis ad geometriam situs pertinentis", Comment. Academiae Sci. I. Petropolitanae 8 (1736), 128–140.
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.
W. T. Tutte și C. A. B. Smith (1941) "On Unicursal Paths in a Network of Degree 4", American Mathematical Monthly 48: 233–237.
Note
Legături externe
Categorie:Teoria grafurilor