b'\n_START_ARTICLE_\nDrum eulerian\n_START_SECTION_\nDefini\xc8\x9bie\n_START_PARAGRAPH_\nUn\xc2\xa0drum eulerian, sau lan\xc8\x9b eulerian\xc2\xa0\xc3\xaentr-un graf neorientat este un drum care traverseaz\xc4\x83 fiecare muchie exact o dat\xc4\x83. Dac\xc4\x83 un astfel de drum exist\xc4\x83, graficul este numit traversabil\xc2\xa0sau semi-eulerian._NEWLINE_Un\xc2\xa0ciclu eulerian,\xc2\xa0sau \xe2\x80\x9ecircuit eulerian\xe2\x80\x9d\xc2\xa0\xc3\xaentr-un graf neorientat este un ciclu care parcurge fiecare muchie exact o dat\xc4\x83. Dac\xc4\x83 un astfel de ciclu exist\xc4\x83, graficul este numit eulerian\xc2\xa0sau unicursal.\xc2\xa0Termenul de \xe2\x80\x9egraf eulerian\xe2\x80\x9d este folosit uneori \xc8\x99i \xc3\xaentr-un sens mai slab, cu referire la un graf \xc3\xaen care fiecare nod are grad par. Pentru grafuri conexe\xc2\xa0finite, cele dou\xc4\x83 defini\xc8\x9bii sunt echivalente, \xc3\xaen timp ce un graf posibil neconex este eulerian \xc3\xaentr-un sens mai slab dac\xc4\x83 \xc8\x99i numai dac\xc4\x83 fiecare component\xc4\x83 conex\xc4\x83 are un ciclu eulerian._NEWLINE_Pentru grafurile orientate, no\xc8\x9biunea de \xe2\x80\x9edrum\xe2\x80\x9d este luat\xc4\x83 \xc3\xaen sensul de drum orientat\xc2\xa0\xc8\x99i cea de \xe2\x80\x9eciclu\xe2\x80\x9d, cu sensul de\xc2\xa0ciclu orientat._NEWLINE_Defini\xc8\x9bia \xc8\x99i propriet\xc4\x83\xc8\x9bile drumurilor, ciclurilor \xc8\x99i grafurilor \xc2\xa0euleriene sunt valabile \xc8\x99i pentru multigrafuri._NEWLINE_O orientare eulerian\xc4\x83 a unui graf neorientat G este atribuirea unei direc\xc8\x9bii pentru fiecare muchie din G astfel \xc3\xaenc\xc3\xa2t, la fiecare nod v, gradul interior al lui\xc2\xa0v s\xc4\x83 fie egal cu gradul exterior al lui\xc2\xa0v. O astfel de orientare exist\xc4\x83 pentru orice graf neorientat \xc3\xaen care fiecare nod are grad par, \xc8\x99i poate fi g\xc4\x83sit\xc4\x83 prin construirea unui ciclu eulerian \xc3\xaen fiecare component\xc4\x83 conex\xc4\x83 a lui\xc2\xa0G \xc8\x99i apoi orientarea muchiilor potrivit drumului. Fiecare orientare eulerian\xc4\x83 a unui graf conex este o\xc2\xa0orientare tare, adic\xc4\x83 o orientare care face graful orientat rezultat s\xc4\x83 fie\xc2\xa0tare conex.\n_START_SECTION_\nAlgoritmul lui Fleury\n_START_PARAGRAPH_\nAlgoritmul lui Fleury este un algoritm elegant, dar ineficient, care dateaz\xc4\x83 din 1883. Se d\xc4\x83 un graf despre care se \xc8\x99tie c\xc4\x83 are toate muchiile \xc3\xaen aceea\xc8\x99i component\xc4\x83 \xc8\x99i cel mult dou\xc4\x83 noduri de grad impar. Algoritmul porne\xc8\x99te de la un nod de grad impar, sau, dac\xc4\x83 graficul nu are niciunul, \xc3\xaencepe cu un nod arbitrar ales. La fiecare pas se alege urm\xc4\x83toarea muchie din drum ca fiind una a c\xc4\x83rei \xc8\x99tergere nu ar face graful s\xc4\x83 \xc3\xae\xc8\x99i piard\xc4\x83 conexitatea, iar dac\xc4\x83 nu exist\xc4\x83 nicio astfel de muchie, se alege muchia r\xc4\x83mas\xc4\x83 pentru nodul curent. Apoi se trece la cel\xc4\x83lalt cap\xc4\x83t al muchiei, iar muchia aleas\xc4\x83 anterior se \xc8\x99terge. La sf\xc3\xa2r\xc8\x99itul algoritmului nu mai exist\xc4\x83 muchii, \xc8\x99i secven\xc8\x9ba \xc3\xaen care au fost alese muchiile formeaz\xc4\x83 un ciclu eulerian unde graful nu are noduri de grad impar, sau un drum eulerian, dac\xc4\x83 exist\xc4\x83 exact dou\xc4\x83 noduri de grad impar._NEWLINE_\xc3\x8en timp ce\xc2\xa0parcurgerea grafului \xc3\xaen algoritmul lui Fleury\xc2\xa0este \xc3\xaen timp liniar \xc3\xaen raport cu num\xc4\x83rul de muchii, adic\xc4\x83 O(|E|), trebuie luat\xc4\x83 \xc3\xaen calcul \xc8\x99i complexitatea detect\xc4\x83rii de\xc2\xa0pun\xc8\x9bi. Dac\xc4\x83 se ruleaz\xc4\x83 din nou algoritmul \xc3\xaen timp liniar de detec\xc8\x9bie a pun\xc8\x9bilor al lui\xc2\xa0Tarjan\xc2\xa0dup\xc4\x83 \xc8\x99tergerea fiec\xc4\x83rei muchii, algoritmul lui Fleury va avea o complexitate \xc3\xaen timp O(|E|\xc2\xb2). Un algoritm dinamic de detec\xc8\x9bie a pun\xc8\x9bilor al lui\xc2\xa0Thorup (2000) permite ca acest timp s\xc4\x83 fie \xc3\xaembun\xc4\x83t\xc4\x83\xc8\x9bit p\xc3\xa2n\xc4\x83 la\xc2\xa0 dar chiar \xc8\x99i acesta este semnificativ mai lent dec\xc3\xa2t algoritmii alternativi.\n_START_SECTION_\nChestiuni de complexitate\n_START_PARAGRAPH_\nNum\xc4\x83rul ciclurilor euleriene \xc3\xaen digrafuri poate fi calculat folosind a\xc8\x99a-numita teorem\xc4\x83 BEST, dup\xc4\x83 numele lui\xc2\xa0de Bruijn, van Aardenne-Ehrenfest, Smith\xc2\xa0\xc8\x99i Tutte. Formula afirm\xc4\x83 c\xc4\x83 num\xc4\x83rul de cicluri euleriene \xc3\xaentr-un digraf este produsul dintre anumi\xc8\x9bi factoriali ai gradelor \xc8\x99i num\xc4\x83rul de arborescen\xc8\x9be\xc2\xa0cu r\xc4\x83d\xc4\x83cini. Aceasta din urm\xc4\x83 poate fi calculat ca\xc2\xa0determinant, prin\xc2\xa0teorema lui Kirchhoff\xc2\xa0(matrix-tree), de unde rezult\xc4\x83 un algoritm \xc3\xaen timp polinomial._NEWLINE_Teorema BEST a fost enun\xc8\x9bat\xc4\x83 pentru prima dat\xc4\x83 \xc3\xaen aceast\xc4\x83 form\xc4\x83 \xc3\xaentr-o \xe2\x80\x9enot\xc4\x83 de ad\xc4\x83ugire la demonstra\xc8\x9bie\xe2\x80\x9d \xc3\xaen articolul lui Aardenne-Ehrenfest \xc8\x99i de Bruijn (1951). Demonstra\xc8\x9bia ini\xc8\x9bial\xc4\x83 era\xc2\xa0bijectiv\xc4\x83\xc2\xa0\xc8\x99i generaliza\xc2\xa0\xc8\x99irurile de Bruijn. Este o varia\xc8\x9bie a unui rezultat al lui Smith \xc8\x99i Tutte (1941)._NEWLINE_Num\xc4\x83rarea ciclurilor euleriene pe grafuri\xc2\xa0neorientate\xc2\xa0este mult mai dificil\xc4\x83. Aceast\xc4\x83 problem\xc4\x83 este cunoscut\xc4\x83 a fi #P-complet\xc4\x83. \xc3\x8entr-o direc\xc8\x9bie pozitiv\xc4\x83, se consider\xc4\x83 c\xc4\x83 o abordare \xc2\xa0Monte Carlo cu lan\xc8\x9buri Markov, prin intermediul transform\xc4\x83rii\xc2\xa0Kotzig\xc2\xa0(introdus\xc4\x83 de\xc2\xa0Anton Kotzig \xc3\xaen 1968) ofer\xc4\x83 o aproximare bun\xc4\x83 pentru num\xc4\x83rul de cicluri euleriene \xc3\xaentr-un graf, de\xc8\x99i \xc3\xaenc\xc4\x83 nu exist\xc4\x83 nicio demonstra\xc8\x9bie a acestui fapt (chiar \xc8\x99i pentru grafurile cu grad m\xc4\x83rginit).\n_START_SECTION_\nAplica\xc8\x9bii\n_START_PARAGRAPH_\nDrumurile euleriene sunt utilizate \xc3\xaen bioinformatic\xc4\x83 pentru a reconstrui secven\xc8\x9be de ADN\xc2\xa0din fragmente. Ele sunt utilizate \xc8\x99i \xc3\xaen proiectarea circuitelor\xc2\xa0CMOS\xc2\xa0pentru a g\xc4\x83si ordon\xc4\x83ri optime ale\xc2\xa0por\xc8\x9bilor logice. Exist\xc4\x83 unii algoritmi pentru prelucrarea arborilor care se bazeaz\xc4\x83 pe un drum eulerian al arborelui (unde fiecare muchie este tratat\xc4\x83 ca o pereche de arce).'