Grafuri

Curs
7/10 (1 vot)
Domeniu: Calculatoare
Conține 1 fișier: doc
Pagini : 16 în total
Cuvinte : 3499
Mărime: 69.61KB (arhivat)
Cost: Gratis
Profesor îndrumător / Prezentat Profesorului: Talmaciu

Extras din document

GRAFURI. TRAVERSARI PE GRAFURI

Definitie:

Fie G = (V, E) o multime, în care V ¾ este o multime de noduri finita, ¦V¦ = n , si E ¾ o multime de arce, E = {(i, j), i, j Î N }. G se numeste graf, E £ V´V.

Avem: grafuri orientate în care (i, j) ¹ (j, i)

grafuri neorientate în care (i, j) Î E ® (j, i) Î E

Observatie: Un arbore este un caz particular de graf.

Definitii:

- i se numeste predecesor al lui j;

- j se numeste succesor al lui i;

- (i, j) ¾ este adiacent cu i si j;

- i, j ¾ adiacente;

- Ei = { k, (k, i) Î E} ¾ multimea de vecini la intrare;

- E'i = { j, (i, j) Î E} ¾ multimea de vecini la iesire;

- Ei È E'i ¾ multimea vecinilor.

grad_intrare(i) = in_degree(i) = ¦Ei¦

grad_ie_ire(i) = out_degree(i) = ¦ E'i¦

Pentru un graf neorientat (G - neorientat), Ei º E'i si degree(i)= ¦Ei¦.

Definitie

Se numeste drum orientat într-un graf de la x la y secventa de noduri D = (i1 = x, i2, ... , in = y),

(ik, ik+1) Î E, .

Drumul D este neorientat, daca (ik, ik+1) Î E sau (ik+1, ik) Î E

Definitie

Se numeste graf conex graful pentru care " doua noduri (x, y) Î V, $ D un drum de la x la y.

Un graf este complet daca fiecare nod este conectat cu oricare din celelalte noduri: E = V´V {(i, i), i Î V}

Definitie

Fie G = (V, E) un graf. Se numeste subgraf al grafului G, un graf G' = (V', E'), astfel încât V'Ì V, E' £ (V'´V') Ç E

Reprezentari

1) Matrice de adiacenta

Fie G = (V, E) ,¦V¦ = n. Se determina matricea de adiacenta

astfel:

Preview document

Grafuri - Pagina 1
Grafuri - Pagina 2
Grafuri - Pagina 3
Grafuri - Pagina 4
Grafuri - Pagina 5
Grafuri - Pagina 6
Grafuri - Pagina 7
Grafuri - Pagina 8
Grafuri - Pagina 9
Grafuri - Pagina 10
Grafuri - Pagina 11
Grafuri - Pagina 12
Grafuri - Pagina 13
Grafuri - Pagina 14
Grafuri - Pagina 15
Grafuri - Pagina 16

Conținut arhivă zip

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

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

Referat Ingineria Programarii - Arbori si Grafuri

Problema 1 Fie G un graf conex cu n varfuri. Fiecarui arc (i,j) i se pune in corespondenta un cost c[i][j]. Sa se listeze toti arborii acestui...

Arbori

1.1.ASPECTE GENERALE LEGATE DE TEMA LUCRARII . DOMENIUL (N CARE SE (NCADREAZA LUCRAREA (n momentul de fata prelucrarea informatiilor de orice...

Microsoft Excel

Dupa ce programul Excel a fost instalat, pentru a deschide programul Excel se vor efectua urmatorii pasi: - se face clic pe Start, iar pe ecran va...

Ai nevoie de altceva?