Grafuri neorientate

Trimis la data: 2004-06-08 Materia: Informatica Nivel: Liceu Pagini: 6 Nota: / 10 Downloads: 12
Autor: Roxana mantulasa Dimensiune: 25kb Voturi: Tipul fisierelor: doc Acorda si tu o nota acestui referat: 1 2 3 4 5 6 7 8 9 10
vezi mai multe detalii vezi mai putine detalii
Raporteaza o eroare
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 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 4a[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 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 B(X astfel incat A(B=X si A(B=(; 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: A(B=X, A(B=(, 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 (X, in care (() 2 noduri consecutive din succesiune sunt adiacente, adica exista muchiile (x1,x2),(x2,x3),….,(xp-1,xp)(U.
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.


Exemplu:


Lant elementar:1,2,3,4,5; 6,7,3,9,4,8…
Lant neelementar: 1,2,3,2;





Un graf G este conex, daca oricare ar fi doua varfuri ale sale , exista un lant care le leaga.
Se numeste ciclu intr-un graf, un lant in care extremitatile coincid si muchiile sunt diferite intre ele.
Exemplu: c1=(3,4,5,3,7,6,1,2,3), c2=(1,2,3,7,6,1), c3=(3,5,4,9,3)
Daca intr-un ciclu, toate varfurile cu exceptia primului si a ultimului sunt distincte doua cate doua, atunci ciclul se numeste elementar. In caz contrar el este neelementar.
Ciclurile c2 si c3 din exemplul anterior sunt elementare,iar c1 este neelementar(in c1, varful 3 apare si ca varf “intermediar”,adica traseul descris mai trece odata prin varful 3 pe langa faptul ca porneste din el si se intoarce tot in el.).

Parcurgerea grafurilor neorientate

Prin parcurgerea grafurilor neorientate se intelege vizitarea varfurilor intr-o anumita ordine, ordine data de un anumit criteriu.
Exista doua metode de parcurgere:
Parcurgerea in latime BF(Breadth First);
Parcurgerea in adancime DF(Depth First);

Algoritmul de parcurgere in latime BF
Fiind dat un graf neorientat G=(X,U) si un nod x(X, sa se parcurga toate varfurile grafului incepand din varful x.
Metoda consta in:
-se viziteaza varful de pornire, dupa care se viziteaza toate varfurile adiacente cu acesta care nu au fost vizitate inca,in continuare se alege primul varf adiacent cu varful de pornire si se viziteaza toate varfurile adiacente cu acesta nevizitate inca si asa mai departe pentru celelalte varfuri cat timp este posibil.Exemplu:
Presupunem ca varful de pornire este 1,atunci parcurgerea BF este:1,2,5,6,3,4,7.
Pentu 3 varf de pornire:3,2,4,1,5,6,7.

Pentru implementare vom folosi un vector care are proprietatile unei cozi, fie c=(c1,c2,…,ck). Capetele de intoducere si extragere vor fi identificate prin pozitiile p si respectiv u.
Notam cu n numarul de noduri din graf. Este necesar ca elemntele matricei de adiacenta a cu n linii*n coloane sa fie cunoscute.

Mai avem nevoie de un vector viz cu n elemente, in care elementele viz[k] (k=1,2,….,n) au semnificatia: viz[i]=0, daca varful i nu a fost vizitat sau viz[i]=0 daca a fost vizitat. Mai intai initializam tot vectorul viz cu 0.
Initial in coada se gaseste varful de pornire: p=1, u=1, c[p]:=x, viz[x]:=1.
Cat timp mai sunt elemente in coada(“while p

  • pag. 1
  • pag. 2
  • pag. 3
  • pag. 4
  • pag. 5
  • pag. 6

Nota explicativa
Referatele si lucrarile oferite de Referate.ro au scop educativ si orientativ pentru cercetare academica.

Iti recomandam ca referatele pe care le downloadezi de pe site sa le utilizezi doar ca sursa de inspiratie sau ca resurse educationale pentru conceperea unui referat nou, propriu si original.

Referat.ro te invata cum sa faci o lucrare de nota 10!
Filmele zilei
Linkuri utile
Programeaza-te online la salonul favorit Descarca gratuit aplicatiile pentru iOS si Android Filmulete haioase Filme, poante si cele mai tari faze Jocuri Cele mai tari jocuri de pe net Referate scoala Resurse, lucrari, referate materiale pentru lucrari de nota 10 Bacalaureat 2019 Vezi subiectele examenului de Bacalaureat din 2019 Evaluare Nationala 2019 Ultimele informatii despre evaluare nationala
Toate imaginile, textele sau alte materiale prezentate pe site sunt proprietatea referat.ro fiind interzisa reproducerea integrala sau partiala a continutului acestui site pe alte siteuri sau in orice alta forma fara acordul scris al referat.ro. Va rugam sa consultati Termenii si conditiile de utilizare a site-ului. Informati-va despre Politica de confidentialitate. Daca aveti intrebari sau sugestii care pot ajuta la dezvoltarea site-ului va rugam sa ne scrieti la adresa webmaster@referat.ro.
Confidentialitatea ta este importanta pentru noi

Referat.ro utilizeaza fisiere de tip cookie pentru a personaliza si imbunatati experienta ta pe Website-ul nostru. Te informam ca ne-am actualizat politica de confidentialitate pentru a integra cele mai recente modificari privind protectia persoanelor fizice in ceea ce priveste prelucrarea datelor cu caracter personal. Inainte de a continua navigarea pe Website-ul nostru te rugam sa aloci timpul necesar pentru a citi si intelege continutul Politicii de Cookie. Prin continuarea navigarii pe Website-ul nostru confirmi acceptarea utilizarii fisierelor de tip cookie conform Politicii de Cookie. Nu uita totusi ca poti modifica in orice moment setarile acestor fisiere cookie urmarind instructiunile din Politica de Cookie.


Politica de Cookie
Am inteles