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

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

AutoCad

APERTURE - controleazã mãrimea cursorului selector, caracteristic modului object snap. ARC - traseazã un arc de cerc de orice dimensiune. A -...

Biblioteca de Șabloane Standard

Biblioteca de Sabloane Standard (STL) asigura o abstractizare standardizata a datelor prin intermediul containerelor si o abstractizare procedurala...

Clase Derivate

1. Clase derivate. Prin mostenire, atributele unei clase de baza sunt transmise unor clase derivate. Derivarea permite definirea unor clase noi,...

Clase în Java

Clase pentru miniaplicatii Miniaplicatiile constituie extensii ale unei clase deja existente java.applet.Applet. Structura clasei unui applet...

Clase

1. Programare procedurala –Programare orientata pe obiecte. Limbajul C, ca si Pascal, utilizeaza modelul programarii structurate procedurale, care...

Comunicații internet

2.1. Stilurile caracterelor {n sfirsit pagina dvs. contine ceva, chiar daca este vorba numai de un nume. Vom analiza in continuare elementele de...

Te-ar putea interesa ș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...

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

Grafuri Neorientate

Grafuri neorientate Definiţie. Se numeşte graf neorientat o pereche ordonată de mulţimi (X, U), X fiind o mulţime finită şi nevidă de elemente...

Grafuri Celebre

1. Introducere Numeroase situatii din viata cotidiana pot fi modelate cu ajutorul teoriei grafurilor. Teoria grafurilor este o importanta...

Manual Grafuri

1. Preliminarii 1.1. Algoritmi Toti algoritmii descrisi în cadrul acestei lucrari folosesc structuri de date de tip graf. Unele descrieri sînt...

Algoritmica grafurilor

Capitolul 1 INTRODUCERE Pentru noţiunile din acest paragraf am consultat Behzad, Chartrand, Foster, Croitoru, Olaru, Tomescu. Alte completări...

Ai nevoie de altceva?