Ciclos en grafos con matrices

Respecto a su duda de cómo verificar si se forma un ciclo en el grafo G al añadir la arista (i,j) revisen el siguiente vídeo.



como pueden ver, si calcula M^2+M^3+ ...+M^(n-1) la entrada (i,j) de la suma de estas matrices nos dará el número de caminos existentes del vértice i al vértice j, si es diferente de cero, entonces al añadir la arista (i,j) se formará un ciclo.