Instituto Tecnológico de Querétaro
Campus Centro
Matemáticas Discretas
2.2 Representación de los Grafos
Considere el grafo siguiente "G": y suponga que los nodos se mantienen en memoria en un array DATOS tal como sigue:
DATOS: X, Y, Z, W
Para hallar la matriz de adyacencia A del grafo "G", tenemos que tomar en cuenta que los nodos están normalmente ordenados de acuerdo con la forma en que aparecen en memoria; es decir, asumimos que u1 = X, u2 = Y, u3 = Z, y u4 = W, la matriz de adyacencia A de G sería la
de alado.
Aquí ai j = 1 si hay una arista ui a uj; si no aij = 0. Así entonces para hallar la matriz de camino P de G mediante las potencias de la matriz de adyacencia
Por lo tanto la matriz de caminos P se obtiene ahora haciendo pij = 1 siempre que haya una entrada positiva en la matriz B4 .
La matriz de caminos muestra que no hay camino de u1 a u2 de hecho, no hay camino de ningún nodo a u1 por tanto, G no es fuertemente conexo
BIBLIOGRAFIA