Pagini recente » Diferente pentru problema/paritate intre reviziile 26 si 27 | Diferente pentru 2-sat intre reviziile 4 si 90 | Monitorul de evaluare | Diferente pentru problema/shoturi intre reviziile 12 si 14 | Diferente pentru problema/ciclueuler intre reviziile 6 si 7
Nu exista diferente intre titluri.
Diferente intre continut:
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.
h2. Aplicatii
Incepand cu 'Problema podurilor din Konigsberg':http://en.wikipedia.org/wiki/Seven_Bridges_of_Konigsberg, studiul lanturilor Euleriene in grafuri si-a gasit numeroase aplicatii. In matematica distractiva apar figuri asemanatoare celor de mai jos, punandu-se problema desenarii lor fara a ridica creionul de pe hartie si fara a desena de mai multe ori aceeasi linie.
p=. !problema/ciclueuler?euler01.png!
Raspunsul unor astfel de probleme se obtine simplu prin transformarea retelei respective intr-un graf si testarea proprietatii Euleriene.
De asemenea, o alta aplicatie interesanta este studiul drumurilor si circuitelor Euleriene in 'grafuri de Bruijn':http://en.wikipedia.org/wiki/De_Bruijn_graph. O problema care se poate rezolva cu ajutorul acestor notiuni este 'Biti':problema/biti.
Alte probleme care folosesc in rezolvare ideea drumurilor Euleriene sunt:
== include(page="template/taskfooter" task_id="ciclueuler") ==
Nu exista diferente intre securitate.
Topicul de forum nu a fost schimbat.