Conexión en grafos con recorridos de longitud (menor o) igual a k

Se muestran las conexiones en k pasos de un grafo de n puntos, n entre 3 y 18. Si se activa la casilla "Solo k pasos" se consideran solo los recorridos de k pasos, de lo contrario también los que tengan menor número de pasos.

Se pueden poner/quitar arcos del grafo modificando la parte blanca de la matriz de adyacencia en la hoja de cálculo. Se modifican así el grafo y las matrices A y A^k ó A + A² + ... + A^k.

La solución para la conexión completa con n = 10 y k = 2, con un máximo de tres arcos por nodo, se debe a Eduardo, en el grupo de noticias es.ciencia.matematicas.

Una cota máxima para el número n de nodos conectables con k pasos, si cada uno puede tener hasta m conexiones directas es

n = 1 + k((k - 1)^m - 1)/(k - 2)

Los puntos se distribuyen como el centro y los vértices de un polígono regular de n-1 lados, con la casilla "Nodo central" activada, o como los vértices de un polígono regular de n lados. El orden es: primero el nodo central, si es el caso; a continuación los demás en sentido contrario a las agujas del reloj, empezando por el superior.

Ignacio Larrosa Cañestro (Grupo XeoDin), 13 Diciembre 2013, Creado con GeoGebra