My Operagrafuri
Monday, May 2, 2011 4:23:15 PM
GRAFURI
Se numeste graf o pereche ordonata de multimi (X,U), unde X este o multime finite si nevida, iar U o pereche de multimi.
elementele muchiei X se numesc varfuri sau noduri.Multimea X se mai numeste si multimea varfurilor sau multimea nodurilor grafului G. Ea este de forma
X={x1,X2,……xi….xn}, unde xireprezinta nodul i al grafului care are n noduri
ordinal grafului reprezinta numarul de noduri ale grafului
elementele multimii U sunt perechi de noduri, adica submultimi cu doua elementedin multimea X si se noteaza cu uk.Elementul uk este definit de perechea de forma {xi,xj}, unde xi,xj ϵX si xi≠xj.
U={u1,u2,……uk….um}
multimea U are proprietatea se simetrie daca si numai daca, pentru orice pereche de noduri(xi,xj), daca { xi,xj }ϵU, atunci si {xj,xi}ϵU
un graf G=(X,U) este un graf neorientat daca multimea U are proprietatea de simetrie.Multimea U este formata din perechi neordonate { xi,xj }.
un graf G=(X,U) este un graf orientat daca multimea U nu are proprietatea de simetrie.Multimea U este formata din perechi ordonate { xi,xj }.
GRAFUL NEORIENTAT
elementele multimii U(perechi de noduri ) se numesc muchii
O muchie fiind un element din multimea U, este determinate de o submultime cu doua elemente din multimea X; muchia k a grafului Uk, care uneste muchiile xi si xj este determinata de submultimea { xi,xj } si se noteaza cu [xi,xj].[ xi,xj]si [xj,xi] reprezinta aceeasi muchie a grafului.Graful g are m muchii.
numim noduri adiacente orice pereche de noduri care formeaza o muchie
{ xi,xj}ϵU.Fiecare dintre cele doua noduri xi si xj este nod adiacent cu muchia ukϵ[xi,xj]
nodurile vecine unui nod xi sunt toate nodurile xj care sunt adiacente cu el
se numeste nod extreme al unei muchii oricare dintre cele doua noduri care se gaseste la capatul muchiei. Nodurile xi si xj care au o extremitate comuna xk.
Un graf neorientat G este definit de o pereche de multimi: multime nodurilor sale X si multimea muchiilor sale U. El poate fi considerat ca o multime de noduri din care pot fi unite doua cate doua printr-o muchie
Numarul total de grafuri care se pot forma cu nodurile
g=2c_n^2
gradul unui nod xk al grafului G este egal cu numarul muchiilor incidente cu nodul si se noteaza cu d(xk)
se numeste nod terminal un nod care are gradul egal cu 1-d(xk)=1 (incident cu o singura muchie)
se numeste nod izolat un nod care are gradul egal cu 0-d(xk)=0 (nu se gaseste in extremitatea vreunei muchii)
suma gradelor tuturor nodurilor grafului este egala cu dublul numarului de muchii
daca graful G are n noduri (n≥2), atunci cel putin doua noduri au acelasi grad
GRAFUL ORIENTAT
elementele multimii U(perechiile de noduri) se numesc arce. Multimea U se mai numeste si multimea arcelor grafului G.
numarul de arce=m
se numesc noduri adiacente in garful G oricare din perechiile de noduri care formeaza un arc (xi,xj)ϵU sau (xj,xi)ϵU
nodurile xi si xj sunt extremitatiile arcului [xi,xj]. Nodul xieste extremitate initiala a arcului iar nodul xj este extremitatea finala a arcului
se numesc arce incidente doua arce ui si uj care au o extremitate comuna uk
se numeste succesor al nodului xi orice nod la care ajunge un arc care iese din nodul xi.Multimea succesorilor nodului xi este formata din multimea nodurilor la care ajung arcele care ies din nodul xi si se noteaza cu S(xi) si se defineste ca multimea S(x)={ xjϵx/( xi,xj)ϵU }
multimea arcelor care ies din nodul xi se noteaza U+ (xi)
multimea arcelor care intra in nodul xi se noteaza U-( xi)
nodul sursa al grafului este nodul care are multimea succesorilor formata din toate celelalte noduri, mai putin el, iar multimea predecisorilor sai este multimea vida
nodul destinatie al grafului este nodul care are multimea predecesorilor formata din toate celelalte noduri, mai putin el, iarmultimea succesorilor sai este multimea vida
gradul intern al unui nod xi al grafului G este egal cu numarul arcelor care intra in nodul x si se noteaza d-(x)
gradul extern al unui nod xi al grafului G este egal cu numarul arcelor care ies din nodul x si se noteaza d+(x).
REPREZENTARE
Matricea de adiacenta a unui graf este o matrice patrata binara de ordinul n (An,m) ale carui elemente aij sunt definite astfel:
aij={█(1,daca [i,j]∈U@0,daca [i,j]∉U )┤
elementele de pe diagonal principala au valoarea 0, (i≠j)
in cazul unui graf neorientat, matricea de adiacenta este o matrice simetrica fata de diagonal principala
Matricea de incidenta a unui graf este o matrice binara cu n linii si m coloane ale carei elemente aij sunt definite astfel
aij={█(1,daca [i,j]∈U@ 0,daca [i,j]∉U )┤
pe fiecare coloana exista doua elemente cu valoarea 1(pe liniile i si j, care corespund nodurilor incidente) iar restul elementelor au valoarea 0
matricea de incidenta are 2xm elemente egale cu 1, deoarece fiecare muchie este incidenta cu doua noduri
Lista muchiilor unui graf este formata dim m elemente , care contin fiecare, cate o pereche de noduri xi si xj care formeaza o muchie , daca pentru oricare [xi,xj]ϵU.
matricea muchiilor U are dimensiunea 2xm, in care fiecare linie corespunde unei muchii(arc) si in fiecare linie se inregistreaza in cele doua coloane etichetele nodurilor care se gassc la extremitatiile muchiei(arcului)
int U[<m>][2];
vectorul muchiilor u cu dimensiunea m ale carui elemente sunt inregistrari, fiecare inregistrare fiind formata din doua campuri x si y ce contin etichetele nodurilorcare se gasesc la extremitatiile muchiei(arcului). Pentru elementele vectorului se defines tipul de dta muchie, de tip inregistrare
struct muchie
{
int x,y;
}
muchie U[<m>];
Lista de adiacenta este format din listele Li(1≤i≤n) care contin toti vecinii unui nod xi la care se poate ajunge direct din nodul xi, adica toate nodurile xj pentru care[xi,xj]ϵU
graful G=(X,U) se numeste graf nul daca multimea U este vida, adica graful nu are muchii
un graf cu n noduri este un graf complet daca are proprietatea ca oricare ar fi doua noduri ale grafului, ele sunt adiacente, se noteaza cu Kn.
un graf partial al grafului G este el insusi sau un graf care s-a obtinut prin eliminarea unor muchii(arce) din graful G
un subgraf al grafului G este el insusi sau un graf care s-a obtinut prin suprimarea din graful G a unor noduri si a tuturor muchiilor (arcelor) incidente cu acele noduri
un graf complementar al grafului G contine aceleasi noduri ca si graful G, dar nicio muchie din acest graf
LANT
intr-un graf G=(X,U), se defineste lantul ca fiind o succesiune de noduri care are proprietatea ca, oricare ar fi doua noduri successive ele sunt adiacente
lungimea unui lant reprezinta numarul de parcurgeri ale muchiilor, respective arcelor
sublantul este format dintr-un sir continuu de noduri din lant
daca un graf contine un lant intre doua noduri x si y, atunci contine un lant elementar intre nodurile x si y
daca un lant este elementar este si lant elementar
CICLUL
un lant are toate muchiile distincte doua cate doua si extremitatiile care concid se numeste ciclu
ciclul este un lant simplu in care extremitatiile coincide
daca un graf contine un ciclu, atunci contine si un ciclu elementar
DRUMUL
intr-un graf orientat G=(X,U) se defineste un drum ca fiind o succesiune de noduri care au proprietatea ca, oricare ar fi doua noduri successive, ele sunt legate printr-un arc
lungimea unui drum este data de numarul de arce care-l compun
drumul elementar este drumul in care nodurile sunt distincte doua cate doua
drumul simplu este drumul in care arcele sunt distincte doua cate doua
intr-un graf orientatun drum care are toate arcele distincte doua cate doua si extremitatiile care coincide se numeste circuit
daca un graf contine un circuit, atunci contine si un circuit elementar
un graf G se numeste graf conex daca are proprietatea ca pentru orice pereche de noduri diferite intre ele, exista un lant care sa le lege
un graf orientat G se numeste graf tare conex daca are proprietatea ca pentru orice pereche de noduri diferite intre ele, exista un drum care sa le lege
Parcurgerea grafului reprezinta operatia prin care sunt examinate in mod sistematic nodurile sale, pornind de la un nod dat i, astfel incat fiecare nod accesibil prin nodul i pe muchiile (arcele) adiacente sa fie atinse o singura data.
PARCURGEREA IN LATIME(B.F.) se viziteaza mai intai un nod initial i, apoi vecinii acestuia, apoi vecinii nevizitati ai acestora si asa mai departe.
Se folosesc urmatoarele structure de date si date elementare:
variabile de memorie:
n: numarul de ordine al grafului
k: pentru nodul care se prelucreaza
i,j: pentru parcurgerea matricei de adiacenta si a vectorilor
matricea de adiacenta a grafului
vectorul de vizitare vizitat; contine n elemente in care se inregistreaza valorile vizitate.Elementele vectoruli vizitat sunt 1-daca a fost vizitat si 0-daca nu a fost vizitat inca
coada de asteptare C a nodurilor parcurse
Algoritm
se citesc din fisier, valoarea pentru variabila n si matricea de adiacenta a grafului
se initializeaza cu zero elementele vectorului de vizitare vizitat, deoarece initial niciunul dintre noduri nu a fost vizitat
se introduce de la tastatura valoarea variabilei de memorie k coresounzatoare primului nod cu care incepe parcurgerea grafului
se initializeaza coada de asteptare C:
prim<-1;
ultim<-1;
c[prim]<-k;
se actualizeaza vectorul vizitat vizitat[k]<-1;
cat timp coada nu este vida (prim<>ultim), executa
7.se extrage urmatorul element din coada de asteptare
k<-c[prim];
8.pentru toate nodurile i vecine ale varfului k, nevizitate inca, executa
9.se incrementeaza valoare indicatorului ultim pentru a
inregistra urmatorul nd care trebuie vizitat ultim<-ultim+1;
10.se adauga la sfarsitul cozii de asteptare C, nodul i, vecin cu
k, care nu a fost vizitat inca c[ultim]<-i;
11.prin adaugarea nodului j la coada de asteptare c se
considera ca acest nod a fost vizitat, si se actualizeaza
elementul din vectorul de vizitare care corespunde acestui
nod. Se revine la Pas 6. vizitat<-1;
12.se pregateste indicatorul prim, pentru a se extrage urmatorul nod.
prim<-prim+1; Se trece la pas 7.
13. se afiseaza lista nodurilor vizitate, in ordinea in care au fost vizitate, prin
extragerea lor din vectorul C, pornind de la elementul 1 pana la elementul n
PARCURGEREA IN ADANCIME(D.F.) se viziteaza mai intai un nod initial i, dupa care se parcurge primul dintre vecinii sai nevizitati, de exemplu j, dupa care se trece la primul vecin nevizitat al lui j, s.a.m.d. pana cand se parcurge in adancme ramura respectiva.Cand s-a ajuns la capatul ei, se revine la nodul din care s-a plecat ultima data si se parcurge urmatorul sau vecin nevizitat
Se folosesc urmatoarele structure de date si date elementare:
variabile de memorie:
n: numarul de ordine al grafului
k: pentru nodul care se prelucreaza
i,j: pentru parcurgerea matricei de adiacenta si a vectorilor
matricea de adiacenta a grafului a
vectorul de vizitare vizitat; contine n elemente in care se inregistreaza valorile vizitate.Elementele vectoruli vizitat sunt 1-daca a fost vizitat si 0-daca nu a fost vizitat inca
stiva st a nodurilor parcurse
Algoritm
se citesc din fisier valoarea n si matricea de adiacenta a grafului
se initializeaza cu 0 elementele vectorului de vizitare, vizitat, deoarece niciunul dintre noduri nu a fost vizitat inca
se introduce de la tastatura valoarea variabilei de memorie k, corespunzatoare primului nod cu care incepe parcurgerea grafului si se afiseaza eticheta lui
se initializeaza stiva st, astfel
vf<-1;
st[vf]<-k;
se actualizeaza vectorul vizitat atribuind elementului k al vectorului, valoarea 1, vizitat[k]<-1;
cat timp stiva nu este vida(vf<>0), executa
7.se extrage din varful stivei, elementul corespunzator nodului caruia i se vor vizita vecinii k<-st[vf]
8.se initializeaza nodul i cu care incepe cautarea
9.cat timp nu s-a gasit un nod i vecin nodului k, nevizitat inca (i<=n si a[k]=0 sau a[k]=1 si vizitat=1), executa
10.se trece la urmatorul nod, in vederea verificarii si se revine la pas9 i<-i+1;
11. daca nu s-a gasit un nod i vecin nodului k nevizitat inca, atunci se elimina nodul k din stiva prin coborarea varfului stivei
vf<-vf-1; se afiseaza nodul gasit i, si se adauga in varful stivei vf<-vf+1;
st[vf]<-i;
vizitat<-1.se revine la pas6
Drumul cu cost minim
Costul unui drum este reprezentat de suma costturilor muchiilor de pe drum
ALGORITMUL ROY FLOYD
pentru etichete ale nodului k de la 1 la n (adica pentru orice nod al grafului), executa
2.pentru orice pereche de noduri din graf i si j(cu 1≤i≤n si 1≤j≤n), executa
3.daca suma dintre costul drumului de la k la j (a[k]+[k][j]) este mai mica decat costul drumului de la i la j a[j], atunci in matricea costurilor, costul drumului direct de la i la j este inlocuit cu costul drumului care trece prin nodul k
a[j]=a[k]+a[k][j]
ALGORITMUL DIJKSTRA construieste drumurile cu cost minim care pornesc de la un nod oarecare X-nodul sursa pana la fiecare nod din graful G=(X,U)-nodul destinatie.
Algoritmul intretine o multime cu nodurile care au fost deja selectate –S si o coada de prioritati Q cu nodurile care nu au fost inca selectate Q=X-S, astfel:
un nod y este declarant selectat atunci cand s-a determinat costul final al drumului cu costul minim de la nodul sursa x la el
in coada Q prioritatea cea mai mare o are nodul pentru care costul drumului are valoarea cea maimica dintre toate costurile de drumuri care pornesc de la nodul X la celelalte noduri neselectate inca
La fiecare axtragere a unui nod din coada de prioritati Q, nodul este adugat la multimea S, iar coada de prioritati este reorganizata in functie de acest nod. Pentru calcularea drumurilor de lungime minima se intretine o multime D in care se memoreaza costul drumurilor de la nodul X la nodurile neselectate, noduri care se recalculeaza la fiecare extragere de nod.
Algoritm
se initializeaza S=Ø, se citeste nodul initial x si se atribuie multimii S
se initializeaza multimea D cu costurile drumurilor de la care nodul X la toate celelalte noduri ale grafului (sunt preluate din matricea costurilor elementele a[x])
cat timp coada de prioritati Q nu este vida (mai exista noduri neselectate), executa
4.se cauta printer nodurile neselectate nodul y cu cel mai mic cost al drumului(reprezentand elementul care trebuie eliminate din coada de prioritati)
5.se adauga nodul y la multimea S:S=SU{y}
6.pentru fiecare nod neselectat, nod din coada de prioritati, executa
7.se recalculeaza costul drumului de la nodul x la acest nod folosind ca nod intermediary nodul extras
8.daca acest cost este mai mic decat cel din multimea D, atunci el va fi noul cost
GRAFUL HAMILTONIAN
intr-un graf G=(X,U), se numeste lant Hamiltonian lantul elementar care contine toate nodurile grafului
lantul Hamiltonian in care nodul initial coincide cu nodul final se numeste ciclu Hamiltonian
un graf care contine un ciclu Hamiltonian se numeste graf Hamiltonian
un graf Hamiltonian este un graf in care- pornind de la un nod oarecare- se pot parcurge o singura data toate nodurile grafului revenind la nodul initial.
C={1,2,3,6,4,5,1}
GRAF EULERIAN
intr-un graf G=(X,U), se numeste lant eulerian, lantul care contine toate muchiile grafului, fiecare muchie fiind prezenta o singura data
lantul eulerian in care nodul initial coincide cu nodul final se numeste ciclu eulerian
un graf care contine un ciclu eulerian se numeste graf eulerian
C={1,4,6,7,4,5,5,8,3,2,8,5,2,1}
ARBORI
se numeste arbore liber A un graf neorientat conex si fara ciclu
se numeste subarbore al arborelui A=(X,U), orice arbore S=(Y,V) care are proprietatea
orice arbore cu n noduri are n-1 muchii
orice arbore cu n≥2 noduri are cel putin doua noduri terminale
daca un graf partial al grafului G este arbore, el se numeste arbore partial al grafului
un graf G care contine un arbore partial daca si numai daca este un graf conex
ARBORE PARTIAL DE COST MINIM
consideram un graf conex G=(X,U), o functie C:U->R+ care asociaza fiecarei muchii u, un numar real pozitiv c(u), numit costul muchiei si un graf
H=(V ).Functia c se numeste cost
costul grafului este suma costurilor muchiilor grafului
se numeste graf partial de cost minim al grafului G conex, cu functia de cost C, un graf conex H care are costul minim
arborele care este un graf partial de cost minim al grafului conex G, cu functia de cost C, se numeste arbore partial de cost minim(APM)
ALGORITM
se allege un subarbore al arborelui partial de cost minim Hinit
cat timp nu s-a format arborele partial de cost minim, executa:
3.se adauga o muchie sigura din multimea muchiilor ramase
4.se adauga muchia la subarbore
Algoritmul lui Kruskal
pentru fiecare nod i din graf executa, se formeaza arborii partiali Hi
se sorteaza muchiile din U in ordinea crescatoare a costului C
se allege muchia u cu costul minim
se initializeaza APM cu muchia u
cat timp nu s-au selectat cele n-1 muchii, executa
6.se alege o muchie sigura din multimea muchiilor ramase si se formeaza un arbore partial cu aceasta muchie
7.se unifica APM cu arborele format cu muchia sigura
b) Algoritmul lui Prim
1. se initializeaza APM cu nodul radacina r
2. se initializeaza lista H, astfel pentru fiecare nod i din graf executa H(i)<-0;
3. se initializeaza coada de prioritati Q, astfel Q(r)<-0 si pentru fiecare nod i≠r din graf executa Q(i)<-r
4. cat timp nu s-au selectat cele n-1 muchii, executa
5. se allege o muchie sigura din multimea muchiilor nealese, muchia[i,j] ci iϵA si jϵX-A
6.se adauga muchia la lista H:H(j)<-Q(j)
7.se elimina din coada de prioritati nodu j adaugat la arbore, atribuindu-i valoarea 0 Q(j)<-0
8. se actualizeaza coada de prioritati pentru nodurile nealese, astfel pentru fiecare nod i din Q, executa:
- cauta nodul jϵA cu care formeaza muchia cu costul minim
Se numeste graf o pereche ordonata de multimi (X,U), unde X este o multime finite si nevida, iar U o pereche de multimi.
elementele muchiei X se numesc varfuri sau noduri.Multimea X se mai numeste si multimea varfurilor sau multimea nodurilor grafului G. Ea este de forma
X={x1,X2,……xi….xn}, unde xireprezinta nodul i al grafului care are n noduri
ordinal grafului reprezinta numarul de noduri ale grafului
elementele multimii U sunt perechi de noduri, adica submultimi cu doua elementedin multimea X si se noteaza cu uk.Elementul uk este definit de perechea de forma {xi,xj}, unde xi,xj ϵX si xi≠xj.
U={u1,u2,……uk….um}
multimea U are proprietatea se simetrie daca si numai daca, pentru orice pereche de noduri(xi,xj), daca { xi,xj }ϵU, atunci si {xj,xi}ϵU
un graf G=(X,U) este un graf neorientat daca multimea U are proprietatea de simetrie.Multimea U este formata din perechi neordonate { xi,xj }.
un graf G=(X,U) este un graf orientat daca multimea U nu are proprietatea de simetrie.Multimea U este formata din perechi ordonate { xi,xj }.
GRAFUL NEORIENTAT
elementele multimii U(perechi de noduri ) se numesc muchii
O muchie fiind un element din multimea U, este determinate de o submultime cu doua elemente din multimea X; muchia k a grafului Uk, care uneste muchiile xi si xj este determinata de submultimea { xi,xj } si se noteaza cu [xi,xj].[ xi,xj]si [xj,xi] reprezinta aceeasi muchie a grafului.Graful g are m muchii.
numim noduri adiacente orice pereche de noduri care formeaza o muchie
{ xi,xj}ϵU.Fiecare dintre cele doua noduri xi si xj este nod adiacent cu muchia ukϵ[xi,xj]
nodurile vecine unui nod xi sunt toate nodurile xj care sunt adiacente cu el
se numeste nod extreme al unei muchii oricare dintre cele doua noduri care se gaseste la capatul muchiei. Nodurile xi si xj care au o extremitate comuna xk.
Un graf neorientat G este definit de o pereche de multimi: multime nodurilor sale X si multimea muchiilor sale U. El poate fi considerat ca o multime de noduri din care pot fi unite doua cate doua printr-o muchie
Numarul total de grafuri care se pot forma cu nodurile
g=2c_n^2
gradul unui nod xk al grafului G este egal cu numarul muchiilor incidente cu nodul si se noteaza cu d(xk)
se numeste nod terminal un nod care are gradul egal cu 1-d(xk)=1 (incident cu o singura muchie)
se numeste nod izolat un nod care are gradul egal cu 0-d(xk)=0 (nu se gaseste in extremitatea vreunei muchii)
suma gradelor tuturor nodurilor grafului este egala cu dublul numarului de muchii
daca graful G are n noduri (n≥2), atunci cel putin doua noduri au acelasi grad
GRAFUL ORIENTAT
elementele multimii U(perechiile de noduri) se numesc arce. Multimea U se mai numeste si multimea arcelor grafului G.
numarul de arce=m
se numesc noduri adiacente in garful G oricare din perechiile de noduri care formeaza un arc (xi,xj)ϵU sau (xj,xi)ϵU
nodurile xi si xj sunt extremitatiile arcului [xi,xj]. Nodul xieste extremitate initiala a arcului iar nodul xj este extremitatea finala a arcului
se numesc arce incidente doua arce ui si uj care au o extremitate comuna uk
se numeste succesor al nodului xi orice nod la care ajunge un arc care iese din nodul xi.Multimea succesorilor nodului xi este formata din multimea nodurilor la care ajung arcele care ies din nodul xi si se noteaza cu S(xi) si se defineste ca multimea S(x)={ xjϵx/( xi,xj)ϵU }
multimea arcelor care ies din nodul xi se noteaza U+ (xi)
multimea arcelor care intra in nodul xi se noteaza U-( xi)
nodul sursa al grafului este nodul care are multimea succesorilor formata din toate celelalte noduri, mai putin el, iar multimea predecisorilor sai este multimea vida
nodul destinatie al grafului este nodul care are multimea predecesorilor formata din toate celelalte noduri, mai putin el, iarmultimea succesorilor sai este multimea vida
gradul intern al unui nod xi al grafului G este egal cu numarul arcelor care intra in nodul x si se noteaza d-(x)
gradul extern al unui nod xi al grafului G este egal cu numarul arcelor care ies din nodul x si se noteaza d+(x).
REPREZENTARE
Matricea de adiacenta a unui graf este o matrice patrata binara de ordinul n (An,m) ale carui elemente aij sunt definite astfel:
aij={█(1,daca [i,j]∈U@0,daca [i,j]∉U )┤
elementele de pe diagonal principala au valoarea 0, (i≠j)
in cazul unui graf neorientat, matricea de adiacenta este o matrice simetrica fata de diagonal principala
Matricea de incidenta a unui graf este o matrice binara cu n linii si m coloane ale carei elemente aij sunt definite astfel
aij={█(1,daca [i,j]∈U@ 0,daca [i,j]∉U )┤
pe fiecare coloana exista doua elemente cu valoarea 1(pe liniile i si j, care corespund nodurilor incidente) iar restul elementelor au valoarea 0
matricea de incidenta are 2xm elemente egale cu 1, deoarece fiecare muchie este incidenta cu doua noduri
Lista muchiilor unui graf este formata dim m elemente , care contin fiecare, cate o pereche de noduri xi si xj care formeaza o muchie , daca pentru oricare [xi,xj]ϵU.
matricea muchiilor U are dimensiunea 2xm, in care fiecare linie corespunde unei muchii(arc) si in fiecare linie se inregistreaza in cele doua coloane etichetele nodurilor care se gassc la extremitatiile muchiei(arcului)
int U[<m>][2];
vectorul muchiilor u cu dimensiunea m ale carui elemente sunt inregistrari, fiecare inregistrare fiind formata din doua campuri x si y ce contin etichetele nodurilorcare se gasesc la extremitatiile muchiei(arcului). Pentru elementele vectorului se defines tipul de dta muchie, de tip inregistrare
struct muchie
{
int x,y;
}
muchie U[<m>];
Lista de adiacenta este format din listele Li(1≤i≤n) care contin toti vecinii unui nod xi la care se poate ajunge direct din nodul xi, adica toate nodurile xj pentru care[xi,xj]ϵU
graful G=(X,U) se numeste graf nul daca multimea U este vida, adica graful nu are muchii
un graf cu n noduri este un graf complet daca are proprietatea ca oricare ar fi doua noduri ale grafului, ele sunt adiacente, se noteaza cu Kn.
un graf partial al grafului G este el insusi sau un graf care s-a obtinut prin eliminarea unor muchii(arce) din graful G
un subgraf al grafului G este el insusi sau un graf care s-a obtinut prin suprimarea din graful G a unor noduri si a tuturor muchiilor (arcelor) incidente cu acele noduri
un graf complementar al grafului G contine aceleasi noduri ca si graful G, dar nicio muchie din acest graf
LANT
intr-un graf G=(X,U), se defineste lantul ca fiind o succesiune de noduri care are proprietatea ca, oricare ar fi doua noduri successive ele sunt adiacente
lungimea unui lant reprezinta numarul de parcurgeri ale muchiilor, respective arcelor
sublantul este format dintr-un sir continuu de noduri din lant
daca un graf contine un lant intre doua noduri x si y, atunci contine un lant elementar intre nodurile x si y
daca un lant este elementar este si lant elementar
CICLUL
un lant are toate muchiile distincte doua cate doua si extremitatiile care concid se numeste ciclu
ciclul este un lant simplu in care extremitatiile coincide
daca un graf contine un ciclu, atunci contine si un ciclu elementar
DRUMUL
intr-un graf orientat G=(X,U) se defineste un drum ca fiind o succesiune de noduri care au proprietatea ca, oricare ar fi doua noduri successive, ele sunt legate printr-un arc
lungimea unui drum este data de numarul de arce care-l compun
drumul elementar este drumul in care nodurile sunt distincte doua cate doua
drumul simplu este drumul in care arcele sunt distincte doua cate doua
intr-un graf orientatun drum care are toate arcele distincte doua cate doua si extremitatiile care coincide se numeste circuit
daca un graf contine un circuit, atunci contine si un circuit elementar
un graf G se numeste graf conex daca are proprietatea ca pentru orice pereche de noduri diferite intre ele, exista un lant care sa le lege
un graf orientat G se numeste graf tare conex daca are proprietatea ca pentru orice pereche de noduri diferite intre ele, exista un drum care sa le lege
Parcurgerea grafului reprezinta operatia prin care sunt examinate in mod sistematic nodurile sale, pornind de la un nod dat i, astfel incat fiecare nod accesibil prin nodul i pe muchiile (arcele) adiacente sa fie atinse o singura data.
PARCURGEREA IN LATIME(B.F.) se viziteaza mai intai un nod initial i, apoi vecinii acestuia, apoi vecinii nevizitati ai acestora si asa mai departe.
Se folosesc urmatoarele structure de date si date elementare:
variabile de memorie:
n: numarul de ordine al grafului
k: pentru nodul care se prelucreaza
i,j: pentru parcurgerea matricei de adiacenta si a vectorilor
matricea de adiacenta a grafului
vectorul de vizitare vizitat; contine n elemente in care se inregistreaza valorile vizitate.Elementele vectoruli vizitat sunt 1-daca a fost vizitat si 0-daca nu a fost vizitat inca
coada de asteptare C a nodurilor parcurse
Algoritm
se citesc din fisier, valoarea pentru variabila n si matricea de adiacenta a grafului
se initializeaza cu zero elementele vectorului de vizitare vizitat, deoarece initial niciunul dintre noduri nu a fost vizitat
se introduce de la tastatura valoarea variabilei de memorie k coresounzatoare primului nod cu care incepe parcurgerea grafului
se initializeaza coada de asteptare C:
prim<-1;
ultim<-1;
c[prim]<-k;
se actualizeaza vectorul vizitat vizitat[k]<-1;
cat timp coada nu este vida (prim<>ultim), executa
7.se extrage urmatorul element din coada de asteptare
k<-c[prim];
8.pentru toate nodurile i vecine ale varfului k, nevizitate inca, executa
9.se incrementeaza valoare indicatorului ultim pentru a
inregistra urmatorul nd care trebuie vizitat ultim<-ultim+1;
10.se adauga la sfarsitul cozii de asteptare C, nodul i, vecin cu
k, care nu a fost vizitat inca c[ultim]<-i;
11.prin adaugarea nodului j la coada de asteptare c se
considera ca acest nod a fost vizitat, si se actualizeaza
elementul din vectorul de vizitare care corespunde acestui
nod. Se revine la Pas 6. vizitat<-1;
12.se pregateste indicatorul prim, pentru a se extrage urmatorul nod.
prim<-prim+1; Se trece la pas 7.
13. se afiseaza lista nodurilor vizitate, in ordinea in care au fost vizitate, prin
extragerea lor din vectorul C, pornind de la elementul 1 pana la elementul n
PARCURGEREA IN ADANCIME(D.F.) se viziteaza mai intai un nod initial i, dupa care se parcurge primul dintre vecinii sai nevizitati, de exemplu j, dupa care se trece la primul vecin nevizitat al lui j, s.a.m.d. pana cand se parcurge in adancme ramura respectiva.Cand s-a ajuns la capatul ei, se revine la nodul din care s-a plecat ultima data si se parcurge urmatorul sau vecin nevizitat
Se folosesc urmatoarele structure de date si date elementare:
variabile de memorie:
n: numarul de ordine al grafului
k: pentru nodul care se prelucreaza
i,j: pentru parcurgerea matricei de adiacenta si a vectorilor
matricea de adiacenta a grafului a
vectorul de vizitare vizitat; contine n elemente in care se inregistreaza valorile vizitate.Elementele vectoruli vizitat sunt 1-daca a fost vizitat si 0-daca nu a fost vizitat inca
stiva st a nodurilor parcurse
Algoritm
se citesc din fisier valoarea n si matricea de adiacenta a grafului
se initializeaza cu 0 elementele vectorului de vizitare, vizitat, deoarece niciunul dintre noduri nu a fost vizitat inca
se introduce de la tastatura valoarea variabilei de memorie k, corespunzatoare primului nod cu care incepe parcurgerea grafului si se afiseaza eticheta lui
se initializeaza stiva st, astfel
vf<-1;
st[vf]<-k;
se actualizeaza vectorul vizitat atribuind elementului k al vectorului, valoarea 1, vizitat[k]<-1;
cat timp stiva nu este vida(vf<>0), executa
7.se extrage din varful stivei, elementul corespunzator nodului caruia i se vor vizita vecinii k<-st[vf]
8.se initializeaza nodul i cu care incepe cautarea
9.cat timp nu s-a gasit un nod i vecin nodului k, nevizitat inca (i<=n si a[k]=0 sau a[k]=1 si vizitat=1), executa
10.se trece la urmatorul nod, in vederea verificarii si se revine la pas9 i<-i+1;
11. daca nu s-a gasit un nod i vecin nodului k nevizitat inca, atunci se elimina nodul k din stiva prin coborarea varfului stivei
vf<-vf-1; se afiseaza nodul gasit i, si se adauga in varful stivei vf<-vf+1;
st[vf]<-i;
vizitat<-1.se revine la pas6
Drumul cu cost minim
Costul unui drum este reprezentat de suma costturilor muchiilor de pe drum
ALGORITMUL ROY FLOYD
pentru etichete ale nodului k de la 1 la n (adica pentru orice nod al grafului), executa
2.pentru orice pereche de noduri din graf i si j(cu 1≤i≤n si 1≤j≤n), executa
3.daca suma dintre costul drumului de la k la j (a[k]+[k][j]) este mai mica decat costul drumului de la i la j a[j], atunci in matricea costurilor, costul drumului direct de la i la j este inlocuit cu costul drumului care trece prin nodul k
a[j]=a[k]+a[k][j]
ALGORITMUL DIJKSTRA construieste drumurile cu cost minim care pornesc de la un nod oarecare X-nodul sursa pana la fiecare nod din graful G=(X,U)-nodul destinatie.
Algoritmul intretine o multime cu nodurile care au fost deja selectate –S si o coada de prioritati Q cu nodurile care nu au fost inca selectate Q=X-S, astfel:
un nod y este declarant selectat atunci cand s-a determinat costul final al drumului cu costul minim de la nodul sursa x la el
in coada Q prioritatea cea mai mare o are nodul pentru care costul drumului are valoarea cea maimica dintre toate costurile de drumuri care pornesc de la nodul X la celelalte noduri neselectate inca
La fiecare axtragere a unui nod din coada de prioritati Q, nodul este adugat la multimea S, iar coada de prioritati este reorganizata in functie de acest nod. Pentru calcularea drumurilor de lungime minima se intretine o multime D in care se memoreaza costul drumurilor de la nodul X la nodurile neselectate, noduri care se recalculeaza la fiecare extragere de nod.
Algoritm
se initializeaza S=Ø, se citeste nodul initial x si se atribuie multimii S
se initializeaza multimea D cu costurile drumurilor de la care nodul X la toate celelalte noduri ale grafului (sunt preluate din matricea costurilor elementele a[x])
cat timp coada de prioritati Q nu este vida (mai exista noduri neselectate), executa
4.se cauta printer nodurile neselectate nodul y cu cel mai mic cost al drumului(reprezentand elementul care trebuie eliminate din coada de prioritati)
5.se adauga nodul y la multimea S:S=SU{y}
6.pentru fiecare nod neselectat, nod din coada de prioritati, executa
7.se recalculeaza costul drumului de la nodul x la acest nod folosind ca nod intermediary nodul extras
8.daca acest cost este mai mic decat cel din multimea D, atunci el va fi noul cost
GRAFUL HAMILTONIAN
intr-un graf G=(X,U), se numeste lant Hamiltonian lantul elementar care contine toate nodurile grafului
lantul Hamiltonian in care nodul initial coincide cu nodul final se numeste ciclu Hamiltonian
un graf care contine un ciclu Hamiltonian se numeste graf Hamiltonian
un graf Hamiltonian este un graf in care- pornind de la un nod oarecare- se pot parcurge o singura data toate nodurile grafului revenind la nodul initial.
C={1,2,3,6,4,5,1}
GRAF EULERIAN
intr-un graf G=(X,U), se numeste lant eulerian, lantul care contine toate muchiile grafului, fiecare muchie fiind prezenta o singura data
lantul eulerian in care nodul initial coincide cu nodul final se numeste ciclu eulerian
un graf care contine un ciclu eulerian se numeste graf eulerian
C={1,4,6,7,4,5,5,8,3,2,8,5,2,1}
ARBORI
se numeste arbore liber A un graf neorientat conex si fara ciclu
se numeste subarbore al arborelui A=(X,U), orice arbore S=(Y,V) care are proprietatea
orice arbore cu n noduri are n-1 muchii
orice arbore cu n≥2 noduri are cel putin doua noduri terminale
daca un graf partial al grafului G este arbore, el se numeste arbore partial al grafului
un graf G care contine un arbore partial daca si numai daca este un graf conex
ARBORE PARTIAL DE COST MINIM
consideram un graf conex G=(X,U), o functie C:U->R+ care asociaza fiecarei muchii u, un numar real pozitiv c(u), numit costul muchiei si un graf
H=(V ).Functia c se numeste cost
costul grafului este suma costurilor muchiilor grafului
se numeste graf partial de cost minim al grafului G conex, cu functia de cost C, un graf conex H care are costul minim
arborele care este un graf partial de cost minim al grafului conex G, cu functia de cost C, se numeste arbore partial de cost minim(APM)
ALGORITM
se allege un subarbore al arborelui partial de cost minim Hinit
cat timp nu s-a format arborele partial de cost minim, executa:
3.se adauga o muchie sigura din multimea muchiilor ramase
4.se adauga muchia la subarbore
Algoritmul lui Kruskal
pentru fiecare nod i din graf executa, se formeaza arborii partiali Hi
se sorteaza muchiile din U in ordinea crescatoare a costului C
se allege muchia u cu costul minim
se initializeaza APM cu muchia u
cat timp nu s-au selectat cele n-1 muchii, executa
6.se alege o muchie sigura din multimea muchiilor ramase si se formeaza un arbore partial cu aceasta muchie
7.se unifica APM cu arborele format cu muchia sigura
b) Algoritmul lui Prim
1. se initializeaza APM cu nodul radacina r
2. se initializeaza lista H, astfel pentru fiecare nod i din graf executa H(i)<-0;
3. se initializeaza coada de prioritati Q, astfel Q(r)<-0 si pentru fiecare nod i≠r din graf executa Q(i)<-r
4. cat timp nu s-au selectat cele n-1 muchii, executa
5. se allege o muchie sigura din multimea muchiilor nealese, muchia[i,j] ci iϵA si jϵX-A
6.se adauga muchia la lista H:H(j)<-Q(j)
7.se elimina din coada de prioritati nodu j adaugat la arbore, atribuindu-i valoarea 0 Q(j)<-0
8. se actualizeaza coada de prioritati pentru nodurile nealese, astfel pentru fiecare nod i din Q, executa:
- cauta nodul jϵA cu care formeaza muchia cu costul minim
