Grafuri Neorientate

Referat
7/10 (1 vot)
Domeniu: Calculatoare
Conține 1 fișier: doc
Pagini : 21 în total
Cuvinte : 3381
Mărime: 24.71KB (arhivat)
Cost: 5 puncte
Profesor îndrumător / Prezentat Profesorului: Iulian Amariei
grafuri neorientate

Cuprins

GRAFURI NEORIENTATE – NO}IUNI DE BAZ| 1

GRADE {I {IRURI GRAFICE 3

CLASE SPECIALE DE GRAFURI 4

REPREZENTAREA GRAFURILOR NEORIENTATE 6

PARCURGEREA GRAFURILOR NEORIENTATE 9

METODA BF 10

METODA DF 13

PARCURGERE BF RECURSIV 16

PARCURGERE DF RECURSIV 18

BIBLIOGRAFIE 19

CUPRINS 20

Extras din document

GRAFURI NEORIENTATE

NOTIUNI INTRODUCTIVE

NOTIUNI DE BAZA

DEFINITIE: Se numeste graf neorientat o pereche ordonata de multimi(X,U), X fiind o multime finita si nevida de elemente numite noduri sau varfuri, iar U o multime de perechi neordonate (submultimi cu doua elemente) din X, numite muchii.

Vom nota cu G=(X,U) un graf neorientat. Multimea X se numeste multimea nodurilor sau varfurilor graficului G, iar U, multimea muchiilor.

O muchie uÎU este deci o submultime {x,y} de varfuri distincte din X si se noteaza u=[x,y]. Vom spune despre varfurile x si y ca sunt adiacente in G iar despre u si x ca sunt incidente la fel ca si u si y. Se mai spune ca x si y sunt extremitatile muchiei u.

Daca u1 si u2 sunt doua muchii care au o extremitate comuna, ele vor fi numite de asemenea incidente.

Un graf poate fi reprezentat cu ajutorul unei figuri plane in care fiecarui varf i se asociaza un punct si fiecarei muchii [x,y], o linie curba care uneste in plan punctele ce corespund varfurilor x si y.

Inca un aspect interesant ar fi dezvoltarea naturala a teoriei grafurilor; de indata ce definitia unui graf a fost prezentata, notiunile si rezultatele par sa se nasca singure si in mod spontan, astfel incat cel care studiaza acest domeniu pare sa aiba impresia ca ar fi putut fi chiar el insusi creatorul acestui domeniu.

Exemplu: Fie G=(X,U) astfel incat X={1,2,3,4,5,6,7,8,9,10}, iar U={[1,5],[3,7],[4,6],[9,8],[10,2],[1,2],[9,4],[1,10],[6,8]}.

DEFINITIE: Un graf partial al grafului G=(X,U) este un graf G1=(X,V) astfel incat VÍU, adica G1 are aceeasi multime de varfuri ca G iar multimae de muchii V este chiar U sau o submultime a acesteia.

Exemplu: Pentru graficul G de mai sus, G1 = (X,V), unde V={[1,5],[2,10],[6,4]} este un graf partial.

Fig. 2

DEFINITIE: Un subgraf al unui graf G=(X,U) este un graf H=(Y,U) astfel incat YÌX iar V contine toate muchiile din U care au ambele extremitati in Y. Vom spune ca subgraful H este indus de multimea de varfuri Y.

Exemplu: Pentru graful din figura 1, daca Y={1,2,3,7,10} si V={[1,2],[1,10],[2,10],[3,7]}, atunci H=(Y,V) este subgraf al grafului G, subgraf reprezentat in figura 3.

Preview document

Grafuri Neorientate - Pagina 1
Grafuri Neorientate - Pagina 2
Grafuri Neorientate - Pagina 3
Grafuri Neorientate - Pagina 4
Grafuri Neorientate - Pagina 5
Grafuri Neorientate - Pagina 6
Grafuri Neorientate - Pagina 7
Grafuri Neorientate - Pagina 8
Grafuri Neorientate - Pagina 9
Grafuri Neorientate - Pagina 10
Grafuri Neorientate - Pagina 11
Grafuri Neorientate - Pagina 12
Grafuri Neorientate - Pagina 13
Grafuri Neorientate - Pagina 14
Grafuri Neorientate - Pagina 15
Grafuri Neorientate - Pagina 16
Grafuri Neorientate - Pagina 17
Grafuri Neorientate - Pagina 18
Grafuri Neorientate - Pagina 19
Grafuri Neorientate - Pagina 20
Grafuri Neorientate - Pagina 21

Conținut arhivă zip

  • Grafuri Neorientate.DOC

Alții au mai descărcat și

Elemente de Teoria Grafurilor

INTRODUCERE IN TEORIA GRAFURILOR Exista situatii când oameni ce lucreaza în diverse domenii ajung la reprezentarea unor cazuri concrete prin...

Turbo Pascal - Metoda Backtracking - Tehnica Greedy

Aparitia limbajului Pascal este un raspuns la criza care a aparut in domeniul programarii calculatoarelor , la sfarsitul anilor ’60 . Limitarile...

Grafuri Neorientate - Euleriene

’’ Ideile, si daca sunt abstracte si daca nu, ca sa le poti manui, trebuie sa le ai. Calculatorul, ca sa-si faca treaba, trebuie sa inteleaga...

Parcurgerea Grafurilor Neorientate

Obiective Notiuni teoretice despre parcurgeri (semnificatie, mod de realizare, scop); Metode de parcurgere; Parcurgerea în “latime” (prezentarea...

Drumuri de Cost Minim și Maxim

Am ales aceasta tema in scopul de a va arata ca si in informatica exista distante (adica ”drumuri”) atat minime cat si maxime intre elementele unui...

Algoritmica Grafurilor

Curs 1 1.Notatii.Definitii Multiset – S multime finita, S!=VID R=(S,r) r:S->N³0, r=functie multiplicitate r:S->{0,1} => def partilor lui S (R)...

Grafuri

SCURT ISTORIC AL TEORIEI GRAFURILOR Originile teoriei grafurilor se gãsesc în rezolvarea unor probleme de jocuri si amuzamente matematice,care au...

Grafuri Orientate

Un graf orientat G este format dintr-o pereche ordonata de multimi G=(X,U). ca si in cazul grafurilor neorientate, X este multimea varfurilor sau...

Ai nevoie de altceva?