Usos de la matriz de incidencia de un grafo

Question

La matriz de incidencia de un gráfico es una forma de representar el gráfico. ¿Por qué se ha de crear esta representación de un gráfico? En otras palabras, ¿cuáles son las aplicaciones de la matriz de incidencia o algunas propiedades interesantes que revela sobre su gráfico?

Answer 1

Porque entonces se pueden aplicar las herramientas de la teoría de matrices a los problemas de la teoría de grafos. Un área donde es útil es cuando se consideran los flujos en un gráfico, por ejemplo el flujo de corriente en un circuito eléctrico y los potenciales asociados .

Answer 2

Otro ejemplo es el bello Teorema del Árbol Matriz, que dice que el número de árboles de extensión de un grafo es igual a un menor del Laplaciano del grafo, que es una matriz estrechamente relacionada con la matriz de incidencia.

Answer 3

Las ventajas son muchas, sobre todo si el número total de aristas es $|E| = \Omega(|V|^2)$ . En primer lugar, el tiempo constante en el peor de los casos para añadir y eliminar aristas, así como para comprobar si la arista existe (las listas/conjuntos de adyacencia pueden tener algunos $\log n$ factores). En segundo lugar, la simplicidad: no se necesitan estructuras avanzadas, es fácil trabajar con ellas, etc. Además, algunos algoritmos prefieren almacenar datos para cada arista (como los flujos), por lo que la representación matricial es muy conveniente, y a veces tiene buenas propiedades, como:

• si $A$ contiene $1$ para los bordes y $0$ en caso contrario, entonces $A^k$ contiene el número de trayectorias de longitud $k$ entre todos los vértices,
• si $A$ contiene pesos (con $\infty$ lo que significa que no hay borde), entonces $A^k$ utilizando el semillero minitropical le da los caminos más ligeros de longitud $k$ entre todos los pares.

Por último, hay teoría de los grafos espectrales .

Espero que esto explique algo ;-)