Matricea costurilor

Se numeste graf ponderat ("weighted graph") un graf in cadrul cãruia fiecãrui arc ii este asociatã o valoare. Valoarea asociata arcului are semnificaþia de "cost" a legaturii intre cele 2 noduri sau de "distanta" intre noduri.

Fie G=(V, E) un graf neorientat, unde V are n elemente (n noduri) si E are m elemente (m muchii) memorat prin matricea ponderilor. Se cere ca pentru doua noduri x,y citite sa se determine lungimea minima a lantului de la x la y.

Astfel:

Initial matricea ponderilor pentru nodurile 1 si 4 va retine 10. Se observa ca lantul 1,2,3,4 determina o suma a costurilor mai mica: 2+3+1=6. Lungime minima a lantului de la 1 la 4 este 6.

Algoritmul:
-se genereaza matricea ponderilor:
0 2 pinf 10 pinf
2 0 3 pinf pinf
pinf 3 0 1 8
10 pinf 1 0 pinf
pinf pinf 8 pinf 0
Unde pinf reprezinta plus infinit

-se incearca pentru oricare pereche de noduri i,j sa se obtina “drumuri” mai scurte prin noduri intermediare k (kÎ1…n).

Acest lucru se determina comparand “lungimea” lantului a[i,j] cu lungimea lantului care trece prin k si daca:
a[i,j] > a[i,k]+a[k,j] atunci se atribuie: a[i,j] ¬ a[i,k]+a[k,j]

Astfel generarea matricii drumurilor optime se realizeaza cu urmatoarea secventa:

for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(a[i][j]>a[i][k]+a[k][j])
a[i][j]=a[i][k]+a[k][j];

Se obtine:
0 2 5 6 13
2 0 3 4 11
5 3 0 1 8
6 4 1 0 9
13 11 8 9 0


In continuare, dupa determinarea matricii lanturilor optime, pentru doua noduri citite x, y se cere sa se reconstituie un lant optim de la x la y (pot fi mai multe solutii).

Solutie:
-se determina daca exista un lant de la x la y (ar putea sa nu existe un astfel de lant daca graful nu este conex):
cand a[x,y] ¹¥
-se descompune “drumul” de la x la y prin ca atunci cand: a[x][y]=a[x][k]+a[k][y];
- pentru un astfel de algoritm se utilizeaza strategia Divide et Impera

Matricea drumurilor

Fie G=(V, E) un graf neorientat, unde V are n elemente (n noduri) si E are m elemente (m muchii). Lui G i se asociaza matricea drum, numita matricea lanturilor, cu n linii si n coloane.

Astfel: drum = (drumi j) n x n cu:


1, daca [i,j]ÎE
drum[i,j]=
0, altfel


Matricea lanturilor ca si matricea de adiacenta, in cazul grafurilor neorientate , este o matrice simetrica (daca exista lant de la i la j exista si lant de la j la i).

Grafului de mai jos i se asociaza urmatoarea matrice a lanturilor:

0 1 1 1 1 0 0
1 0 1 1 1 0 0
1 1 0 1 1 0 0
1 1 1 0 1 0 0
1 1 1 1 0 0 0
0 0 0 0 0 0 1
0 0 0 0 0 1 0


Linia k (sau coloana k) a matricei lanturilor ne arata nodurile j pentru care exista lant de k la j ( si de la j la k). Spre exemplu, pentru nodul 3 .

0 1 1 1 1 0 0
1 0 1 1 1 0 0
1 1 0 1 1 0 0
1 1 1 0 1 0 0
1 1 1 1 0 0 0
0 0 0 0 0 0 1
0 0 0 0 0 1 0

Nu se poate ajunge de la nodul 3 la nodurile 6 sau 7.

Parcurgerea grafurilor în adâncime

