Comprobación de la conectividad de la matriz de adyacencia

Question

¿Cuál crees que es el algoritmo más eficiente para comprobar si un grafo representado por una matriz de adyacencia está conectado? En mi caso también me dan los pesos de cada arista.

Hay otra pregunta muy similar a la mía: Cómo comprobar si un grafo está totalmente conectado y encontrar grafos aislados a partir de una matriz de adyacencia

Esa respuesta parece ser buena, excepto que no la entiendo realmente. ¿Cómo es que elevar la matriz al cuadrado repetidamente da información sobre su conectividad? Hay otra respuesta que afirma que los vectores propios también dan información sobre la conectividad del gráfico, ¿podría alguien explicar eso también?

Lo pregunto porque no tengo la formación necesaria para entender las respuestas dadas, sólo estoy resolviendo un problema que tiene que ver con estos temas. Buscando en google tampoco me dio respuesta, así que espero que alguien pueda aclararlo.

Answer 1

Si pones todos los 1 en la diagonal de tu matriz de adyacencia $A$ y todos los pesos de las aristas son positivos, entonces cuando se multiplica $A^2 = A*A$ se obtiene una entrada no nula $a_{ij}$ en $A^2$ si y sólo si existe un $a_{ik}$ y $a_{kj}$ en $A$ para algunos $k$ es decir, hay un camino de longitud $2$ entre $i$ y $j$ si $k\neq j$ y $k\neq i$ y hay un camino de longitud $1$ si $k = j$ o $k = i$ . Por lo tanto, las entradas no nulas en $A^2$ le indica todos los pares de nodos que están conectados por un camino de longitud $2$ . Del mismo modo, las entradas en $A^k$ le indica todos los pares de nodos que están conectados por un camino de longitud $k$ . Así que si empiezas con $A$ y seguir cuadrando hasta conseguir $A^k$ donde $k \geq n$ donde $n$ es el número de nodos, entonces las entradas no nulas de la fila $i$ te dice todos los nodos que están conectados al nodo $i$ (ya que dos nodos conectados deben estar conectados por un camino de longitud $n$ o menos). Así que si tienes una fila en $A^k$ que es todo distinto de cero, entonces el gráfico está conectado. Si el gráfico no está conectado, se puede decir de forma similar los componentes conectados a partir de las filas de $A^k$ .

Answer 2

Sé que la pregunta es antigua y que la primera respuesta es correcta. Sin embargo, debido a su importancia, me gustaría señalar una alternativa más eficiente y más elegante. Utilizando el valor de Fiedler es decir, el segundo valor propio más pequeño de la matriz laplaciana de G (es decir $L=D-A$ ) podemos averiguar de forma eficiente si el gráfico en cuestión está conectado o no, de forma algebraica. Es decir, "La conectividad algebraica de un grafo G es mayor que 0 si y sólo si G es un grafo conexo" (del mismo artículo de Wikipedia). Si este valor propio es positivo, el grafo está conectado. La otra alternativa eficiente (algorítmica) es ejecutar el algoritmo de componentes conectados (ejecutando recursivamente Búsqueda en profundidad ) podemos encontrar todos los componentes conectados y ver si el mayor/primero incluye todos los nodos del gráfico.