Extras din curs
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
Conținut arhivă zip
- Grafuri.DOC
Alții au mai descărcat și
INTRODUCERE IN TEORIA GRAFURILOR Exista situatii când oameni ce lucreaza în diverse domenii ajung la reprezentarea unor cazuri concrete prin...
’’ 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...
Biblioteca de Sabloane Standard (STL) asigura o abstractizare standardizata a datelor prin intermediul containerelor si o abstractizare procedurala...
1. Clase derivate. Prin mostenire, atributele unei clase de baza sunt transmise unor clase derivate. Derivarea permite definirea unor clase noi,...
Clase pentru miniaplicatii Miniaplicatiile constituie extensii ale unei clase deja existente java.applet.Applet. Structura clasei unui applet...
Te-ar putea interesa și
INTRODUCERE IN TEORIA GRAFURILOR Exista situatii când oameni ce lucreaza în diverse domenii ajung la reprezentarea unor cazuri concrete prin...
’’ 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 NOTIUNI INTRODUCTIVE NOTIUNI DE BAZA DEFINITIE: Se numeste graf neorientat o pereche ordonata de multimi(X,U), X fiind o...
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...
1. Introducere Numeroase situatii din viata cotidiana pot fi modelate cu ajutorul teoriei grafurilor. Teoria grafurilor este o importanta...
1. Preliminarii 1.1. Algoritmi Toti algoritmii descrisi în cadrul acestei lucrari folosesc structuri de date de tip graf. Unele descrieri sînt...
Capitolul 1 INTRODUCERE Pentru noţiunile din acest paragraf am consultat Behzad, Chartrand, Foster, Croitoru, Olaru, Tomescu. Alte completări...
