Acest site foloseste cookies. Prin navigarea pe acest site, va exprimati acordul asupra folosirii cookie-urilor. Citeste mai mult... X
Referatele si lucrarile oferite de Clopotel.ro au scop educativ si orientativ pentru cercetare academica.

Grafuri neorientate

Materie: Informatica
Accesari: 11.718
Download-uri: 2.797
Nota: 7.33 (1193 note)
Am probleme cu acest referat!

1 2 3
4 5 6
7 8 9


Download Referat - Grafuri neorientate
Publicitate:

Trimis de aurel
din 10 Martie 2006

Definitie: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)}

Pentru o muchie uk=(x,y), vom spune ca :varfurile x si y sunt adiacente si se numesc extremitatile muchiei uk ;muchia uk si varful x sunt incidente in graf(la fel, muchia uk si varful b);muchia (x,y) este totuna cu (y,x) (nu exista o orientare a muchiei);Doua muchii care au o extremitate comuna se numesc incidente.

Definitie:
Gradul unui varf x, notat d(x), reprezinta numarul muchiilor care trec prin nodul x (incidente cu nodul x).Exemplu: d(1)=3, d(2)=2, d(4)=0, d(5)=1.Un varf care are gradul 0 se numeste varf izolat(de exemplu varful 4).Un varf care are gradul 1 se numeste varf terminal(de exemplu varful 5).

Propozitie:
Fie G=(X,U) un graf neorientat cu n noduri si m muchii, suma gradelor tuturor nodurilor este egala cu 2m.Intr-un graf neorientat numarul nodurilor de grad impar este un numar par.Se numeste graf partial al grafului G=(X,U) un graf neorientat G'=(X,V), unde VX. Altfel spus, un graf G' a lui G, este chiar G sau se obtine din G pastrand toate varfurile si suprimand niste muchii.Se numeste subgraf al grafului G=(X,U) ungraf neorientat H=(Y,V), unde YX iar V contine toate muchiile din U care au ambele extremitati in multimea Y.

Reprezentarea grafurilor neorientate
Cele mai cunoscute forme de reprezentare ale unui astfel de graf sunt: matricea de adiacenta, listele vecinilor si vectorul muchiilor.

Matricea de adiacenta
Este o matrice patratica cu n linii si n coloane, in care elementele a[i,j] se definesc astfel: a[i,j]=1 daca exista (i,j) in U, cu x diferit de y si 0 daca nu exista (i,j) in U.
Pentru graful G=(X,U) din figura de mai jos, matricea de adiacenta este:
linia
0 1 1 1 1
1 0 1 0 2
A= 1 1 0 1 3
1 0 1 0 4
coloana 1 2 3 4
a[i,j]=a[j,i] oricare ar fi i,j I{1,2,.....,n}

Proprietatile matricei de adiacenta:Este o matrice simetrica;Pe diagonala principala are toate elemntele egale cu 0;Suma elementelor pe linia sau coloana i este egala cu gradul nodului i;Daca elementele pe linia/coloana i sunt toate egale cu 0 atunci nodul este izolat;Daca toate elementele din matrice,mai putin cele de pe diagonala principala, sunt 1 inseamna ca graful este complet.

Listele vecinilor
Pentru fiecare nod al grafului se retin nodurile adiacente cu el.Pentru reprezentarea listei de adiacenta se poate folosi alocare dinamica.Exemplu pentru matricea de adiacenta de mai sus:

nodul lista vecinilor
2, 3, 4
1, 3
1, 2, 4
1, 3

Vectorul muchiilor
Fiecare muchie a grafului poate fi privita ca o inregistrare cu doua componente: cele doua varfuri care constitue extremitatile muchiei. Notand aceste extremitati cu nod1 si nod2, putem defini tipul de date tmuchie, astfel:

type tmuchie=record
nod1,nod2:integer;
end;

Graful in ansamblul sau, este o multime de muchii, adica o multime de elemente de tipul tmuchie.In consecinta definim graful ca un "vector de muchii", adica un vector cu elementele de tipul tmuchie:var v:array[1..25] of tmuchie;Graf complet si graf bipartit.Se numeste graf complet cu n varfuri, notat Kn, un graf G=(X,U) cu proprietatea ca intre oricare doua varfuri exista o muchie.

Exemplu:Un graf complet cu n varfuri are n*(n-1)/2 muchii.
Un graf neorientat G=(X,U) se numeste bipartit daca exista 2 multimi de noduri A si BIX astfel incat AEB=X si AB=A; iar orice muchie din U are o extremitate in multimea A si una in multimea B.Exemplu: Fie G=(X,U) unde X={1,2,3,4,5,6,7}, U={(1;5),(2;6),(3;6),(4;7)}

Cu multimile A={1,2,3,4} si B={5,6,7}
Se obesrva ca: AEB=X, AB=A, iar fiecare muchie are o extremitate in A si una in B.

Se numeste graf bibartit complet, un graf bipartit cu proprietatea ca pentru orice varf x din A si orice varf y din B, exista muchia(x,y) (unde A si B sunt cele doua submultimi care partitioneaza multimea varfurilorX).
Exemplu:

Notiunile de lant si ciclu:
Se numeste lant in graful G, o succesiune de varfuri L=(x1,x2,.....,xp),cu xi IX,in care(")2 noduri consecutive din succesiune sunt adiacente, adica exista muchiile(x1,x2),(x2,x3),....,(xp-1,xp)IU.Varfurile x1 si xp se numesc extremitatile lantului, iar numarul de muchii care intra in componenta sa reprezinta lungimea lantului.Un lant in care (") 2 elemente sunt diferite se numeste lant elementar. Altfel lantul este neelementar.

Exem...

Atentie : Textul de mai sus este doar un preview al referatului, pentru a vedea daca continutul acestui referat te poate ajuta. Pentru varianta printabila care poate sa contina imagini sau tabele apasa butonul de 'download' !!!
Download Referat - Grafuri neorientate