Número mínimo de intersecciones de borde de gráfico

En teoría de grafos, el número de intersección cr( G ) de un gráfico G es el número más pequeño de intersecciones de aristas en un dibujo plano de un gráfico G . Por ejemplo, un gráfico es plano si y solo si su número de intersección es cero.

El punto de partida matemático para estudiar el número de intersecciones fue el problema de la fábrica de ladrillos de Turan planteado por Pal Turan , en el que se requería encontrar el número de intersecciones de un grafo bipartito completo K m,n [1] . Sin embargo, la misma tarea se planteó en sociología aproximadamente al mismo tiempo en relación con la construcción de sociogramas [2] . La tarea sigue desempeñando un papel importante en la visualización de gráficos .

A menos que se indique lo contrario, el recuento de intersecciones se refiere a las representaciones de gráficos por cualquier curva. La condición de intersección de línea recta requiere que todos los bordes sean segmentos de línea, lo que puede cambiar la respuesta. En particular, el número de intersecciones de líneas rectas de un gráfico completo es igual al número mínimo de cuadriláteros convexos definidos por un conjunto de n puntos en posición general, lo que está estrechamente relacionado con el problema del final feliz [3] .

Historia

Durante la Segunda Guerra Mundial, el matemático húngaro Pal Turan se ve obligado a trabajar en una fábrica de ladrillos, empujando un carro cargado de ladrillos desde los hornos hasta los almacenes. La fábrica tenía vías desde cada horno hasta cada almacén, y era más difícil empujar el carro en las intersecciones de las vías, lo que llevó a Turan a formular el problema de la fábrica de ladrillos: ¿cuál es el número mínimo de intersecciones de un dibujo de un edificio completo ? gráfico ? [4] .

Zarankiewicz intentó resolver el problema de Turan [5] . Su prueba contenía un error, pero estableció el límite superior correcto

para el número de intersecciones del grafo bipartito completo K m,n . La hipótesis de que esta desigualdad es de hecho una igualdad se conoce como la conjetura de Zarankiewicz. El límite inferior fue descubierto sólo once años después de la publicación casi simultánea por Gerhard Ringel y Paul Chester Kainen [6] .

El problema de determinar el número de intersección de un gráfico completo fue planteado por primera vez por Anthony Hill y apareció impreso en 1960 [7] . Hill y su colaborador John Ernest eran dos artistas constructivistas fascinados por las matemáticas, y no solo formularon el problema, sino que también formularon un límite superior en la conjetura del número de intersección para tales gráficos, que Richard K. Guy publicó en 1960 [7] . Es decir, este límite es igual a

lo que da los valores 1, 3, 9, 18, 36, 60, 100, 150 para p = 5,…, 12 (secuencia A000241 en OEIS ). Thomas L. Saaty dio una formulación independiente de la conjetura en 1964 [8] . Saati descubrió más tarde que el límite superior se alcanza para p ≤ 10 , y Pan y Richter demostraron que también se alcanza para p = 11, 12

Si solo se permiten arcos rectos, se requieren más intersecciones. El número de intersecciones de línea recta para los gráficos K 5 - K 12 es 1, 3, 9, 19, 36, 62, 102, 153 (secuencia A014540 en OEIS ). Se conocen valores para gráficos hasta K 27 . Para K 28 , se necesitan cruces 7233 o 7234. Otros valores se recopilan en el proyecto "Número de intersecciones en línea recta" [9] . Curiosamente, no se sabe si los números de intersección ordinarios y rectilíneos son los mismos para gráficos bipartitos completos. Si la conjetura de Zarankievich es verdadera, entonces la fórmula para el número de intersección de un gráfico completo es asintóticamente verdadera [10] , es decir,

A partir de abril de 2015, se conoce el número de intersecciones para un número muy pequeño de familias de grafos. En particular, a excepción de unos pocos casos iniciales, el número de intersecciones de gráficos completos, gráficos bipartitos completos y productos de ciclo sigue siendo desconocido. Ha habido cierto éxito para el límite inferior, según de Klerk, Maharry, Pasechnik y Richter [11] . Schaefer [12] proporciona una amplia descripción general de las diversas opciones .

La conjetura de Albertson , formulada por Michael O. Albertson en 2007, establece que entre todos los gráficos con número cromático n , el gráfico completo K n tiene el número mínimo de intersecciones. Es decir, si la conjetura de Guy-Saaty sobre el número de intersección de un gráfico completo es cierta, cualquier gráfico n -cromático tiene un número de intersección al menos igual a la fórmula de la hipótesis. Se sabe que esto es válido para n ≤ 16 [13] .

Dificultad

En el caso general, determinar el número de intersecciones de un gráfico es una tarea difícil. Garey y Johnson (Michael Garey, David S. Johnson) en 1983 demostraron que este problema es NP-difícil [14] . De hecho, el problema sigue siendo NP-difícil incluso cuando se limita a gráficos cúbicos [15] y gráficos casi planos [16] (gráficos que se vuelven planos después de eliminar un borde). En particular, la definición del número de intersecciones rectilíneas es completa para la teoría existencial de los números reales [17] .

Sin embargo, existen algoritmos eficientes para determinar que el número de intersecciones no exceda una constante k fija . En otras palabras, el problema es solucionable con un parámetro fijo [18] [19] . Sigue siendo difícil para grandes k como | V |/2. También existen algoritmos de aproximación eficientes para estimar cr( G ) en grafos con grado acotado [20] . En la práctica, se utilizan algoritmos heurísticos , como un algoritmo simple que comienza con un gráfico sin bordes y agrega bordes gradualmente para obtener el mínimo número adicional posible de intersecciones. Este algoritmo se utiliza en el programa del proyecto de computación distribuida "Número de intersecciones de líneas rectas" [21] .

Número de intersecciones de gráficas cúbicas

Se conocen los gráficos cúbicos más pequeños con cruces 1-8 (secuencia A110507 en OEIS ).

Los gráficos cúbicos más pequeños con el número de intersecciones: [22]

1 es un grafo bipartito completo K 3,3 con 6 vértices. 2 es un gráfico de Petersen con 10 vértices. 3 es un gráfico de Heawood con 14 vértices. 4 es un gráfico de Möbius-Cantor con 16 vértices. 5 es un gráfico de Pappa con 18 vértices. 6 - Gráfico de Desargues con 20 vértices. 7 - 4 gráficos con 22 vértices (CNG 7A, CNG 7B, CNG 7C, CNG 7D). 8 - Gráfico de Nauru y gráfico de McGee (o (3,7) -celda ) con 24 vértices.

En 2009, Ikzu (Exoo) sugirió que el gráfico cúbico más pequeño con el número de intersección 11 es el gráfico de Coxeter , con el número de intersección 13 el gráfico Tatta-Coxeter , con el número de intersección 170 el Tatta de 12 celdas [23] [24] .

Desigualdad para el número de intersecciones

Una desigualdad muy útil para el número de intersecciones fue descubierta de forma independiente por Aitai , Chvatal , Newborn y Szemeredi [25] y Layton [26] :

Para grafos simples no dirigidos G con n vértices y e aristas tales que e > 7 n tenemos:

La constante 29 es la más conocida. Según Ackerman [27] la constante 7 puede reducirse a 4 , pero costará cambiar la constante 29 a 64 .

La razón del interés de Leighton en el estudio del número de intersecciones fue la aplicación al desarrollo de chips VLSI en informática teórica. Más tarde, Szekely [28] también se dio cuenta de que esta desigualdad da pruebas muy simples de algunos teoremas importantes de la geometría de incidencia , como el teorema de Beck y el teorema de Szemeredi-Trotter , y Tamal Dey usó la desigualdad para probar un límite superior en k geométrico - conjuntos [29] .

Para gráficos con circunferencia mayor que 2 r y e ≥ 4 n , Pach, Spencer y Toth [30] mostraron una mejora en esta desigualdad

Prueba de la desigualdad para el número de intersecciones

Primero, damos una estimación preliminar: para cualquier gráfico G con n vértices y e aristas, tenemos

Para probar esto, presentamos un dibujo de un gráfico G con intersecciones exactamente cr( G ) . Cada una de esas intersecciones se puede eliminar junto con la eliminación de un borde de G . Por lo tanto, podemos encontrar un grafo con al menos e − cr( G ) aristas y n vértices con cero intersecciones, y por lo tanto será un grafo plano . Pero de la fórmula de Euler debemos tener e − cr( G ) ≤ 3 n , de donde obtenemos la desigualdad requerida. (De hecho, tenemos e − cr( G ) ≤ 3 n − 6 para n ≥ 3 ).

Para obtener la desigualdad del número de intersección, aplicamos el razonamiento probabilístico . Sea 0 < p < 1  un parámetro probabilístico a elegir más adelante. Construya un subgrafo aleatorio H de G colocando cada vértice de G en H independientemente con probabilidad p , y cada arista de G estará en H si y solo si ambos vértices de la arista se encuentran en H . Sean e H , n H y cr H el número de aristas, vértices e intersecciones del gráfico H , respectivamente. Como H es un subgrafo de G , su diagrama está contenido en el diagrama de G. Por la desigualdad preliminar para el número de intersecciones, tenemos

Calculando las expectativas matemáticas , obtenemos

Dado que cada uno de los n vértices de G tiene una probabilidad p de caer en H , obtenemos E [ n H ] = pn . De la misma manera, toda arista en G tiene una probabilidad p 2 de permanecer en H ya que ambos extremos deben estar en H . Por lo tanto, mi [ mi H ] = p 2 e . Finalmente, cada intersección en G tiene probabilidad p 4 de permanecer en H , ya que cada intersección involucra cuatro vértices. Para entender esto, imagina un diagrama G con intersecciones cr( G ) . Podemos suponer que dos aristas cualesquiera en este diagrama con un vértice común no se intersecan; de lo contrario, intercambiamos partes de las aristas hasta que la intersección y el número de intersecciones se reduce en uno. Así, podemos considerar que la intersección involucra cuatro vértices diferentes del grafo G . Como consecuencia, E [cr H ] = p 4 cr( G ) y obtenemos

Ahora, si ponemos p = 4 n / e < 1 (ya que asumimos que e > 4 n ), después de algunos cálculos algebraicos, obtenemos

Un ligero cambio en la argumentación anterior nos permite reemplazar 64 con 33.75 para e > 7.5 n [31] .

Véase también

Notas

  1. ↑ Turán, 1977 , p. 7-9.
  2. ↑ Bronfenbrenner, 1944 , pág. 283-289.
  3. ↑ Scheinerman, Wilf, 1994 , pág. 939-943.
  4. ↑ Pach, Sharir, 2009 , pág. 126-127.
  5. ↑ Zarankiewicz, 1954 , pág. 137-145.
  6. ↑ Guy, 1969 , pág. 63-69.
  7. ↑ 1 2 Guy, 1960 , pág. 68-72.
  8. ↑ Saaty, 1964 , pág. 688-690.
  9. ↑ Aichholzer .
  10. ↑ Kainen, 1968 , pág. 374-377.
  11. ↑ Klerk, Maharry, Pasechnik, Richter, Salazar, 2006 , p. 189-202.
  12. ↑ Schaefer, 2014 , pág. #DS21.
  13. ↑ Barat, Toth, 2009 .
  14. ↑ Garey y Johnson, 1983 , pág. 312-316.
  15. ↑ Hliněny, 2006 , p. 455-471.
  16. ↑ Cabello, Mohar, 2013 , pág. 1803-1829.
  17. ↑ Schaefer, 2010 , pág. 334-344.
  18. ↑ Grohe, 2005 , pág. 285-302.
  19. ↑ Kawarabayashi, Reed, 2007 , pág. 382-390.
  20. ↑ Even, Guha, Schieber, 2003 , p. 231-252.
  21. ↑ Número de cruce rectilíneo Archivado el 25 de junio de 2008 en Wayback Machine , Instituto de Ingeniería de Software de Graz, Universidad de Tecnología (2009).
  22. ↑ Weisstein, Eric W. "Gráfico de número de cruce cúbico más pequeño". De MathWorld: un recurso web de Wolfram. . Consultado el 20 de septiembre de 2020. Archivado desde el original el 19 de marzo de 2020.
  23. ↑ Exoo .
  24. ↑ Pegg, Exoo, 2009 .
  25. ↑ Ajtai, Chvátal, Newborn, Szemerédi, 1982 , p. 9-12.
  26. ↑ Leighton, 1983 .
  27. ↑ Ackermann, 2013 . Para obtener resultados anteriores con otras constantes, consulte Pach y Toph Pach, Tóth, 1997 , p. 427-439, Pach, Radchik, Tardos y Tof Pach, Radoičić, Tardos, Tóth, 2006 , p. 527-552
  28. ↑ Szekely, 1997 , pág. 353-358.
  29. ↑ Dey, 1998 , pág. 373-382.
  30. ↑ Pach, Spencer, Tóth, 2000 , p. 623-644.
  31. ↑ Ackermann, 2013 .

Literatura