Elemente de Teoria Grafurilor

Proiect
8/10 (3 voturi)
Domeniu: Calculatoare
Conține 1 fișier: doc
Pagini : 72 în total
Cuvinte : 16792
Mărime: 693.33KB (arhivat)
Cost: 8 puncte
Profesor îndrumător / Prezentat Profesorului: Anastasoaie Vasile
proeict pentru ora de informatica

Cuprins

Cuprins

CAP.I INTRODUCERE IN TEORIA GRAFURILOR 1

CAP.II DETERMINAREA CONECTIVITĂŢII UNUI GRAF 5

2.1 Matrice asociată unui graf 5

2.2 Algoritmul lui Roy-Warshall 7

2.3 Parcurgerea grafurilor 10

2.3.1 Parcurgerea grafurilor în adâncime (depth-first search) 10

2.3.2 Parcurgerea grafurilor prin cuprindere (breadth-first search) 15

2.3.3 Aplicaţii in conexitate ale parcurgerii grafurilor 17

Cap.III K-CONEXITATE ŞI -CONEXITATE 27

3.1 Noţiuni intoductive 27

3.2 Proprietăţi 28

3.3 Variaţiuni grafice ale teoremei lui Menger 33

3.4 Caracterizarea grafurilor 2-conexe şi 3-conexe 38

Cap.IV GRAFURI K-CONEXE MINIMALE 46

Cap.V TENDINŢE NOI ÎN LUMEA GRAFURILOR ŞI APLICAŢII ALE LOR ŞI, ÎN PARTICULAR ALE CONEXITĂŢII, ÎN LUMEA REALĂ 50

ANEXA 1 54

ANEXA 2 57

ANEXA 3 59

ANEXA 4 61

ANEXA 5 62

BIBLIOGRAFIE 70

CUPRINS 71

Extras din document

INTRODUCERE IN TEORIA GRAFURILOR

Exista situatii când oameni ce lucreaza în diverse domenii ajung la reprezentarea unor cazuri concrete prin desenarea unor puncte, cu o anumita semnificatie, unite prin segmente si care simbolizeaza o anumita relatie ce exista între acele puncte. Punctele au fost denumite noduri, iar segmentele au fost denumite arce, iar o astfel de reprezentare se numeste graf. Am pomenit mai sus de ramuri diverse unde apare notiunea de graf. Voi da cateva exemple:

- in chimie: reprezentarea unei molecule este un graf (vezi fig.1.1)

fig.1.1-Reprezentarea grafica a câtorva molecule

- in biologie, de exemplu repreyentarea plana a moleculei de ADN poate fi considerata un graf infinit (de fapt are o lungime finita,dar foarte mare) ;

- reteaua de drumuri dintr-o tara, spre exemplu, impreuna cu localitatile pe care le unesc formeaza un graf;

- un circuit electric este de fapt un graf (aceasta reprezentare l-a ajutat pe Kirkhoff în experimentele sale fizice);

- calculatoarele aflate legate într-o retea formeaza de asemenea un graf;

De fapt notiunea de graf îsi are originea în lucrarile lui Euler care

în 1976 studia celebra problema a celor 7 poduri din Königsberg reprezentata in

Fig.1.2 Problema podurilor din Königsberg

Problema cere aflarea unui drum ce parcurge toate podurile o singura data si se ajunge în punctul din care s-a plecat. Euler a demonstrat ca problema nu are solutie. Astazi teoria grafurilor îsi gaseste utilitatea în multe ramuri ale matematicii, economiei etc. În continuare voi prezenta câteva notiuni teoretice de baza despre grafuri.

Definitia 1.1

Se numeste graf o pereche G=( X, U ) formata dintr-o multime X de elemente numite vârfuri si dintr-o familie U de perechi de vârfuri ale carei elemente se numesc muchii. În continuare vom presupune ca graful G este finit, adica multimea X={x1,x2,…,xn} este finita si familia U=(u1,u2,…,um) a muchiilor este un sir finit. Daca sirul U al muchiilor este o multime de perechi, adica UÍX´X graful se numeste graf orientat. (figura 1.4),iar muchiile le vom numi in acest caz arce. Daca un graf nu are bucle si nu contine doua muchii egale (în sensul teoriei multimilor), iar familia U este o submultime a lui P2(X) (multimea partilor cu doua elemente ale lui X) graful se numeste graf neorientat.(figura 1.3)

Preview document

