Teme Algorimtica Grafurilor

download Teme Algorimtica  Grafurilor

If you can't read please download the document

  • date post

    08-Aug-2015
  • Category

    Documents

  • view

    269
  • download

    17

Embed Size (px)

description

grafuri

Transcript of Teme Algorimtica Grafurilor

1 TEMA NR. 1 4 martie 2003 1. Un graf se numete rar dac numrul su de muchii m este mai mic dect nnlog2, unde n reprezint numruldevrfuri.OjustificareesteaceeacmatriceadeadiacenAagrafului,careocupn2 locaiidememorie,poatefintotdeaunareprezentatfolosindO(nnlog2)locaiidememorie,astfel nctrspunsullaontrebareA(i,j)=1?ssefacnO(1).Descrieioastfeldeschemde reprezentare. Soluie: AvndnvederefaptulcnmatriceadeadiacenAaunuigraffiecareelementA(i, j) poate lua doar valorile 0 i 1, este suficient un singur bit pentru a memora aceste informaii.Pentrureducereaspaiuluiocupatdematriceadeadiacensepropuneurmtoareaschemde reprezentare: -matricea A este mprit n matrice ptratice de dimensiune (n log X (n log ; -numrul acestor matrice este (nnlog2; -se creeaz o nou matrice ptratic A de dimensiune ((nnnnlog logX ; -fiecare element al matricei A este o codificare a unei matrice de dimensiune (n log X (n logdup cum urmeaz: oo astfel de matrice are log n elemente ce pot lua doar valorile 0 i 1; odac matricea este parcurs pe linii se obine o segven de log n biti; ofiecare astfel de segven poate fi reprezentarea binar a unui numr ntre 0 i 2log n = n; ofieBomatricededimensiune (n log X (n log obinutprinpartiionarealuiAca mai sus, cu B(i,j) = A(k1(n log +i, k2(n log +j) i fie s secventa de biti obtinut prin parcurgereamatriceiBpelinii;atunciA(k1,k2)=m,undemestenumrulacrui reprezentare binar este s; oavnd n vedere c reprezentarea binar a numerelor naturale este unic, dac B1 B2, atunci s1 s2 i m1 m2; -obinerea rspunsului la ntrebarea: A(i, j) = 1 ?: valoarea lui A(i,j) se poate obine din matricea A astfel: 2 odin modul de partiionare a lui A se constat c elementul A(i,j) se obine din procesarea elementului A( (nilog, (njlog); oreprezentareabinaraelementuluiA( (nilog, (njlog)estesuccesiunealiniilor matriciiB,undeB(p,q)=A(i,j),cup = i mod (n log i q = j mod (n log , adic bitul de pe poziia (i mod (n log )* (n log +jmod (n log dinreprezentareabinaraluiA( (nilog, (njlog),numrnd de la stnga la dreapta; Observaie:Avnd n vedere faptul c numnul n nu se mparte ntotdeauna exact la (n log , este posibilcamatriceledelaextremitiledreapta,respectivjosalematriceiAmatricele obinute prin patriionare s nu aib dimensiunile cerute, ci dimensiuni mai mici.Deexemplu,omatricededimendiune5X5trebuiepatriionatnmatricide dimensiune2X2.Coloanaacinceavafidecimpritn3matrice,doude dimensiune 2 X 1 iuna de dimensiune 1 X 1. Aceste matrice vor fi extinse la matrice de dimensiune 2 X 2 astfel: Fie B1 o matrice de dimensiune 2 X 1 (de exemplu, B1(0,0) = A(0,4) i B1(1,0) = A(1,4)i B2 matricea de dimensiune 2 X 2 la care va fi extins B1; atunci B2(0,0) = B1(0,0), B2(1,0) = B1(1,0), iar B2(0,1) iB2(1,1) pot avea oricare din valorile 0 i 1. B2(0,0) B2(0,1), B2(1,0), B2(1,1) este reprezentarea binar a valorii elementului A(2,0).Amvzutmaisuscumsefaceextragereadintr-unelementalluiAabituluicarereprezintvaloarealuiA(i,j).Deacolonedmseamacnusevancercaniciodat extragereaunuibitcarenucorespundeunuielementdinmatriceaA,decivalorile elementelor adugate la extinderea matricelor B nu au importan. -complexiti: omatricea A are (nnlog2elemente, deci complexitatea spaiu a reprezentrii sale este O(nnlog2);ooperaiiledecalculalelementuluicorespunztorluiA(i,j)dinAsefacprinefectuarea unor mpriri sau calcule de resturi, operaii ce necesit timp constant O(1); oaccesul la elementele matricei A se face n timp constant O(1); oextragerea unui bit din reprezentarea binar a unui element din A se poate face n timp constant O(1) prin operaii logice pe bii (utilizndu-se eventual o masc); 3 nconcluzie,rspunsullantrebarea:A(i,j)=1?sepoateobinentimpconstant (independent de n) O(1). 2. Diametrulunuigrafestelungimeamaximaunuidrumdelungimeminimntredouvrfuriale grafului. Dou vrfuri care sunt extremitile unui drum minim de lungime maxim n graf se numesc diametral opuse. Demonstrai c urmtorul algoritm determin o pereche de vrfuri diametral opuse ntr-un arbore T : -Dintr-un vrf oarecare se execut o parcurgere BFS a arborelui; fie u ultimul vrf vizitat; -Din vrful u se executa o parcurgere BFS a arborelui; fie v ultimul vrf vizitat; -Return u, v. Rmne valabil algoritmul pentru un graf conex arecare? Soluie1: AtuncicndseaplicBFSunuigrafseobineunarborenumitarboredelime (carenuparcurgentotdeaunatoatemuchiilegrafuluiiniial).Prinnoiuneadearborede lime ntelegem un arbore cu rdcina n nodul de start al BFS-ului i care are proprietatea c drumuldelaoricarenodlardcinestecelmaimicdrumdintreceledounoduri,ngraful iniial.Aceastanseamncalgoritmuldescopernoduriledeladistanakfaderdcin nainte s descopere nodurile de la distana k+1. Ultimul nod descoperit de BFS este cel mai din dreapta nod de pe frontier. n cazul n care graful iniial este arbore, arborele lime va conine toate muchiile sale ( drumul ntre dou noduri din graful iniial este unic deci, automat, minim). Primul BFS din algoritmul de mai sus, aplicat pentru un nod de start oarecare din arborele iniial, se poziioneaz pe cel mai din dreapta nod de pe frontier, notat cu u, iar ultimul nod vizitat de al doilea BFS este cel mai deprtat nod de u, i anumev. Trebuie s demonstrmc distana de la u la v este de fapt diametrul arborelui iniial, i anume cel mai lung drum dintre dou noduri ale arborelui. Pentrusimplificarevomconsideradrumuldelaulavcafiinddelungime2L.(cazulcndacest drum are lungime impar se trateaz similar). Privim arborele sub alt form : aezm drumul de la u la v n linie dreapt, ca o ax, iar ceilali subarbori i agm de nodurile de pe ax, n semiplanul superior determinat de aceasta sau n cel inferior. Considerm w ca fiind un nod aflat la mijlocul drumului dintre u i v, la distana l de cele 2 noduri.

1 BIBLIOGRAFIE: csce.unl.edu/~vimod/CSCE423/4Sol.pdf 4 Notm cu s nodul ales aleator ca nod de start pentru primul BFS. Observm c s trebuie s fie n dreapta nodului w, deoarece, dac s ar fi n stnga, am obine drumul de la s la v mai mare dect drumul de la s la u, ceea ce contrazice ipoteza, ntrucat u era cel mai neprtat nod de s. FieTunsubarborependantdintr-unnodxaflatpedrumuldelaulav,lastngaluiw.Pentru fiecare astfel de subarbore obinem urmatoarea relaie:adncime(T) s d(u,x) Dac aceast relaie nu ar fi adevarat, am obine urmtorul rezultat :adncime (T) + d(x,s) > d(u,x) + d(x,s).Deci ar exista un nod z de pe T astfel nctd(z,x) + d(x,s) > d(u,s) => d(z,s) > d(u,s) ceea ce contrazice ipoteza c u este cel mai departat nod de s, aa cum am obinut din primul BFS. Fie T un subarbore pendant dintr-un nod y aflat pe drumul de la u la v, la dreapta lui w. Pentru fiecare astfel de subarbore obinem urmtoarea relaie: adncime (T) s d(y,v). Dac aceast relaie nu ar fi adevrat, am obine urmtorul rezultat :adncime (T) + d(y,u) > d(u,y) + d(y,v). Deci ar exista z, un nod de pe T astfel nct d(u,z) > d(u,v) ceea ce contrazice ipoteza c v este cel mai deprtat nod de u, aa cum am obinut din al doilea BFS, aplicat pentru nodul u . Deci pentru fiecare x si y alei ca mai sus, i T respectiv T, obinem relaiile: adncime (T) s d(u,x) i adncime (T) s d(y,v) din care avem adncime (T) + d(x,w) s d(u,x) + d(x, w) = d(u,w) =L si adncime (T) + d(w,y) s d(w,y) + d(y,v) = d(w,v ) = L. DecipentruoricarenodzdepesubarboreleTobinemd(z,w)sLipentruoricarenodzdepe subarborele T obinem d(z,w) s L. Decid(z,w) + d(w, z) s 2L, de unde d(z,z) s 2L oricare ar fi z si z dou noduri aflate pe doi astfel de subarbori ca cei alei mai sus.5 Dacamalege2subarboripendantideaceeaipartealuiwamobtineacelairezultat.De asemenea este evident c orice dou noduri aflate pe drumul de la u la v au distanta ntre ele mai mic dect d(u,v). n concluzie, oricum am alege dou noduri din arbore, drumul dintre ele nu poate fi mai mic dect drumul de la u la v. Deci distana de la u la v este diametrul arborelui initial (faptul c am impus lungimea drumuluidelaulavcafiindegalacu2Lnurestrangerezultatulobinut,ntruct,dacacestdrumar avealungimeadeforma2L-1,amalegewladistantaLdeusiL-1devsauinversiamurmaaceiaipaicapentrusituaia anterioar ).q.e.d. ncazulncaregrafuliniialesteungrafconexoarecare,algoritmuldemaisusnumaid ntotdeauna rspunsul corect, ntruct ntre oricare dou noduri putem avea mai mult de un drum ( deci putem avea cicluri ) iar arborele lime obinut va pstra numai primele drumuri gsite de la rdcina sa la celelalte noduri. Pentru oricare dou noduri se va reine numai un drum i acesta difer pentru fiecare arbore laime obtinut (n funcie de nodul de plecare).Vom da un exemplu n care, pentru un graf oarecare, n funcie de nodul de pornire i de ordinea de alegere a nodurilor adiacente, obinem drumuri distincte n arbori de lime diferii, ntre dou noduri, iar dac vom calcula diametrul dup algoritmul de mai sus vom obine valori diferite.

6 3. FieTunarborebinarcurdcin.UnalgoritmsimpludedesenarealuiTpoatefidescrisrecursiv dup cum urmeaz. -Folosim ca suport o grila (limiatura unui caiet de matematic); vrfurile se plaseaza in punctele de intersecie ale grilei. -Desenm subarborele stng.-Desenm subarborele drept. -Plasm cele dou desene unul lng altul la distana pe orizontala doi i cu rdcinile la aceeasi nalime. -Plasmrdcinacuunnivelmaisuslajumtateadistaneipeorizontaldintreceidoi copii. -Dac avem doar un copil plasm rdcina cu un nivel mai sus la distana 1 fa de copil. (la stnga sau la dreapta dup cum este acesta). DescrieicumsepotasociapentrufiecarenodvalarboreluiT(folosindalgoritmuldemaisus) coordonatele (x(v), y(v)) reprezentnd punctul de pe gril unde va fi desenat. Soluie: Fie Tun arbore cu n noduri numerotate (pentru simplificare)de la 1 la n. Pentru fiecare nod din acestaarborevommemoravaloareasa,legturactreprinte,catrefiulstangicatrefiuldrept. Dac unul dintre acetia nu exist, legtura va fi NIL. Se vor mai utiliza de asemenea 4 vectori suplimentari: -x, unde x*i+ este coordonata pe orizontal a nodului i; -y, , unde y[i] este coordonata pe vertical a nodului i; -lrgimeStnga,undelrgimeStnga*i+estedistanapexdelailacelmaidinstnganodal subarborelui cu rdcina i; -lrgimeDreapta,undelrgimeDreapta*i+estedistanapexdelailacelmaidindreaptanodal