En el invertibility de matriz de adyacencia

Question

Que son las suficientes y necesarias condiciones para un grafo no dirigido sin auto bordes (es decir, sin bucle de longitud 1) tener una invertible la matriz de adyacencia?

Recuerdo que en este caso la matriz de adyacencia es simétrica (es decir,$A = A^T$), todos los elementos en la diagonal son $0$ y hay un $1$, tanto en las entradas $(i,j)$$(j,i)$,$i\neq j$, iff vértice $i$ $j$ están conectados.

Seguramente, necesito que todos los vértices tienen al menos una conexión, de lo contrario la fila relativa de $A$ es nulo. Pero, ¿qué más?

Answer 1

Hasta donde yo sé, no hay una "simple" condición necesaria y suficiente de $G$ para una invertible la matriz de adyacencia. Un par de comentarios:

• Una condición necesaria para que se generaliza su "cada vértice se necesita al menos una conexión de" la condición es que si $S$ es cualquier subconjunto de vértices de la gráfica, hay al menos $|S|$ vértices en la gráfica que tener al menos un vecino en $S$ (incluyendo posiblemente los vértices en $S$ sí). Esto es debido a que las filas de la matriz de adyacencia correspondiente a $S$ necesita tener al menos $|S|$ diferentes columnas con una entrada distinto de cero para ser independiente.

Esta condición necesaria no es suficiente. Por ejemplo, $4$ el ciclo de la expansión de la propiedad, pero un singular de la matriz de adyacencia.

• Un caso especial de la anterior: Si $G$ es bipartito con los no-singular de la matriz de adyacencia, ambas mitades del desdoblamiento tienen igual tamaño.

• La propiedad no es en general lo que se denomina "monotono" -- añadir bordes a una invertible gráfico puede girarse un no-singular de la matriz en un singular y viceversa (por ejemplo, el cierre de un camino de $3$ vértices de un triángulo vs el cierre de un camino de $4$ vértices a un $4$ ciclo).

• Se ha conjeturado que la gran mayoría de singular matrices de adyacencia son causados por vértices aislados, en el siguiente sentido: si nos fijamos en todos los gráficos en $n$ vértices, entonces: $$\frac{|\{G \textrm{ with at least one isolated vertex }\}|}{|\{G \textrm{ with singular adjacency matrix }\}|} \rightarrow 1$$ como $n$ va al infinito. sin embargo, esto es todavía un problema abierto. El numerador es una $(1/2+o(1))^n$ fracción de todos los $n$-vértice gráficos, y el mejor resultado conocido es que el denominador es una $\exp(-n^c)$ fracción de gráficos para algunos pequeños positivo $c$ (debido a Vershynin).

Answer 2

Creo que será difícil conseguir un conjunto general de condiciones. Para fundamentar esta afirmación hago la siguiente observación negativa.

La matriz de adyacencia de cualquier grafo bipartito con un número impar de vértices no es inversible.

Esto sigue puesto que los valores propios de un grafo bipartito son simétricos alrededor de $0$, y puesto que hay un número impar de valores propios (si el gráfico tiene un número impar de vértices) entonces al menos uno de ellos es $0$.

Answer 3

Usted puede encontrar la siguiente referencia útil:

• Sciriha, Irene. "Una caracterización de singular gráficos". Revista electrónica de Álgebra Lineal 16.1 (2007): 38.

Describe las condiciones necesarias y suficientes para la matriz de adyacencia de un gráfico simple para ser singular (no invertible). Ten en cuenta: estos no parecen ser particularmente "bonita" de condiciones.

Answer 4

Usted podría tener un poco de suerte se aproxima el problema desde el otro lado y explorar el significado de las propiedades de una matriz invertible (por el invertible la matriz teorema) en términos de las propiedades de la gráfica descrita por su matriz de adyacencia. Estoy de acuerdo con Owen que es poco probable para encontrar un exhaustivo conjunto general de condiciones, pero se pueden encontrar algunas propiedades de gráfico que garantiza una invertible la matriz de adyacencia y que podría ser útil en su situación particular.

Para aclarar con un ejemplo, un prometedor propiedad de una matriz invertible es que cada una de las columnas deben ser linealmente independientes. Obviamente, esto impone restricciones en la conectividad de la base del gráfico, que se podría traducir a algún conocido, o al menos correctamente definida, propiedades del grafo gráficos.