Determina el número de paseos diferentes de longitud 4.

Question

Dejemos que $K_3$ denota el gráfico completo que tiene 3 vértices. Determina el número de paseos diferentes de longitud 4 que hay en $K_3$ de v a v.

Así que utilicé una regla de inducción para encontrar el número máximo de aristas (obtuve 6) y dibujé el gráfico. Teniendo en cuenta que se trata de paseos, los paseos inversos y superpuestos cuentan.

Sé que puedo hacer esto de la manera larga, y pasar por cada paseo individualmente, pero me preguntaba si había tal vez una manera más simple y mucho más rápida, dado que este es un ejemplo bastante pequeño y que las preguntas como estas pueden usar números ridículamente grandes.

Answer 1

Se puede utilizar el siguiente resultado interesante . Sea $A$ denota la matriz de adyacencia de tu grafo. Entonces, la $(i,j)$ entrada de la matriz $A^n$ denotará el número de paseos de longitud $n$ del vértice $i$ al vértice $j$ .

Answer 2

Déjame probar esto.

Considere $K_n$ , $k$ pasos.

El número total de paseos comienza en $v_1 = (n-1)^k$ .

Dejemos que $N_i$ denota el número de paseos que terminan en $v_i$ . Claramente $\{N_1,...,N_n\}=\{N_1,N_2\}$ . Sea $N_1=A_k$ , $N_2=B_k$ .

Se puede ver que $A_k=(n-1) B_{k-1}$ y $B_k=(n-2) B_{k-1}+A_{k-1}=(n-2) B_{k-1}+(n-1)B_{k-2}$ .

Si no se permiten los bucles (y se pueden utilizar vértices y aristas para más de una vez), se tiene

$0$ pasos: $1$ caminar

$1$ pasos: $0$ caminar

$2$ pasos: $2$ camina

$3$ pasos: $2$ camina

$4$ pasos: $4$ camina.

A continuación, puede añadir algunos bucles a la secuencia de aristas para convertirla en una $4$ -Caminar.

Esto le da $1+0+2\times \binom{5}{2}+2 \times \binom{4+1}{4}+4$ . Entonces el número total de paseos es $1+0+10*2+2*4+4=33$