¿Cuáles son los teoremas / deducciones más ingeniosos en la teoría de grafos?

Dos resultados originalmente propuestos por Leonhard Euler son bastante interesantes y fundamentales para la teoría de grafos:

1. Siete puentes de Königsberg
2. Característica de Euler (V – E + F = 2)

La solución de los Siete Puentes de Königsberg de Euler es uno de los primeros problemas celebrados de la teoría de grafos y se dice que sentó las bases para la topología de los siglos XIX y XX. Euler demostró que no era posible caminar por la ciudad de Königsberg (ver más abajo) y cruzar cada uno de sus 7 puentes exactamente una vez.

Euler señaló que la elección de la ruta dentro de cada masa de tierra es

irrelevante. La única característica importante de una ruta es la secuencia de

Puentes cruzados. Esto le permitió reformular el problema como se muestra en el siguiente gráfico.

Euler observó que (excepto en los puntos finales de la caminata), cada vez que uno entra en un vértice por un puente, uno sale del vértice por un puente. En otras palabras, durante cualquier recorrido en el gráfico, el número de veces que uno ingresa en un vértice no terminal es igual al número de veces que uno lo abandona. Ahora, si cada puente se atraviesa exactamente una vez, se deduce que, para cada masa de tierra (excepto posiblemente para los elegidos para el inicio y el final), el número de puentes que tocan esa masa de tierra es par. Sin embargo, las cuatro masas de tierra en el problema original son tocadas por un número impar de puentes, por lo que no es posible atravesar todos los puentes exactamente una vez. Más tarde se demostró que si un gráfico tiene exactamente cero o dos vértices de grado impar, entonces existe un “paseo de Euler” del gráfico.

Para poliedros convexos y gráficos planos, sostiene que V – E + F = 2 donde:

• V es el número de vértices
• E es el número de aristas
• F es el número de caras

La característica de Euler es fundamental para demostrar que hay exactamente 5 sólidos platónicos (todos los bordes, vértices y ángulos son congruentes), a saber, tetraedro, cubo, octaedro, dodecaedro, isocaedro.

[1]: http://en.wikipedia.org/wiki/Sev …
[2]: http://en.wikipedia.org/wiki/Eul …

Uno de los resultados más fundamentales e ingeniosos en la teoría de grafos y de hecho todas las matemáticas discretas es el Lema de regularidad de Szemeredi [1]. Originalmente se avanzó como resultado auxiliar para probar una conjetura de Erdős y Turán de 1936 (sobre las propiedades de Ramsey de las progresiones aritméticas), que establecía que las secuencias de enteros con densidad superior positiva SIEMPRE deben contener progresiones aritméticas arbitrariamente largas (ahora llamadas como el teorema de Szemeredi (1978) [2]). Ahora el lema de regularidad en sí mismo se considera como una de las herramientas más importantes en la teoría de grafos.

Declaración: más o menos, el Lema de regularidad de Szemeredi establece que:

Cada gráfico puede ser aproximado por gráficos aleatorios. Esto es en el sentido de que cada gráfico se puede dividir en un número limitado de partes iguales de manera que:
1. La mayoría de los bordes corren ENTRE diferentes partes
2. Y que estos bordes se comportan como si se generaran al azar.

La naturaleza fundamental del Lema de regularidad como herramienta en la teoría de gráficos (y más allá) podría entenderse por el hecho de que dos medallas de campo recientes (Timothy Gowers, 1998 y Terence Tao, 2006) fueron otorgadas al menos en parte por lograr resultados innovadores en el lema de regularidad y su uso para demostrar resultados fundamentales en progresiones aritméticas (como el Teorema de Green-Tao [3]).

Ampliando el enunciado aproximado anterior, básicamente el Lema de regularidad de Szemeredi afirma lo siguiente: Si tenemos un gráfico, entonces existe una partición de su vértice establecido en clases disjuntas [math] k [/ math]. Estas k clases podrían considerarse como [math] {} _ k C_2 ​​[/ math] pares (gráficos bipartitos). De modo que los bordes entre estos gráficos bipartitos se comporten al azar en todos los pares excepto [math] \ epsilon k ^ 2 [/ math]. (donde \ epsilon es un número pequeño. Un valor típico es 1/16).

Para esbozar de manera aproximada cómo funciona el lema de regularidad, primero presentamos algunas definiciones:
Definición 1: Si [matemática] G = (V, E) [/ matemática] es un gráfico y [matemática] A, B [/ matemática] son ​​subconjuntos disjuntos de [matemática] V [/ matemática]. Luego, denotamos el número de aristas con un punto final en [matemática] A [/ matemática] y otra en [matemática] B [/ matemática] por [matemática] e (A, B) [/ matemática]. Cuando [matemática] A [/ matemática] y [matemática] B [/ matemática] no están vacías, definimos la densidad de los bordes entre [matemática] A [/ matemática] y [matemática] B [/ matemática] como
[matemáticas] d (A, B) = \ frac {e (A, B)} {| A || B |} [/ matemáticas].

Esto solo define la densidad del borde en un gráfico bipartito.

Definición 2: El gráfico bipartito [math] G = (A, B, E) [/ math] se llama [math] \ epsilon [/ math] -regular si para cada [math] X \ subconjunto A [/ math] y [matemática] Y \ subconjunto B [/ matemática] satisfactoria

[matemáticas] | X | > \ epsilon | A |, | Y | > \ epsilon | B | [/ math]
nosotros tendriamos:
[matemáticas] | d (X, Y) – d (A, B) | <\ epsilon [/ math]

Esto significa que un gráfico bipartito es épsilon regular SI tomamos cualquier subets aleatorios (X e Y) de A y B e incluso entonces la densidad de borde entre estos subconjuntos es casi la misma que la densidad de borde en el gráfico bipartito original. En efecto, esto implica que si un gráfico bipartito es épsilon regular, todos los bordes entre los dos conjuntos disjuntos se distribuyen uniformemente.

Definición 3: Una partición equitativa del conjunto de vértices [matemática] V [/ matemática] de un gráfico [matemática] G = (V, E) [/ matemática] es una partición de [matemática] V [/ matemática] tal que todos las particiones [matemáticas] C_0, C_1, \ puntos, \ C_k [/ matemáticas] están separadas por pares. Y que todos [matemáticas] C_i [/ ​​matemáticas] con [matemáticas] 1 \ leq i \ leq k [/ matemáticas] tienen la misma cardinalidad. [math] C_0 [/ math] se denomina conjunto excepcional y solo está presente por razones técnicas (para garantizar que todas las particiones tengan la misma cardinalidad).

Definición 4: Para cada partición equitativa [matemática] P [/ matemática] del conjunto de vértices [matemática] V [/ matemática] de [matemática] G = (V, E) [/ matemática] en clases [matemática] C_0, C_1 , \ dots, \ C_k [/ math], asociamos una medida llamada índice de la partición (también llamada potencial) de [math] P [/ math] definida como:

[matemáticas] \ displaystyle ind (P) = \ frac {1} {k ^ 2} \ sum_ {1 \ leq r

Esto solo define una medida de cuán cerca está todo el conjunto de particiones de ser épsilon regular.