operaciones con matrices para enumerar todos los caminos a través de n-partite gráfico

Question

tengo una n-partite gráfico (no dirigida), dado como una matriz de adyacencia, por ejemplo éste aquí:

 
    a b c d 
a 0 1 1 0 
b 0 0 0 1 
c 0 0 0 1 
d 0 0 0 0 

me gustaría saber si hay un conjunto de operaciones matriciales que puedo aplicar a esta matriz, que dará como resultado una matriz que "enumera" todas las rutas (de longitud n, es decir, a través de todas las particiones) en este gráfico. Para el ejemplo anterior, hay caminos a-> b-> d y a-> c-> d. Por lo tanto, me gustaría obtener la siguiente matriz como resultado:

 
a b c d 
1 1 0 1 
1 0 1 1 

La primera ruta de acceso contiene los nodos A, B, D y el segundo nodos A, c, d. Si es necesario, la matriz de resultados puede tener algunas líneas de 0, como aquí:

 
a b c d 
1 1 0 1 
0 0 0 0 
1 0 1 1 
0 0 0 0 

¡Gracias!

P.S. He analizado algoritmos para calcular el cierre transitivo, pero estos generalmente solo indican si hay una ruta entre dos nodos, y no directamente qué nodos están en esa ruta.

Answer 1

Una cosa que puedes hacer es calcular la enésima potencia de tu matriz A. El resultado te dirá cuántas rutas hay de longitud n desde un vértice a otro.

Ahora, si está interesado en conocer todos los vértices a lo largo de la ruta, no creo que el uso de operaciones puramente matriciales sea el camino a seguir. Teniendo en cuenta que tiene un gráfico n-partite, establecería una estructura de datos de la siguiente manera: (Tenga en cuenta que los costos de espacio serán caros para todos los valores, excepto para los pequeños)

Cada columna tendrá una entrada de cada uno de los nodos en nuestro gráfico. La n-ésima columna contendrá 1 en caso de que este nodo sea alcanzable en la enésima iteración desde nuestro vértice de inicio designado o conjunto de inicio, y cero en caso contrario. Cada entrada de columna también contendrá una lista de punteros hacia atrás a los vértices en la columna n-1 que condujo a este vértice en la enésima columna. (Esto es como el algoritmo de Viterbi, excepto que tenemos que mantener una lista de contraseñas para cada entrada en lugar de solo una.) La complejidad de hacer esto es (m^2) * n, donde m es el número de vértices en el gráfico, y n es la longitud de la ruta deseada.

Estoy un poco confundido por su matriz superior: con un gráfico sin corregir, esperaría que la matriz de adyacencia fuera simétrica.

Answer 2

No, no existe una forma de matriz pura para generar todas las rutas. Por favor, use algoritmos combinatorios puros.

'Una cosa que puedes hacer es calcular la enésima potencia de tu matriz A. El resultado te dirá cuántas rutas hay de longitud n desde un vértice a otro'.

El poder de matriax genera paseos, no caminos.