h2. Solutie

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:

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 (exista unele lucrari care definesc proprietatea Euleriana pe baza acestei teoreme, insa, indiferent de modalitatea de abordare aleasa de autori, rezultatul final cu privire la aceste structuri ramane acelasi). Pentru a construi un ciclu Eulerian 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.