Elemente de Teoria Grafurilor - Pagina 1
Elemente de Teoria Grafurilor - Pagina 2
Elemente de Teoria Grafurilor - Pagina 3
Elemente de Teoria Grafurilor - Pagina 4
Elemente de Teoria Grafurilor - Pagina 5
Elemente de Teoria Grafurilor - Pagina 6
Elemente de Teoria Grafurilor - Pagina 7
Elemente de Teoria Grafurilor - Pagina 8
Elemente de Teoria Grafurilor - Pagina 9
Elemente de Teoria Grafurilor - Pagina 10
Elemente de Teoria Grafurilor - Pagina 11
Elemente de Teoria Grafurilor - Pagina 12
Elemente de Teoria Grafurilor - Pagina 13
Elemente de Teoria Grafurilor - Pagina 14
Elemente de Teoria Grafurilor - Pagina 15
Elemente de Teoria Grafurilor - Pagina 16
Elemente de Teoria Grafurilor - Pagina 17
Elemente de Teoria Grafurilor - Pagina 18
Elemente de Teoria Grafurilor - Pagina 19
Elemente de Teoria Grafurilor - Pagina 20
Elemente de Teoria Grafurilor - Pagina 21
Elemente de Teoria Grafurilor - Pagina 22
Elemente de Teoria Grafurilor - Pagina 23
Elemente de Teoria Grafurilor - Pagina 24
Elemente de Teoria Grafurilor - Pagina 25
Elemente de Teoria Grafurilor - Pagina 26
Elemente de Teoria Grafurilor - Pagina 27
Elemente de Teoria Grafurilor - Pagina 28
Elemente de Teoria Grafurilor - Pagina 29
Elemente de Teoria Grafurilor - Pagina 30
Elemente de Teoria Grafurilor - Pagina 31
Elemente de Teoria Grafurilor - Pagina 32
Elemente de Teoria Grafurilor - Pagina 33
Elemente de Teoria Grafurilor - Pagina 34
Elemente de Teoria Grafurilor - Pagina 35
Elemente de Teoria Grafurilor - Pagina 36
Elemente de Teoria Grafurilor - Pagina 37
Elemente de Teoria Grafurilor - Pagina 38
Elemente de Teoria Grafurilor - Pagina 39
Elemente de Teoria Grafurilor - Pagina 40
Elemente de Teoria Grafurilor - Pagina 41
Elemente de Teoria Grafurilor - Pagina 42
Elemente de Teoria Grafurilor - Pagina 43
Elemente de Teoria Grafurilor - Pagina 44
Elemente de Teoria Grafurilor - Pagina 45
Elemente de Teoria Grafurilor - Pagina 46
Elemente de Teoria Grafurilor - Pagina 47
Elemente de Teoria Grafurilor - Pagina 48
Elemente de Teoria Grafurilor - Pagina 49
Elemente de Teoria Grafurilor - Pagina 50
Elemente de Teoria Grafurilor - Pagina 51
Elemente de Teoria Grafurilor - Pagina 52
Elemente de Teoria Grafurilor - Pagina 53
Elemente de Teoria Grafurilor - Pagina 54
Elemente de Teoria Grafurilor - Pagina 55
Elemente de Teoria Grafurilor - Pagina 56
Elemente de Teoria Grafurilor - Pagina 57
Elemente de Teoria Grafurilor - Pagina 58
Elemente de Teoria Grafurilor - Pagina 59
Elemente de Teoria Grafurilor - Pagina 60
Elemente de Teoria Grafurilor - Pagina 61
Elemente de Teoria Grafurilor - Pagina 62
Elemente de Teoria Grafurilor - Pagina 63
Elemente de Teoria Grafurilor - Pagina 64
Elemente de Teoria Grafurilor - Pagina 65
Elemente de Teoria Grafurilor - Pagina 66
Elemente de Teoria Grafurilor - Pagina 67
Elemente de Teoria Grafurilor - Pagina 68
Elemente de Teoria Grafurilor - Pagina 69
Elemente de Teoria Grafurilor - Pagina 70
Elemente de Teoria Grafurilor - Pagina 71
Elemente de Teoria Grafurilor - Pagina 72

Conținut arhivă zip

  • Elemente de Teoria Grafurilor.doc

Alții au mai descărcat și

Virusi Informatici

CAPITOLUL 1 VIRUSI INFORMATICI 1. Definitia virusilor informatici 2. Istoria virusilor. 3. Clasificarea virusilor. 4. Modul de infectare. 5....

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...

Grafuri Neorientate

GRAFURI NEORIENTATE NOTIUNI INTRODUCTIVE NOTIUNI DE BAZA DEFINITIE: Se numeste graf neorientat o pereche ordonata de multimi(X,U), X fiind o...

Arbori Partiali de Cost Minim

I. Arbori Fie G un graf orientat. G este un arbore cu radacina r, daca exista in G un varf r din care oricare alt varf poate fi ajuns printr-un...

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...

Algoritmul lui Dijkstra

#include<iostream.h> class dijkstra { private: int graph[15][15]; int set[15],predecessor[15],mark[15],pathestimate[15]; int source; int...

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)...

Ai nevoie de altceva?