Elemente matematice atasate grafului - Matrice atasate grafurilor

Elemente matematice atasate grafului

Matrice atasate grafurilor

Pentru rezolvarea unor grafuri de dimensiuni mari si a unor probleme practice, se asociaza grafului o serie de matrice ce usureaza studiul acestora.Cu ajut matricelor atasate grafurilor se pot det: succesiunile optime a unor procese de productie, legatutile ce se stabilesc intre-un proces tehnologic, modul de transmitere a unei informatii direct sau indirect, rute strategice dpdv ec.

Matricea arcelor (matricea conexiunilor directe)

Fie G=(X,U) un graf orientat cu X=.Grafului orientat G i se asociaza o matrice booleana patratica

A aij ), i = 1,..., n, j = 1,...n numita matricea arcelor (conexiunilor directe) cu urmat elem:

Aij=

Obsevatii

- Daca in matricea A se pune in locul valorii 1, valoarea arcului, se va obtine matricea capacitatilor arcului;

- Daca pe diagonala principala nu exista elernente egale cu 1, atunci graful dat nu are bucle;

- In linia i(1<=i<=n) a matricei A sunt marcate cu 1 arcele incidente spre exterior in nodul xi;

- In coloana j(l<=j<=n) sunt marcate cu 1 arcele incidente spre interior in nodul xj;

- In cazul unei bucle (xi,xj), elementul de pe diagonal a aij este egal cu 1;

- Gradul de intrare d¯(xj) ptr nodul xj este dat de relatia d¯(xj)=Σaij ;

- Gradul de iesire d+(xj) pentru nodul xj este dat de relatia d+(xj)=Σaij

Exemplu

Unui graf orientat G cu 4 noduri x1,x2,x3,x4 si eu arcele (x1,x2),(x1,x3), (x2,x2),(x2,x3),(x2,x4),(x3,x4) i se asociaza matricea booleana: A(0 1 1 0// 0 1 1 1 // 0 0 0 1 // 1 0 0 0)

Avand in vedere matricea A avem urmat propr:

P1. Daca un graf este antisimetric, atunci in matricea asociata A: aij*aji = 0 Oricare) xi,xj є X,i nu=j

P2. Matricea asociata unui graf partial G* se obt din matricea asociata grafului G prin inlocuirea cu 0 a elem asociate arcelor suprimate.

P3. Matricea asociata unui subgraf partial H se obt prin suprimarea din matricea asociata grafului G a liniilor si coloanelor corespunz nodurilor exc1use. Matricea unui subgraf este o matrice patratica extrasa din matricea grafului G.

Daca graful G = (X,U^)este neorientat muchiile sale se orienteaza in ambele sensuri: |xi,xj|<->(xi,xj) si (xj,xi)

si elem matricei A=(aij) asociata grafului G se definese:

aij

In cazul unui graf neorientat, matricea asociata A este o matrice simetrica.

Ptr un graf cu patru noduri x1,x2,x3,x4 cu muchiile (x1,x2), (x1,x3),(x2,x3),(x2,x4),(x3,x4) matricea asociata A este:

A( . Matricei booleene patratice A i se asociaza un graf orientat

cu arcele (xi, xj) pentru toatele elementete aij=1.

Matricea drumurilor (matricea conexiunilor totale)

Fie G = (X ,U) un graf orientat cu X = si A matricea arcelor.

In matricea A avem:

-pe linia i,1<=i<=n sunt marcate cu 1 drumurile de lungime 1 care pleaca din nodul xi;

in coloana j,1<= j<=n sunt marcate cu 1 drumurile de lungime 1 care converg in nodul xj;

Matricea A este matricea booleana a drumurilor de lungime 1.

Daca un elem aij la (k) = 1 exista un drum de lungime k de la xi la xj.Astfel, in matricea booleana A la (k):

-elem de pe linia i,1<= i<= n arata drumurile de lungime k de la nodul xj la nodurile in coloanele carora apare 1 pe aceasta linie;

-elem de pe coloana j,l <= j<=n arata drumurile de lungime k de la nodurile pe a carora linie apare 1 in aceasta coloana la nodul xj;

Daca ridicam la puteri succesive matricea A prin operatiile obisnuite de inmultire si adunare a numerelor naturale reale se obtine numarul drumurilor de o anumita lungime.

Daca A este matricea asociata unui graf neorientat G=(X,E),puterile succesive A la (k) ofera informatii despre existenta si nr lanturilor si circuitelor de lungime egala cu puterea matricei.Aici matr A este simetrica.