Foarte mulţi algoritmi de prelucrare a grafurilor necesită examinarea tuturor nodurilor unui graf. Pentru aceasta este necesară definirea unei strategii de traversare a grafului. Se poate vorbi în principal de două tehnici de traversare: în adâncime (Depth First)în lăţime (Breadth First)În explicarea modului de funcţionare a primei variante se foloseşte un şir de întregi, VIZITAT, de lungime n cu ajutorul căruia se marchează nodurile deja "vizitate" pentru a evita trecerea de mai multe ori prin acelaşi nod. Cu alte cuvinte VIZITAT[j] = 1 dacă nodul j a fost deja atins şi VIZITAT[j] = 0 în caz contrar. Vom spune despre un nod i că a fost explorat dacă are toate nodurile adiacente vizitate. Procedura recursivă care asigură parcurgerea unui graf în adâncime începând cu un anumit vârf i: Procedura Parcurgere_în_adâncime(i)pentru toate vârfurile k adiacente cu vârful i executădaca vârful k este neparcursatunci se parcurge vârful kapel parcurgere_în_adâncime(k)Ieşirea din recursivitate se produce în momentul în care nu se mai găsesc vârfuri neparcurse adiacente cu vârfurile parcurse deja. Este posibil ca după un apel al procedurii incepând cu un anumit vârf i să rămână în graf vârfuri neparcurse. În această situaţie apelul procedurii se repetă pentru un alt vârf iniţial (dintre vârfurile neparcurse) până la parcurgerea tuturor nodurilor grafului. Programul apelant trebuie să asigure parcurgerea vârfului utilizat în apel. Condiţiile interne care apar în problemele particulare de backtracking pot impune o parcurgere integrală sau numai parţială a grafului. Procedura backtracking(i) este pentru cazul parcurgerii integrale a unui graf în adâncime: Procedura Backtracking(i)pentru toate vârfurile k adiacente cu vârful i executădaca vârful k este neparcurs şi sunt îndeplinite condiţiile de continuareatunci se parcurge vârful kse utilizeaza vârful k în soluţiedacă s-a ajuns la o soluţie se afişeazăapel Backtracking(k)Folosind această tehnică de traversare ne propunem să răspundem la întrebarea: Fiind dat un graf neorientat G=(V, E), este acesta un graf conex?Conform acestei metode explorarea unui nod este suspendată ori de câte ori un nou vârf este vizitat. Pentru graful G daca pornim din vârful 1, vizitarea nodurilor se va face în ordinea: 1, 2, 4, 8, 5, 6, 3, 7.

Parcurgerea in latime a grafurilor

