Acasa | Trimite referat | Cere referat | Contact

Referat Grafuri neorientate

Grafuri neorientate

Categorie: Referate Informatica

Referat downloadat de: 258 ori.

Cauta referat dupa: grafuri neorientate

Descriere referat:

Grafuri neorientate 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)} [pic] 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 V(X. 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 Y(X 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 ({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 eleme

Alte referate din materia: Informatica

Nr.	Nume referat	Hits
1	mtSZPKbW	20
2	TkkvMlabSupl	50
3	qzpymq@dxuzju.com	147
4	email@gmail.com	269
5	pfuqxd@exjswl.com	287
6	ncqcez@hdtnnq.com	244
7	Hard	722
8	ISTORIA INTERNET-ULUI	782
9	Impera	469
10	Info Doc	524
11	Info-TIRON	467
12	Informatica - Grafica pentru web	938
13	Informatica - Introducere in HTML	711
14	Initiere in pc	701
15	Instalarea sistemului de operare Windows	593
16	Internetul ca sursa de comunicare	580
17	Istoria Internetului	617
18	Istoria calculatorului	539
19	Istoria metodelor de proiectare	359
20	Java visavis de C++	401
21	Java vizavi de C	333
22	LIMBAJUL DE PROGRAMARE PASCAL - Programul defineste tipul salariat, o inregistrare cu variante, valorile citite fiind salvate in fisierul salariat.dat	0
23	Limbajul C	413
24	Lista vinuri prg	322
25	Lotus software	293

Acasa Trimite referat Cere referat Adauga la favorite Seteaza ca homepage Contact libertateailuziei Trailere Filme Filme Noi Jocuri Online Jocuri Barbie Jocuri pentru Copii GameBox.ro Make Money Bucuresti regim hotelier