Referat Grafuri

Mai jos puteti citi fragmente din Referat Grafuri si de asemenea puteti face Download Referat Grafuri

Citeste fragmente din Referat Grafuri

Noţiuni introductive: Fie o mulţime finită x={x1,x2,…,xn}.Fie Γ XxX, unde XxX este produsul cartezian al mulţimii X cu ea însăşi. Definiţie. Se numeşte graf orientat perechea ordonată G=(x, Γ). Elementele xi є x se numesc noduri sau vârfuri. Elementele mulţimii Γ se numesc arce.Un arc (xk,xi)єΓ se notează şi cu [xk,xi].Prin abuz de notaţie, vom scrie: [xk,xi]єΓ. În concluzie, graful este: G=(x, Γ)= ({x1,x2,x3,x4},{[x1,x2],[x2,x1],[x3,x4],[x3,x2],[x3,x3]}). Un graf orientat poate fi reprezentat printr-un desen, aşa cum rezultă din imaginea alăturată. Dacă în graful G=(x, Γ) [x,y]єΓ vom spune că x şi y sunt adiacente, iar vârfurile x şi y sunt incidente cu muchia [x,y]. Dacă Γ=Ø (mulţimea vidă),graful G=(x, Γ) se numeşte graf nul şi reprezentarea lui în plan se reduce la puncte izolate. un graf partial se obtine dintr-un graf suprimand anumite arcuri. G=(x, Γ) G1=(x, Γ1) Definiţie: Un subgraf al unui graf orientat G=(x, Γ) este un graf H=(x, Γ1), unde ,iar muchiile din sunt toate muchiile din care au ambele extremităţi în mulţimea Y. Metode de reprezentare în memorie a unui graf orientat : Un graf orientat cu n noduri poate fi memorat prin utilizarea unei matrice booleene cu n linii şi n coloane, numită matricea de adiacenţă: Ai,j = 1,pentru [i,j] є Γ 0,pentru [i,j] є Γ Exemplu: graful orientat următor se reprezintă astfel: 0 1 0 1 A= 1 0 0 0 0 1 1 1 0 0 0 0 Dezavantajul memorării unui graf prin matricea de adiacenţă este dat de faptul că multe elemente ale matricei sunt nule, deci se consumă memorie inutil. Aceasta tehnica se foloseste in rezolvarea problemeor care indeplinesc simultan urmatoarele conditii: • solutia lor poate fi pusa sub forma unui vector s=x1x2,…,xn, cu x1 din A1,x2 din A2,….,xn din An; • multimile A1,A2,…,An sunt mutimi finite, iar elementele lor se considera ca se afla intr-o relatie de ordine bine stabilita; • nu se dispune de o alta metoda de rezolvare mai rapida; OBSERVATII: • nu pentru toate problemele, n este cunoscut de la inceput; • x1,x2,..,xn pot fi la randul lor vectori; • in multe probleme, multimile A1,A2,…,An coincid. La intalnirea unei astfel de probleme, daca nu cunoastem aceasta tehnica, suntem tentati sa generam toate elementele produsului cartezian si fiecare element sa fie testat daca este solutie. Rezolvand problema in acest mod, timpul de executie este atat de mare,incat poate fi considerat infinit, algoritmul neavand nici o valoare practica. OBSERVATIE: Tehnica backtracking are ca rezultat obtinerea tuturor solutiilor problemei. In cazul in care se cere o singura solutie se poate forta oprirea, atunci cand a fost gasita. In general, metoda backtracking foloseste stiva. Vom nota cu “k” nivelul stivei si cu “s[k]” valoarea depusa pe nivelul k. Metoda backtracking are sase functii: • functia init – are rolul de a initializa un nivel al stivei cu cea mai mare valoare mai mica decat toate elementele multimii solutiei. Este prima functie ce actioneaza asupra unui nivel. • functia succesor – va verifica daca exista succesor pentru valoarea prezenta pe un anumit nivel al stivei. Succesor inseamna urmatorul element din multime. L æ 옍ćː댁؁萏Ƴ葞Ƴ摧㭲ö 2 8 : < @ B D „ . z | Ø æ ò ø -valid – are rolul de a verifica daca cu ajutorul acelui succesor se poate ajunge la o solutie. • functia solutie – verifica daca s-a ajuns la o solutie. • functia tipar – are rolul de a prelucra solutia. • functia back – are rolul de a executa rutina backtracking, unica pentru toate problemele. OBSERVATII: • pentru majoritatea problemelor aceasta functie este aceeasi. •functia back toate celelalte functii. Prezentam rutina backtracking: void back( ) { int as;k=1; init( ); while(k>0) { do {as=successor( ); }while(as&&!valid( )); if( as) if(solutie( )) tipar( ); else {k++;init( );} else k--; } } Pe un anumit nivel k se cauta succesorul atat timp cat exista successor care nu este valid . Variabila as are rolul de a retine daca , atunci cand sa iesit din ciclu , am avut successor , in caz in care acesta este valid. Toate variabilele cum ar fi stiva s,nivelul la care s-a ajuns k, sunt variabile globale. Deoarece rezolvarea problemelor cu aceasta matoda necesita timp indelungat de rulare , este indicat sa o utilizam numai atinci cand nu avem la dispozitie un alt algoritm , mai eficient. Mentionam ca exista probleme pentru care nu se cunosc algoritmi eficienti de rezolvare, deci e indicate metoda backtracking. Propunem urmatoarea problema : Sa se coloreze in toate modurile posibile arcele unui graf orientat cu n varfuri si n arce folosind un numar c de culori disponibile astfel incat oricare doua arce incidente sa fie colorate diferit. PAGE 1 PAGE 1 X1 X3 X4 X2 X1 X3 X2 X4 X1 X3 X2 X4 X1 X2 X3 X4 쥁@