Diferente pentru problema/ciclueuler intre reviziile #8 si #15

Nu exista diferente intre titluri.

Diferente intre continut:

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.
      adauga v la ciclu
==
Aceasta abordare recursiva este foarte simpla si usor de implementat, cu toate ca, pentru grafuri de dimensiuni mari, va conduce la probleme de stack overflow. Din aceata cauza, recomandam implementarea iterativa a algoritmului, folosind o stiva gestionata manual pentru a retine nodurile din ciclul format. O solutie ce urmareste aceasta idee se afla 'aici':http://infoarena.ro/job_detail/237577?action=view-source.
Aceasta abordare recursiva este foarte simpla si usor de implementat, cu toate ca, pentru grafuri de dimensiuni mari, va conduce la probleme de stack overflow. Din aceata cauza, recomandam implementarea iterativa a algoritmului, folosind o stiva gestionata manual pentru a retine nodurile din ciclul format. O solutie ce urmareste aceasta idee se afla 'aici':job_detail/1789307?action=view-source.
Exista mai multe extensii ale ultimei solutii prezentate. Ideea algoritmului poate fi aplicata cu succes si in cazul gasirii unui lant Eulerian. In cazul acesta, multigraful trebuie sa contine _exact_ doua noduri de grad impar, care vor fi nodurile de inceput si sfarsit ale lantului. Pentru determinarea lantului, vom adaugata fictiv o muchie intre aceste doua noduri, dupa care vom aplica algoritmul de determinare a unui ciclu Eulerian. Eventual, acest ciclu determinat va fi 'rupt' in locul in care apare muchia adaugata si tiparit in ordinea corecta.
Dupa aceeasi idee putem construi algoritmi pentru a gasi drumuri si circuite Euleriene in grafuri orientate. Aici, criteriul de existenta pentru un circuit Eulerian este ca fiecare nod sa aiba gradul interior (numarul arcelor care 'intra' in acel nod) egal cu cel exterior (numarul arcelor care 'ies' din nod), iar pentru drum Eulerian sa existe _exact_ doua noduri, unul cu gradul exterior cu 1 mai mare decat cel interior, iar celalalt cu gradul interior cu 1 mai mare decat cel exterior; primul nod va actiona ca punct de plecare, iar celalalt ca punct de sosire pentru drum.
* 'Domino':problema/domino
* 'Johnie':problema/johnie
* 'Tester':problema/tester
* "Winning Checkers":http://ace.delos.com/ioiupload?d=gold&a=mQlEnO2VpIw&lang=en
* "Bridges Painting":http://acm.sgu.ru/problem.php?contest=0&problem=121
* "Strange Graph":http://acm.sgu.ru/problem.php?contest=0&problem=156
* "Winning Checkers":http://ace.delos.com/ioiupload?d=gold&a=mQlEnO2VpIw&lang=en
* "Ancient Decoration":http://acm.sgu.ru/problem.php?contest=0&problem=286
* "Depot Rearrangement":http://ceoi.inf.elte.hu/ceoi2005/download/tasks/day1/depot.pdf, _CEOI 2005_
== include(page="template/taskfooter" task_id="ciclueuler") ==
 
== include(page="template/taskfooter" task_id="ciclueuler") ==

Nu exista diferente intre securitate.

Diferente intre topic forum:

 
3532