¿Cuál es la razón por la que [matemáticas] A ^ n [/ matemáticas] contiene el número de caminatas de longitud n?

Answer 1

Dividamos sus preguntas en 2 partes: ¿Qué método usa la prueba? (¿Qué es?) Y ¿Qué es la intuición?

Por absurdo que pueda parecer, déjenme responder la parte 2 primero, hará que la parte 1 sea mucho más fácil de ver:
– La intuición es la siguiente: Gráfico [matemática] G = (V, E) [/ matemática]. Dado un vértice [matemático] v \ en V [/ matemático], el número de caminos a ‘v’ desde todos los otros vértices [matemático] v_ {i} \ en V [/ matemático], de modo que [matemático] v_ {i } [/ math]! = [math] v [/ math], es igual a lo siguiente: [math] \ epsilon [/ math] * (camina ([math] v_ {1} [/ math]) + .. camina ([matemática] v_ {n}) [/ matemática]), donde [matemática] \ epsilon = 1 [/ matemática], si f [matemática] v_ {i} [/ matemática] es adyacente a [matemática] v [/ matemáticas]. En inglés, es la suma del número de caminatas de todos los vértices adyacentes a ‘v’. Si observa, la multiplicación de matrices hace exactamente esto. Dada una columna que se está multiplicando, la columna cumple el propósito de la condición [math] \ epsilon [/ math], y la fila se está multiplicando (de alguna [math] A ^ {k-1} [/ math]), sirve para que cada [matemática] a_ {ij} [/ matemática] represente el número de caminatas desde i -> j. Entonces, en esencia, según las leyes de la multiplicación de matrices, la matriz [matemáticas] A ^ {k} = A ^ {k – 1} [/ matemáticas] * [matemáticas] A [/ matemáticas] representa la ecuación anterior, para cada vértice [matemática] ‘v’ \ en V [/ matemática].

Respuesta 1 (Prueba) : La prueba usa principalmente Inducción . La razón de esto es que es una prueba que puede considerarse fácilmente de forma intuitiva como “construir los pasos” de un gráfico, nivel por nivel. Por definición, la matriz de adyacencia da el número de caminatas ‘1’ de longitud desde un vértice i -> j, ya que una caminata de una longitud es lo mismo que un borde [matemático] (ij) \ en E [/ matemático]. Suponga que, para todas [matemáticas] k j. Entonces, para [matemáticas] n = k [/ matemáticas], tenemos que [matemáticas] A ^ {k} = A ^ {k-1} [/ matemáticas] * [matemáticas] A [/ matemáticas], lo que nos da la longitud ‘k’ camina desde i -> j, para todas [matemáticas] v_ {i}, v_ {j} \ en V [/ matemáticas]. Sustituya [math] k = n [/ math], y obtendrá la longitud deseada de caminatas que busca.
QED

¡Espero que esto ayude!

Answer 2

El resultado es bastante fácil de probar por inducción. Considere [matemáticas] n = 1 [/ matemáticas]. Entonces [math] A_ {ij} [/ math] es uno si [math] i \ to j [/ math] y cero en caso contrario. Entonces, si sumamos toda la matriz, vemos que el total es el número de formas en que podemos ir desde cualquier nodo inicial a algún nodo final.

Ahora, suponga que el elemento [math] (i, j) [/ math] de [math] A ^ n [/ math] representa el número de formas de ir de [math] i [/ math] a [math] j [ / math] en exactamente [math] n [/ math] pasos. Una vez más, sumar toda la matriz nos indicaría el número total de caminatas de n pasos.

Luego, considere el elemento [math] (i, j) [/ math] de [math] A ^ {n + 1} [/ math]. Como [matemáticas] A ^ {n + 1} = A ^ n \ cdot A [/ matemáticas], vemos que:

[matemáticas] A ^ {n + 1} _ {ij} = \ sum_k A ^ n_ {ik} A_ {kj} [/ matemáticas]

Ahora, según la hipótesis inductiva, [matemáticas] A ^ n_ {ik} [/ matemáticas] es el número total de formas en que podemos pasar de [matemáticas] i [/ matemáticas] a [matemáticas] k [/ matemáticas] en [ matemática] n [/ matemática] pasos. Además, [math] A_ {kj} [/ math] es cero o uno para indicar una conexión de [math] k [/ math] a [math] j [/ math]. Entonces, el producto de estos dos términos es cero (si no puede pasar de [matemática] k [/ matemática] a [matemática] j [/ matemática]) o [matemática] A ^ n_ {ik} [/ matemática] (si puede ir de [matemáticas] k [/ matemáticas] a [matemáticas] j [/ matemáticas]). Entonces, sumando todo [matemática] k [/ matemática], vemos que [matemática] A ^ {n + 1} _ {ij} [/ matemática] representa el número de formas en que puede ir desde [matemática] i [/ matemática ] a [matemática] j [/ matemática] en [matemática] n + 1 [/ matemática] pasos. Y si sumamos toda la matriz [math] A ^ {n + 1} [/ math], obtenemos el número total de rutas desde cualquier punto de inicio a cualquier punto de finalización [math] n + 1 [/ math] .

Eso completa la prueba inductiva.

Answer 3

A representa los enlaces entre sus filas y columnas de modo que [matemáticas] A_ {xy} = 1 [/ matemáticas] si hay un enlace de [matemáticas] x [/ matemáticas] a [matemáticas] y [/ matemáticas].

[matemáticas] A ^ 2 = \ Sigma {A_ {xp} A_ {py}} [/ matemáticas]

tiene un enlace si hay una ap tal que hay una caminata desde [math] x [/ math] a p y de p a y. Cada término que agrega permite una caminata más larga y cada caminata agrega una al término correspondiente.

[matemáticas] A ^ 3 = \ Sigma {A_ {xp} A_ {pq} A_ {qy}} [/ matemáticas]

etc.

He utilizado la convención de que la suma pasa sobre todos los índices que aparecen dos veces.