Parcurgerea unui graf neorientat indica posibilitatea de a ajunge o singura data in fiecare varf al grafului, pornind de la un varf dat “xk” si parcurgand muchii adiacente. Aceasta operatiune poarta numele de vizitare sau traversare a varfurilor grafului si este efectuata cu scopul prelucrarii informatiei asociata varfurilor.Deoarece graful este o structura neliniara de organizare a datelor, prin parcurgerea sa in mod systematic se realizeaza si o aranjare liniaraq a varfurilor sale, deci informatiile stocate in varfuri se pot regasi si prelucra mai usor. Pentru a facilita scrierea, convenim ca in loc de {x1,x2,…, xn} sa se scrie {1,2,…,n}, fara ca valabilitatea rezultatelor sa fie diminuata. Astfel, prin similitudine, se poate folosi drept relatie de ordine intre varfurile grafului, relatia de ordine din numerele naturale (notata cu “<”).Metoda de parcurgere BFNumele provine din limba engleza (Breadth First-“in latime”) si principiul este: se viziteaza intai varful initial, apoi vecinii acestuia, apoi vecinii nevizitati ai acestora, si asa mai departe.Vizitarea unui varf inseamna de fapt o anumita prelucrare specificata asupra varfului respectiv.Derularea algoritmului presupune alegerea, la un moment dat, dintre toti vecinii unui varf, pe acela ce nu a fost inca vizitat. Acest lucru este posibil prin folosirea unui vector VIZITAT de dimensiune n, ale carui componente se definesc astfel: pentru ( k({1,2,3,…,n}:VIZITAT[k] ( 1, daca varful k a fost vizitat( 0, in caz contrar Se foloseste o structura de tip coada (simulata in alocare statica printr-un vector V) in care prelucrarea unui varf k aflat la un capat al cozii (varful cozii), consta in introducerea in celalat capat al ei (coada cozii), a tuturor varfurilor j vecine cu k, nevizitate inca. Pentru inceput, k este egal cu varful indicat initial i si toate componentele lui VIZITAT sunt zero.Algoritmul consta in urmatorii pasi:se prelucreaza varful initial k;se adauga varful k in coada;varful k se considera vizitat;cat timp coada este nevida se executa:pentru toti vecinii j nevizitati inca ai varfului k, executa:se adauga varful j in coada;varful j se considera vizita;varful j devine varful k;3) se afiseaza continutul cozii;

lanturi.cicluri.drumuri

Lanturi. Drumuri
A. Pentru grafuri neorientate
Se numeste lant o succesiune de noduri x1 ... xk, cu proprietatea ca oricare doua noduri vecine (xi,xi+1) apartin de B.
x1, xk sunt extremitatile lantului.
Lungimea lantului este egala cu numarul de muchii care il compun, k-1.
Daca nodurile din lant sunt distincte, atunci lantul este elementar.

B. Pentru grafuri orientate
Se numeste lant o succesiune de arce u1, u2 ... uk, cu proprietatea ca oricare doua arce de pe pozitii consecutive au un nod comun.
Observatie: nu conteaza ordinea de parcurgere
Se numeste drum o succesiune de noduri x1, x2 ... xk cu proprietatea ca (xi,xi+1) este arc.
Observatie: conteaza ordinea de parcurgere
Daca nodurile sunt distincte, drumul se numeste elementar

Cicluri. Circuite

A. Pentru grafuri neorientate
Se numeste ciclu intr-un graf neorientat un lant x1,x2 ... xk si oricare 2 muchii (xi,xi+1) sunt distincte.
Daca un ciclu are toate nodurile distincte 2 cate 2 cu exceptia capetelor, atunci el se numeste ciclu elementar.


B. Pentru grafuri orientate
Se numeste circuit intr-un graf un drum x1,x2 ... xk cu proprietatea ca x1 = xk si arcele (xi,xi+1) sa fie distincte 2 cate 2.
Un circuit in care toate nodurile sunt distincte cu exceptia capetelor se numeste circuit elementar.



Grafuri conexe
Un graf este conex daca este format dintr-un singur nod sau daca intre oricare doua noduri ale sale exista cel putin un lant.


Se numeste componenta conexa a unui graf un sungraf al sau care este conex si care este maximal in raport cu aceasta proprietate (daca i se adauga un nod isi pierde aceasta proprietate).
Observatie: pentru grafurile orientate nu se tine cont de orientarea arcelor.

Grafuri tare conexe
Un graf este tare conex daca ar un singur nod sau daca oricare ar fi (x,y) exista drum de la x la y si exista drum de la y la x.
Determinarea componentelor tare conexe
Se poate realiza prin 3 metode:
Utilizand metoda DF/BF
Utilizand matricea drumurilor
Algoritmul +/-
O componenta tare conexa este un subgraf al sau care este tare conex si care este maximal in raport cu aceasta proprietate.
Observatie: reunind toate arcele din componentele tare conexe se poate obtine o multime mai mica decat multimea arcelor grafului initial.
Se poate construi un graf al componentelor tare conexe in care fiecare componenta tare conexa formeaza un nod iar arcele simuleaza legaturile dintre ele.

Grafuri hamiltoniene
Lant hamiltonian: lant elementar care contine toate nodurile grafului.
Ciclu hamiltonian: ciclu elementar care contine toate nodurile grafului.
Graf hamiltonian: graf care contine un ciclu hamiltonian.


Grafuri euleriene
Ciclu eulerian: ciclu care trece prin toate muchiile unui graf exact o data.
Graf eulerian: graf care contine cel putin un ciclu eulerian.

grafuri

Numim graf o pereche ordonată de mulţimi, notată G=(X,U), unde X este o mulţime finită şi nevidă de elemente numite noduri sau vârfuri, iar U este o mulţime de perechi (ordonate sau neordonate) de elemente din X numite muchii (dacă sunt perechi neordonate) sau arce (dacă sunt perechi ordonate). În primul caz, graful se numeşte orientat, altfel acesta este neorientat.Aşadar un graf poate fi reprezentat sub forma unei figuri geometrice alcătuite din puncte (care corespund vârfurilor) şi din linii drepte sau curbe care unesc aceste puncte (care corespund muchiilor sau arcelor).
Grafuri neorientate
Se numeste graf neorientat, o pereche ordonata de multimi notata G=(X,U), unde X={x1,x2,...,xn} este o multime finite si nevida de elemnte numite noduri sau varfuri, iar U={u1,u2,...,un} este o multime de perechi neordonate de elemente din X numite muchii. Asadar un neorientat poate fi reprezentat sub forma unei figure geometrice alcatuite din puncte(noduri,varfuri) si linii drepte sau curbe care unesc aceste puncte (muchii,arce). Exemplu: G=(X,U) X={1,2,3,4,5,6,7,8,9,10} U={(1,2);(1,3);(1,5);(2,3);(6,7);(6,10);(7,8);(8,9);(9,10)}
Nod = element al mulţimii V, unde G=(V, E) este un graf neorientat. Muchie = element al mulţimii E ce descrie o relaţie existentă între două vârfuri din V, unde G=(V, E) este un graf neorientat;
Adiacenta: Într-un graf neorientat existenţa muchiei (v,w) presupune că w este adiacent cu v şi v adiacent cu w. Incidenţă = o muchie este incidentă cu un nod dacă îl are pe acesta ca extremitate. Muchia (v,w) este incidentă în nodul v respectiv w. Grad = Gradul unui nod v, dintr-un graf neorientat, este un număr natural ce reprezintă numărul de noduri adiacente cu acesta (sau numarul de muchii incidente cu nodul respectiv) Nod izolat = Un nod cu gradul 0. Nod terminal= un nod cu gradul 1
Graf complet = graf neorientat G=(V,E) în care există muchie între oricare două noduri.
Numărul de muchii ale unui graf complet este: nr*(nr-1)/2.Unde nr este numarul de noduri
graf complet. Nr de muchii: 4x(4-1)/2 = 6
Numim ordinul unui graf, numărul de noduri al grafului, deci cardinalul mulţimii X(G), şi notăm această valoare cu G .