¿Hay alguna operación de matriz que pueda realizar (por ejemplo, multiplicación, cuadratura) en la matriz de un gráfico que corresponda a aspectos de la teoría de gráficos?

Answer 1

Si asociamos la matriz de adyacencia [matemática] A [/ matemática] con una gráfica [matemática] G [/ matemática], entonces la matriz [matemática] A ^ n [/ matemática] codifica el número de pasos de longitud [matemática] n [/ math] en el gráfico. Por ejemplo, para encontrar el número de pasos de longitud [matemática] 3 [/ matemática] desde el vértice [matemática] 2 [/ matemática] al vértice [matemática] 4 [/ matemática] en [matemática] G [/ matemática], usted lea la entrada en la segunda fila y cuarta columna de la matriz [matemática] A ^ 3 [/ matemática].

Relacionado con esto, la matriz [matemáticas] (xI-A) ^ {- 1} [/ matemáticas] es extremadamente interesante. La entrada [math] ij ^ \ textrm {th} [/ math] de esta matriz es una función racional, cuya expansión de la serie de potencia formal [math] w_0 + w_1x + w_2x ^ 2 + w_3x ^ 3 + \ cdots [/ math] proporciona el número de caminatas de cualquier longitud entre vértices [matemática] i [/ matemática] y [matemática] j [/ matemática] en [matemática] G [/ matemática]. Aquí, [math] w_k [/ math] es el número requerido de caminatas de longitud [math] k [/ math] para cualquier [math] k [/ math].

Por supuesto, el determinante de [matemáticas] xI-A [/ matemáticas] es el polinomio característico de la gráfica. Los coeficientes de este polinomio están relacionados con las estructuras del gráfico, llamadas figuras elementales y figuras básicas, por el teorema del coeficiente de Sachs. Las raíces de este polinomio son los valores propios de la gráfica. Estos valores propios pueden parecer inocuos a primera vista, sin embargo, pueden aproximar soluciones a problemas difíciles de NP. Por ejemplo, el problema de determinar el número mínimo de colores necesarios para colorear los vértices de [math] G [/ math] para que los vértices adyacentes tengan colores distintos, el llamado número cromático, es un problema NP-difícil. Pero el conocimiento de los valores propios más pequeños y más grandes de la gráfica, [math] \ lambda_n [/ math] y [math] \ lambda_1 [/ math] respectivamente, es suficiente para decirnos que este número está entre [math] 1- \ frac {\ lambda_1} {\ lambda_n} [/ math] y [math] 1+ \ lambda_1 [/ math]. Esto puede ser de gran ayuda en muchas circunstancias.

Más recientemente, ha habido algo de desarrollo en dar un significado al inverso de [matemáticas] A [/ matemáticas], por personas como Panda y Pati.

Si utilizamos la matriz laplaciana para representar nuestro gráfico, entonces el determinante de cualquier cofactor de esta matriz es igual al número de árboles de expansión del gráfico. Este es el famoso teorema de Matrix Tree.

Answer 2

Bueno, si considera la “matriz de incidencia” de una gráfica, es una matriz booleana A donde A [i, j] es verdadera cuando hay un borde entre i y j, entonces puede calcular el cierre transitivo de la gráfica ( agregue una arista entre i y j cuando hay una ruta en el gráfico de i a j) usando la multiplicación de matrices.

Esta es en realidad una de las formas más eficientes de calcular el cierre transitivo (ver, por ejemplo, http://ieeexplore.ieee.org/docum …).

En relación con esta idea, puede implementar el algoritmo Floyd-Warshall (que calcula la distancia más corta entre dos nodos en un gráfico) utilizando la multiplicación de matrices. En este caso, considera una matriz de enteros (distancias) y reemplaza la multiplicación entre enteros calculando el valor máximo.

Esto es para lo básico. Para ejemplos que van más allá del simple uso de la multiplicación de matrices, le sugiero que eche un vistazo a la teoría de gráficos espectrales. Este es un dominio de investigación que establece un vínculo entre la teoría de grafos y los valores propios de las matrices relacionadas (teoría de grafos espectrales – Wikipedia).

Otra relación interesante entre las dos teorías se encuentra en el estudio de las matrices totalmente unimodulares (matriz unimodular – Wikipedia). Solo para dar un extracto de la página de Wikipedia: “La matriz de incidencia no orientada de un gráfico bipartito, que es la matriz de coeficientes para la coincidencia bipartita, es totalmente unimodular (TU)”. Esto tiene algunas aplicaciones interesantes en la práctica.

Answer 3

Las descomposiciones laplacianas y de valores propios en general son bastante útiles (partición, cálculo de brecha espectral …). Hay algunas aplicaciones interesantes de ecuaciones diferenciales estocásticas a las matrices de adyacencia que representan la difusión de información o la propagación de epidemias que también son aplicaciones bastante interesantes.

Una de las aplicaciones más famosas es el algoritmo PageRank y sus primos (HodgeRank …). Estos se basan en series de potencia y el teorema de Perron-Frobenius.

Answer 4

Si. Si una matriz A es una matriz de adyacencia para un gráfico G, la entrada (i, j) de A nos dirá cuántas rutas hay desde el vértice i al vértice j de longitud 1 . La entrada (i, j) de la enésima potencia de A nos indicaría cuántos caminos hay presentes desde el vértice i hasta el vértice j de longitud n.