h2. Solutie

Conform unei 'teoreme':http://www.math.dartmouth.edu/~euler/docs/originals/E053.pdf datorate lui Leonhard Euler, un multigraf este Eulerian daca si numai daca toate nodurile sale au grad par.

Conform unei 'teoreme':http://www.math.dartmouth.edu/~euler/docs/originals/E053.pdf datorate lui Leonhard Euler, un multigraf este Eulerian (admite un ciclu Eulerian) daca si numai daca este conex si toate nodurile sale au grad par. Pentru a construi un astfel de ciclu putem folosi urmatoarele variante:
 
* Generam toate ciclurile simple ale multigrafului (spre exemplu, folosind metoda 'backtracking':http://en.wikipedia.org/wiki/Backtracking) si verificam proprietatea Euleriana. O astfel de abordare are, insa, complexitate exponentiala in raport cu dimensiunea datelor de intrare si o consideram lipsita de utilitate practica.
* Folosind _algoritmul lui Fleury_, pornim de la un nod oarecare si, la fiecare pas, parcurgem o muchie a carei stergere din graf nu l-ar deconecta. Stergem muchia respectiva si, deplasandu-ne in celalalt capat al ei, continuam algoritmul in aceeasi maniera pana cand vom epuiza toate muchiile grafului. Ciclul obtinut este Eulerian.
Pentru implementarea algoritmului lui Fleury, putem face o parcurgere in adancime din nodul de start, etichetand muchiile dupa tipul lor (muchii _de arbore_ si muchii _de intoarcere_). La fiecare pas in construirea ciclului, vom alege intotdeauna muchiile de intoarcere inaintea muchiilor de arbore. Implementata cu grija, aceasta solutie are complexitate liniara.
 

[...]
== include(page="template/taskfooter" task_id="ciclueuler") ==