Determinantes en la teoría de grafos

Question

En teoría de grafos, trabajamos con matrices de adyacencia que definen las conexiones entre los vértices. Estas matrices tienen varios lineal-propiedades algebraicas. Por ejemplo, su seguimiento puede ser calculado (es cero en el caso de un loopless gráfico, es decir, una irreflexiva simétrico binario relación). Y también podemos calcular sus factores determinantes.

¿Cómo interpreta usted el factor determinante en el contexto de una gráfica? Por ejemplo, que me enseñe la teoría de redes y el cálculo de la "centralidad de vector propio' requiere el uso de los determinantes. Pero en general, la pregunta que siempre surge: ¿qué hace el determinante significan en el contexto de la red (o gráfico)? Se me dirá de una propiedad de la red que es útil?

En esencia, estoy tratando de encontrar a un usuario de fácil interpretación de los factores determinantes en el contexto de las redes o grafos. Agradecería cualquier tipo de ayuda.

Answer 1

Deje $G$ ser un grafo con matriz de adyacencia $A$. Deje $s(G)$ el número de componentes conectados de $G$ que son los ciclos y $r(G)$ el número de componentes conectados que son o $K_2$ o incluso ciclos. Entonces $$\det(A) = \sum_{H} (-1)^{r(H)} 2^{s(H)}$$ where the sum is over all spanning subgraphs $H$ of $G$ that have only $K_2$ y ciclos como sus componentes conectados.

En particular, si $T$ es un árbol, el determinante de su matriz de adyacencia es $\pm$ el número de perfecto elecciones de $T$.

Un pasaje de N. Biggs: Algebraicas Teoría de grafos. Segunda Edición. Cambridge University Press, es:

Esta identidad puede ser generalizado a todos los demás coeficientes del polinomio característico de $A.$ Para obtener más información, consulte el capítulo "Determinante expansiones" de Biggs' libro sobre algebraicas teoría de grafos.

Answer 2

Si su gráfico está dirigido y cada borde tiene un peso$1$, entonces el determinante cuenta el número de ciclos no necesariamente conectados (es decir, las subgrafías son uniones disjuntas de ciclos conectados) que pasan por cada vértice del gráfico. El ciclo se cuenta como$-1$ si el número de sus componentes tiene una paridad diferente al número de vértices del gráfico; de lo contrario, se cuenta como$1$.