Elemente de teoria grafurilor

Un graf G este o pereche de forma G=(X, A), unde X este o multime finita, iar A este o submultime a lui .

Elementele se numesc varfuri sau noduri ale grafului G iar perechile se numesc arce ale grafului.

Exemplu

Fie graful G=(X, A), unde si .

Un graf spoate fi reprezentat grafic astfel:

- se plaseaza in plan cele patru varfuri in pozitii distincte oarecare;

- pentru fiecare arc , punctele si se unesc printr-un segment orientat (printr-o sageata ce porneste din si ajunge in ).

Sa reprezentam grafic graful din exemplul considerat:

Matrici asociate unui graf

Fie graful G=(X, A), unde . Matricea , unde , daca , si daca , se numeste matrice atasata grafului G.

Cum aceasta matrice contine doar elementele 0 si 1, ea se numeste matrice booleeana.

Observatie

Daca se cunoaste matricea atasata grafului, atunci graful este cunoscut si poate fi rerezentat grafic.

Pentru exemplul considerat mai sus, matricea atasata este:

.

Arcelor unui graf G putem sa le asociem niste valori care vor indica valoarea arcului. Astfel de grafuri se numesc grafuri valuate.

In astfel de cazuri, matricea asociata va fi definita astfel: valoarea asociata arcului daca , si daca .

Exemplu

In acest caz, matricea asociata va fi:

Determinarea drumurilor de lungime minima intr-un graf

Fiind dat un graf valuat, dorim sa determinam drumurile de lungime minima ce pornesc din varful x1 si ajung in oricare din celelalte varfuri ale grafului.

Lungimea drumului va fi data de suma valorilor arcelor care alcatuiesc drumul respectiv.

Sa notam cu valoarea asociata arcului .

Pentru a determina drumurile de lungime minima ce pornesc din x1 vom alcatui un tabel ce va contine n+2 linii si coloane, unde n este numarul de noduri ale grafului, in felul urmator:

- pe prima linie vom lasa libere primele doua celule ale tabelului si pornind din cea de-a treia celula vom indica nodurile grafului;

- pe prima coloana vom lasa libere primele doua celule ale tabelului si pornind din cea de-a treia celula vom indica nodurile grafului;

- celula de pe linia 2, coloana 2, o vom imparti in doua si vom scrie respectiv , asa cum se observa in continuare: