Teorema de enderezamiento del gráfico de Fari

El teorema de Farey  es una declaración teórica de grafos sobre la posibilidad de enderezar los bordes de cualquier gráfico plano . En otras palabras, el permiso para dibujar bordes no como segmentos, sino como curvas, no amplía la clase de gráficos planos.

Nombrado en honor al matemático húngaro István Fáry [1] , aunque fue probado de forma independiente por Klaus Wagner en 1936 [2] y Stein en 1951 [3] .

Declaración: cualquier gráfico plano simple tiene una representación plana en la que todos los bordes se representan como segmentos de línea .

Prueba

Una de las formas de probar el teorema de Fari es el uso de la inducción matemática [4] . Sea G un grafo plano  simple con n vértices. Podemos considerar el gráfico como planar máximo, si es necesario, podemos agregar bordes al gráfico original G . Todas las caras de G en este caso deben ser triángulos, ya que podemos agregar una arista a cualquier cara con más lados sin romper la planaridad del gráfico, lo que contradice la convención de maximalidad del gráfico. Elegimos unos tres vértices a , b , c , formando una cara triangular del grafo G . Probaremos por inducción sobre n que existe otro empotramiento combinatoriamente isomórfico con aristas directas del grafo G en el que el triángulo abc es la cara exterior del empotramiento. ( El isomorfismo combinatorio significa que los vértices, las aristas y las caras del nuevo dibujo pueden corresponder a los elementos del dibujo anterior, conservando todas las relaciones de incidencia entre las aristas, los vértices y las caras, no solo entre los vértices y las aristas. ) La base de la inducción es trivial cuando a , b y c son los únicos vértices en G ( n =3 ).

Por la fórmula de Euler para gráficos planos, el gráfico G tiene 3n − 6 aristas . De manera equivalente, si definimos el déficit de un vértice v en G como 6 − grado ( v ) , la suma de los déficits es 12 . Cada vértice en G puede tener un déficit de como máximo tres, por lo que hay al menos cuatro vértices con un déficit positivo. En particular, podemos elegir un vértice v con cinco vecinos como máximo que sea diferente de a , b y c . Sea G' formado quitando el vértice v del grafo G y triangulando la cara f obtenida después de quitar el vértice v . Por inducción, el grafo G' tiene una incrustación de borde recto combinatoriamente isomórfica en la que abc es una cara exterior. Dado que la incrustación G resultante era combinatoriamente isomorfa a G' , al eliminar las aristas que se agregaron para obtener el grafo G', queda una cara f , que ahora es un polígono P con cinco lados como máximo. Para obtener un dibujo G con un empotramiento combinatoriamente isomorfo con aristas rectas, se debe agregar el vértice v al polígono y conectar por segmentos a los vértices del polígono. Por el teorema de la galería de imágenes, hay un punto dentro de P donde se puede colocar un vértice v , de modo que las aristas que conectan el vértice v con los vértices del polígono P no se cruzan con otras aristas del polígono, lo que completa la demostración.

El paso de inducción de la prueba se ilustra a la derecha.

Resultados relacionados

De Freysix, Pach y Polak mostraron cómo encontrar en tiempo lineal un patrón con bordes rectos en una red con dimensiones linealmente dependientes del tamaño del gráfico, dando un conjunto universal de puntos con dimensiones cuadráticas. Schneider usó un método similar para probar límites mejorados y caracterización de planaridad , donde se basó en un orden de incidencia parcial. Su trabajo enfatiza la existencia de una cierta partición de los bordes de un gráfico plano máximo en tres árboles, lo que se conoce como el bosque de Schneider .

El teorema del "empaquetamiento de goma" de Tutt establece que cualquier gráfico plano de tres conexiones se puede dibujar en el plano sin intersecciones, de modo que sus bordes sean segmentos de línea y su cara exterior sea un polígono convexo [5] . El nombre refleja el hecho de que dicha incrustación se puede encontrar como un punto de equilibrio para un sistema de resortes que representan los bordes del gráfico.

El teorema de Steinitz establece que cualquier gráfico plano conectado en 3 se puede representar como los bordes de un poliedro convexo en un espacio tridimensional. Se puede obtener una incrustación con bordes rectos de un gráfico como una proyección de dicho poliedro en un plano.

El teorema de empaquetamiento de círculos establece que cualquier gráfico plano puede representarse como el gráfico de intersección de un conjunto de círculos disjuntos en el plano. Si colocamos cada vértice de la gráfica en el centro del círculo correspondiente, obtenemos una representación de la gráfica con aristas rectas.

Problemas no resueltos en Matemáticas : ¿Algún gráfico plano tiene una representación con aristas directas en la que las longitudes de todas las aristas son números enteros?

Haiwo Harbort planteó la cuestión de si para cualquier gráfico plano existe una representación con aristas directas en la que todas las longitudes de las aristas son números enteros [6] . ¿Es correcta la hipótesis de Harbort?, sigue siendo una pregunta abierta (a partir de 2014). Sin embargo, se sabe que existe una incrustación con bordes directos enteros paragráficos cúbicos[7].

Sachs [8] planteó la cuestión de si cualquier gráfico con una incrustación no vinculada en el espacio euclidiano tridimensional tiene una incrustación no vinculada en la que todos los bordes están representados por segmentos de línea, por analogía con el teorema de Farey para incrustaciones bidimensionales.

Véase también

Notas

  1. ↑ Fáry, 1948 , p. 229–233.
  2. ↑ Wagner, 1936 .
  3. ↑ Stein, 1951 .
  4. ↑ La prueba anterior se puede encontrar en el libro de V. V. Prasolov. Elementos de topología combinatoria y diferencial. M.: MTsNMO, 2004.
  5. ↑ Tutte, 1963 , pág. 743–767.
  6. ↑ Harbourth, Kemnitz, Moller, Sussenbach, 1987 ; Kemnitz, Harbourth, 2001 ; Mohar, Thomassen, 2001 .
  7. ↑ Geelen, Guo, McKinnon, 2008 .
  8. ↑ Sachs, 1983 .

Literatura