Multiplicación de la matriz de adyacencia de dos grafos

Question

Considere dos $N \times N$ matrices de adyacencia $A$ y $B$ pertenecientes a diferentes grafos (no ponderados y no dirigidos). ¿Qué hace su producto $AB$ ¿Representar? Sé que las potencias de la matriz de adyacencia dan el número de caminos entre dos vértices cualesquiera de longitud igual a la potencia. Pero tengo problemas para extender esta lógica al problema anterior

Answer 1

Celda $(i,j)$ en $AB$ contiene el número de paseos de $i$ a $j$ donde el primer paso es en $A$ pero el segundo paso está en $B$ . (Como si alguien cambiara el laberinto de $A$ a $B$ después del primer paso).

En términos de multiplicación de matrices $$(AB)_{ij}=a_{i1}b_{1j}+a_{i2}b_{2j}+\cdots+a_{in}b_{nj}$$ donde, por ejemplo, el término $a_{i1}b_{1j}$ es igual a $1$ si y sólo si podemos caminar desde el vértice $i$ al vértice $1$ en $A$ , entonces desde el vértice $1$ al vértice $j$ en $B$ .