Ejemplos de teoremas en teoría de grafos

Question

Estoy buscando ejemplos de usos de la matriz de incidencia en los gráficos para mi clase (aparte de demostrar que para un gráfico $G=(V,E)$ tenemos $2|E|=\underset{v\in V}{\sum}d(v)$ ). ¿Se te ocurre algo interesante?
Gracias de antemano por cualquier ayuda.

Answer 1

Un ejemplo clásico es el Teorema de la amistad de Erdos y Renyi.

Answer 2

Dejemos que $R$ sea un anillo conmutativo y $R(V), R(E)$ el libre $R$ -en los vértices y las aristas, respectivamente. Elige una orientación del grafo (una flecha unida a cada arista que apunta de un vértice a otro). La página web orientado La matriz de incidencia es la matriz de un $R$ -homomorfismo de módulo

$$\partial : R(E) \to R(V)$$

enviando un borde $e$ a $v - w$ , donde $v, w$ son los vértices con la orientación adecuada. Este morfismo, y en particular su núcleo, es un invariante básico del grafo: cuando $R = \mathbb{Z}$ o $R = \mathbb{F}_2$ su núcleo es la integral (resp. mod $2$ ) espacio para bicicletas del grafo, que es una herramienta útil para responder a ciertas preguntas en la teoría de grafos (el artículo de Wikipedia tiene referencias). En abstracto, se trata de un simple ejemplo de homología simplicial grupo. (Tenga en cuenta que no tiene que elegir una orientación si $R$ tiene la característica $2$ . Este es un comportamiento familiar de la topología algebraica).

La transposición de la matriz de incidencia es la matriz de un homomorfismo

$$d : R^V \to R^E$$

en la otra dirección (donde $R^S$ es el $R$ -módulo de funciones $S \to R$ ) doble a la anterior. Envía una función $f(v)$ en los vértices a la función $df(e) = f(v) - f(w)$ en los bordes y puede considerarse como un análogo simple de la derivada. De hecho, todo este montaje es un análogo simple de cohomología de Rham y Teoría de Hodge y se puede obtener el Laplaciano naturalmente de esta manera también.

Los operadores anteriores aparecen de forma natural si se piensa en los grafos como circuitos. De hecho, Leyes de Kirchhoff se puede enunciar de forma natural utilizándolas cuando $R = \mathbb{R}$ un elemento $I \in \mathbb{R}(E)$ puede interpretarse como una lista de corrientes si y sólo si

$$\partial I = 0$$

y un elemento $e \in R^E$ puede interpretarse como una lista de posibles diferencias si y sólo si existe $\phi \in R^V$ (el potencial) tal que

$$d \phi = e.$$

El material sobre circuitos debería estar en Bollobás' Teoría moderna de los grafos y para más información Doyle y Snell's Paseos aleatorios y redes eléctricas también merece la pena comprobarlo.

Answer 3

Los valores propios de la matriz de adyacencia proporcionan límites al número cromático $\chi(G)$ .

Para un gráfico $G$ , dejemos que $\mu_\max(G)$ y $\mu_\min(G)$ sean los valores propios máximo y mínimo de la matriz de adyacencia. Nota: $\mu_\min(G) < 0 < \mu_\max(G)$ si $G$ no está vacío.

Todos los gráficos no vacíos satisfacen $$1 - \frac{\mu_\max(G)}{\mu_\min(G)} \leq \chi(G) \leq \mu_\max(G) + 1.$$

Esto se demuestra en la obra de Bollobas Teoría moderna de los grafos .

Answer 4

También existe el resultado clásico de que las potencias de la matriz de adyacencia describen el número de caminos de una longitud determinada entre dos vértices.