El número de trazados en un gráfico de longitud fija sin repeatings

Question

Lo siento por mal inglés.

Considerar un gráfico $G$ con el % de la matriz de adyacencia $A$. Sé que el número de caminos de longitud $n$ es la suma de elementos $A^n$.

Pero ¿qué pasa si no podemos caminar a través de un vértice más de una veces?

Answer 1

Que $A\otimes B$ se define como el producto de matrices donde se extrajo la diagonal es decir: $$A\otimes B=(A-diag(A))\times(B-diag(B))$$ Let $A_1=A$ y $A_n=A\otimes A_{n-1}$.

El número de caminos de longitud n sin pasar por un vértice veces más uno es igual a la suma de elementos de $A_n$.