Prueba de la conectividad algebraica

Question

Tengo mucha curiosidad por la prueba de la conectividad algebraica

Conectividad algebraica:

La conectividad algebraica de un grafo $G$ es el segundo valor propio más pequeño de la matriz laplaciana de $G$ . Este valor propio es mayor que $0$ si y sólo si $G$ Esto es un corolario del hecho de que el número de veces que $0$ aparece como un valor propio en el laplaciano es el número de componentes conectados en el gráfico.

Para más detalles : Conectividad algebraica en Wikipedia .

Me pareció muy interesante esta afirmación, cómo exactamente el segundo valor propio más pequeño puede ser el signo de la conectividad del gráfico.

A continuación, un hecho no menos interesante,

Denotemos los valores propios por $\lambda_1 \leq \lambda_2 \leq \cdots \leq \lambda_n$ entonces $\lambda_1=0$ . Esto se puede demostrar utilizando el hecho de que la matriz laplaciana es semidefinida positiva, lo que implica que tiene valores propios no negativos, y mostrando que 0 es el valor propio de esta matriz correspondiente al vector $ \langle 1,1, \cdots, 1 \rangle$ .

Hasta ahora no he hecho la prueba de la conectividad algebraica. Si tienes un enlace, te agradeceré que lo publiques.

Gracias.

Answer 1

Dejemos que $G = (V, E)$ sea un gráfico finito y que $\Delta$ denotan su Laplaciano (aquí tomamos la convención de que el Laplaciano es semidefinido positivo). Para simplificar, los vértices se denominan $1, 2, ... n$ . Entonces $\Delta$ es la matriz asociada a la forma cuadrática $$q(x_1, ... x_n) = \sum_{(i, j) \in E} (x_i - x_j)^2$$

que se podría llamar el Energía de Dirichlet . Recordemos que, para un cambio apropiado de variables, dicha forma cuadrática puede escribirse como $$q(z_1, ... z_n) = \sum_i \lambda_i z_i^2$$

donde $\lambda_i$ son los valores propios de $\Delta$ . Así pues, para determinar la multiplicidad del valor propio cero basta con determinar cuándo $q$ puede ser cero. Pero a partir de la primera expresión debe quedar claro que $q = 0$ si y sólo si $x_i = x_j$ siempre que $(i, j) \in E$ es decir, siempre que $(x_1, ... x_n)$ determina una función $$x : V \to \mathbb{R}$$

que es constante en cada componente conectado de $G$ . La dimensión de este espacio de funciones es claramente el número de componentes conectados de $G$ y la conclusión es la siguiente.

Answer 2

segunda prueba

La prueba dada anteriormente tiene la debilidad de que no dice que se trata de otro valor propio. Por eso este hecho "Pero a partir de la primera expresión debería estar claro que $q = 0$ si y sólo si $x_i = x_j$ siempre que $(i, j) \in E$ es decir, siempre que $(x_1, ... x_n)$ determina una función $$x : V \to \mathbb{R}$$ "significa simplemente que el vector propio del segundo valor propio es $c \left( \begin{array}{c} 1 \\ 1 \\ \vdots \\ 1 \end{array} \right) $ donde $ c= x_i, \; \forall i $ .\

Para solucionar este problema, proponemos la siguiente prueba.

Supongamos que $ \lambda_2=0 $ Entonces, como $ \lambda_1=0 $ la multiplicidad de $ 0 $ el valor propio de $L , \text{ ( The Laplacian Matrix of G )}, $ es al menos 2. (decimos que es al menos dos para no perder la generalidad).\N-

A partir del producto interior de filas lema $ L=DD^T $ , donde $ D $ es la matriz de incidencia de un gráfico orientado de $G$ .\

Si $ 0 $ tiene una multiplicidad de al menos 2, entonces $ L=DD^T $ tiene un rango como máximo $ n-2 $ .\

Eso es, $n-2 \geq rank(DD^T)=rank(D)=n-c_0 $ , donde $ c_0 $ es el número de componentes de $G$ . \

Esto significa que $ n-c_0 \leq n-2 \Leftrightarrow c_0 \geq 2 $ .\

Es decir $ G $ tiene al menos $2$ componentes. Es decir, está desconectado. El mismo enfoque también funciona para la inversa y el corolario.