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
No hay comentarios.:
Publicar un comentario