Número de caminos. Potencias de matrices
Esta actividad pertenece al libro de GeoGebra Redes y Grafos.
Imagina un árbol en el que el tronco se divide en dos ramas, cada rama en otras dos, y así sucesivamente. El número de ramas, cada vez más alejadas del tronco, va creciendo de forma exponencial. El número de cada tipo de ramas es fácil de calcular, ya que ha de ser una potencia de dos: 20 (un tronco), 21 (dos ramas principales), 22 (cuatro ramas secundarias), 23 (ocho ramas terciarias), etc.
Ya hemos visto que la estructura de un árbol es un caso particular de grafo. ¿Existe algún modo de contar rápidamente el número de caminos entre dos nodos de un grafo que no tenga estructura de árbol? Pues sí, existe, gracias a la matriz de adyacencia.
Del mismo modo que el número de ramas de un árbol que se bifurca sigue una sucesión de potencias de 2, el número de caminos de un grafo cualquiera sigue una sucesión de potencias de su matriz de adyacencia M: M0, M1, M2, M3, etc.
En la siguiente construcción partimos del grafo correspondiente a los puentes de Königsberg y de su matriz de adyacencia M. Al multiplicar sucesivamente M por sí misma (es decir, al calcular las sucesivas potencias), obtenemos el número de caminos para ir de un nodo a otro.
Por ejemplo, el primer elemento de la siguiente matriz, que es M2, indica que hay 5 caminos diferentes para salir de A, cruzar 2 puentes (que pueden ser el mismo) y volver a A. Observa, en la aplicación, que incluso se cumple para el caso de exponente 0.
Autor de la actividad y construcción GeoGebra: Rafael Losada.