Matricea drumurilor

Fie G=(V, E) un graf neorientat, unde V are n elemente (n noduri) si E are m elemente (m muchii). Lui G i se asociaza matricea drum, numita matricea lanturilor, cu n linii si n coloane.

Astfel: drum = (drumi j) n x n cu:


1, daca [i,j]ÎE
drum[i,j]=
0, altfel


Matricea lanturilor ca si matricea de adiacenta, in cazul grafurilor neorientate , este o matrice simetrica (daca exista lant de la i la j exista si lant de la j la i).

Grafului de mai jos i se asociaza urmatoarea matrice a lanturilor:

0 1 1 1 1 0 0
1 0 1 1 1 0 0
1 1 0 1 1 0 0
1 1 1 0 1 0 0
1 1 1 1 0 0 0
0 0 0 0 0 0 1
0 0 0 0 0 1 0


Linia k (sau coloana k) a matricei lanturilor ne arata nodurile j pentru care exista lant de k la j ( si de la j la k). Spre exemplu, pentru nodul 3 .

0 1 1 1 1 0 0
1 0 1 1 1 0 0
1 1 0 1 1 0 0
1 1 1 0 1 0 0
1 1 1 1 0 0 0
0 0 0 0 0 0 1
0 0 0 0 0 1 0

Nu se poate ajunge de la nodul 3 la nodurile 6 sau 7.