¿Cuál es el $2N-$ potencia de la matriz de adyacencia $A$ de un árbol dirigido?

Question

Supongamos que tenemos un árbol dirigido con raíz $v$ y que $A$ sea su matriz de adyacencia. Supongamos que el número de vértices es $N$ . Calcule $A^{2N}$ .

Sé que el $n-$ potencia de una matriz de adyacencia da el número de de longitud n entre dos nodos. Ahora bien, como estamos hablando de un árbol, no podemos permitir ciclos. ¿Es posible construir un árbol con un $2N$ ¿un largo camino? Lo intenté, pero no pude encontrarlo, por lo tanto todo $A^{2N}$ matrices que pude calcular estaban formadas por todas las entradas cero.

Lo que pregunto es: ¿por qué el ejercicio pide $A^{2N}$ y no simplemente para $A^{N}$ que ya está formado por todas las entradas cero? ¿Qué significa $2$ ¿Quieres decir aquí?

Answer 1

Sea $A$ sea la matriz de adyacencia de un dígrafo $T$ . Obsérvese que para cualquier número entero $\ell$ la matriz $A^{\ell}$ da el número de paseos dirigidos entre dos vértices cualesquiera; es decir, para dos vértices cualesquiera $u$ y $v$ el número entero $A^{\ell}_{uv}$ es el número de paseos dirigidos entre $u$ y $v$ . Si $T$ es acíclico [por acíclico también entendemos que no tiene ciclos de longitud 1 ó 2, es decir, no tiene arcos que sean bucles ni pares de vértices $u$ y $v$ s.t. ambos $(u,v)$ y $(v,u)$ son arcos en $T$ ] entonces esto implica que cualquier camino dirigido entre dos vértices debe ser un trayectoria dirigida o dipath para abreviar.

Por lo tanto $\ell$ es la longitud [por longitud me refiero al número de aristas], de un dipath más largo en cualquier grafo acíclico $T$ [que incluye cualquier árbol en el que cada arista esté dirigida exactamente en una dirección -puede estar rooteado pero no tiene por qué estarlo] y sea $A$ sea la matriz de adyacencia de $T$ . Entonces $A^{\ell+1}_{uv}$ es 0 para cada vértice $u$ y $v$ sur $T$ y así $A^{\ell+1}$ es la matriz 0, y de forma similar, también lo es $A^k$ para cada $k \ge \ell+1$ . La longitud del dipath en un árbol en $N$ vértices, es decir, cualquier grafo en $N$ o menos vértices--no es más que $N-1$ . Así que $A^k$ es 0 para todo $k \ge \ell$ para un gráfico de este tipo $T$ .