Número de cruce (teoría de grafos)

Menor número de cruces de aristas al dibujar un gráfico

Dibujo del gráfico de Heawood con tres cruces. Este es el número mínimo de cruces entre todos los dibujos de este gráfico, por lo que el gráfico tiene un número de cruces cr( G ) = 3 .

En teoría de grafos , el número de cruces cr( G ) de un grafo G es el número más bajo de cruces de aristas de un dibujo plano del grafo G . Por ejemplo, un grafo es plano si y solo si su número de cruces es cero. Determinar el número de cruces sigue siendo de gran importancia en el dibujo de grafos, ya que los estudios de usuarios han demostrado que dibujar grafos con pocos cruces hace que sea más fácil para las personas comprender el dibujo. ^[1]

El estudio de los números de cruce se originó en el problema de la fábrica de ladrillos de Turán , en el que Pál Turán pidió un plano de fábrica que minimizara el número de cruces entre las vías que conectaban los hornos de ladrillos con los sitios de almacenamiento. Matemáticamente, este problema se puede formalizar como preguntar por el número de cruce de un grafo bipartito completo . ^[2] El mismo problema surgió de forma independiente en sociología aproximadamente al mismo tiempo, en relación con la construcción de sociogramas . ^[3] La fórmula conjeturada de Turán para los números de cruce de grafos bipartitos completos sigue sin demostrarse, al igual que una fórmula análoga para los grafos completos .

La desigualdad del número de cruces establece que, para los grafos donde el número e de aristas es suficientemente mayor que el número n de vértices , el número de cruces es al menos proporcional a e ³ / n ² . Tiene aplicaciones en el diseño VLSI y la geometría de incidencia .

Sin más matizaciones, el número de cruce permite realizar dibujos en los que las aristas pueden estar representadas por curvas arbitrarias. Una variación de este concepto, el número de cruce rectilíneo , requiere que todas las aristas sean segmentos de línea recta y puede diferir del número de cruce. En particular, el número de cruce rectilíneo de un grafo completo es esencialmente el mismo que el número mínimo de cuadriláteros convexos determinado por un conjunto de n puntos en posición general. El problema de determinar este número está estrechamente relacionado con el problema del final feliz . ^[4]

Definiciones

Para los fines de definir el número de cruces, un dibujo de un grafo no dirigido es una aplicación de los vértices del grafo a puntos disjuntos en el plano, y de los bordes del grafo a curvas que conectan sus dos puntos finales. Ningún vértice debe ser aplicado a un borde del cual no es un punto final, y siempre que dos bordes tengan curvas que se intersequen (salvo en un punto final compartido) sus intersecciones deben formar un conjunto finito de cruces propios, donde las dos curvas sean transversales . Un cruce se cuenta por separado para cada uno de estos puntos de cruce, para cada par de bordes que se cruzan. El número de cruces de un grafo es entonces el mínimo, sobre todos esos dibujos, del número de cruces en un dibujo. ^[5]

Algunos autores añaden más restricciones a la definición de un dibujo, por ejemplo, que cada par de aristas tenga como máximo un punto de intersección (un punto final compartido o cruce). Para el número de cruces definido anteriormente, estas restricciones no hacen ninguna diferencia, porque un dibujo de cruce mínimo no puede tener aristas con múltiples puntos de intersección. Si dos aristas con un punto final compartido se cruzan, el dibujo se puede cambiar localmente en el punto de cruce, dejando el resto del dibujo sin cambios, para producir un dibujo diferente con un cruce menos. Y de manera similar, si dos aristas se cruzan dos o más veces, el dibujo se puede cambiar localmente en dos puntos de cruce para hacer un dibujo diferente con dos cruces menos. Sin embargo, estas restricciones son relevantes para las definiciones variantes del número de cruces que, por ejemplo, cuentan solo el número de pares de aristas que se cruzan en lugar del número de cruces. ^[5]

Casos especiales

A partir de abril de 2015, se conocen los números de cruces de muy pocas familias de grafos. En particular, a excepción de unos pocos casos iniciales, el número de cruces de grafos completos, grafos completos bipartitos y productos de ciclos sigue siendo desconocido, aunque se han producido algunos avances en los límites inferiores. ^[6]

Grafos bipartitos completos

Un dibujo óptimo de K _4,7 que muestra que el problema de la fábrica de ladrillos de Turán con 4 sitios de almacenamiento (puntos amarillos) y 7 hornos (puntos azules) requiere 18 cruces (puntos rojos)

Durante la Segunda Guerra Mundial , el matemático húngaro Pál Turán se vio obligado a trabajar en una fábrica de ladrillos, empujando vagones llenos de ladrillos desde los hornos hasta los lugares de almacenamiento. La fábrica tenía vías desde cada horno hasta cada lugar de almacenamiento, y los vagones eran más difíciles de empujar en los puntos donde las vías se cruzaban entre sí, a partir de lo cual Turán se vio obligado a plantear su problema de fábrica de ladrillos: ¿cómo se pueden organizar los hornos, los lugares de almacenamiento y las vías para minimizar el número total de cruces? Matemáticamente, los hornos y los lugares de almacenamiento se pueden formalizar como los vértices de un grafo bipartito completo , con las vías como sus aristas. El diseño de una fábrica se puede representar como un dibujo de este grafo, por lo que el problema se convierte en: ¿cuál es el número mínimo posible de cruces en un dibujo de un grafo bipartito completo ? ^[7]

Kazimierz Zarankiewicz intentó resolver el problema de la fábrica de ladrillos de Turán; ^[8] su prueba contenía un error, pero estableció un límite superior válido

${\displaystyle {\textrm {cr}}(K_{m,n})\leq \left\lfloor {\frac {n}{2}}\right\rfloor \left\lfloor {\frac {n-1}{2}}\right\rfloor \left\lfloor {\frac {m}{2}}\right\rfloor \left\lfloor {\frac {m-1}{2}}\right\rfloor }$

para el número de cruces del grafo bipartito completo K _m,n . Se ha conjeturado que este límite es el número óptimo de cruces para todos los grafos bipartitos completos. ^[9]

Gráficas completas y coloración de gráficas

El problema de determinar el número de cruces del grafo completo fue planteado por primera vez por Anthony Hill y apareció impreso en 1960. ^[10] Hill y su colaborador John Ernest eran dos artistas construccionistas fascinados por las matemáticas. No solo formularon este problema, sino que también originaron una fórmula conjetural para este número de cruces, que Richard K. Guy publicó en 1960. ^[10] Es decir, se sabe que siempre existe un dibujo con

${\displaystyle {\textrm {cr}}(K_{p})\leq {\frac {1}{4}}\left\lfloor {\frac {p}{2}}\right\rfloor \left\lfloor {\frac {p-1}{2}}\right\rfloor \left\lfloor {\frac {p-2}{2}}\right\rfloor \left\lfloor {\frac {p-3}{2}}\right\rfloor }$

cruces. Esta fórmula da valores de 1, 3, 9, 18, 36, 60, 100, 150 para p = 5, ..., 12 ; véase la secuencia A000241 en la Enciclopedia en línea de secuencias enteras . La conjetura es que no puede haber un mejor dibujo, de modo que esta fórmula da el número óptimo de cruces para los grafos completos. Thomas L. Saaty realizó una formulación independiente de la misma conjetura en 1964. ^[11]

Saaty verificó además que esta fórmula proporciona el número óptimo de cruces para p ≤ 10 y Pan y Richter demostraron que también es óptima para p = 11, 12. [ ^12]

La conjetura de Albertson , formulada por Michael O. Albertson en 2007, establece que, entre todos los grafos con número cromático n , el grafo completo K _n tiene el número mínimo de cruces. Es decir, si la fórmula conjeturada para el número de cruces del grafo completo es correcta, entonces cada grafo n -cromático tiene un número de cruces al menos igual a la misma fórmula . Ahora se sabe que la conjetura de Albertson es válida para n ≤ 16. ^[13]

Gráficas cúbicas

Se conocen los grafos cúbicos más pequeños con números de cruces 1–8 y 11 (secuencia A110507 en la OEIS ). El grafo cúbico de 1 cruce más pequeño es el grafo bipartito completo K _3,3 , con 6 vértices. El grafo cúbico de 2 cruces más pequeño es el grafo de Petersen , con 10 vértices. El grafo cúbico de 3 cruces más pequeño es el grafo de Heawood , con 14 vértices. El grafo cúbico de 4 cruces más pequeño es el grafo de Möbius-Kantor , con 16 vértices. El grafo cúbico de 5 cruces más pequeño es el grafo de Pappus , con 18 vértices. El grafo cúbico de 6 cruces más pequeño es el grafo de Desargues , con 20 vértices. Ninguno de los cuatro grafos cúbicos de 7 cruces, con 22 vértices, es bien conocido. ^[14] Los grafos cúbicos de 8 cruces más pequeños incluyen el grafo de Nauru y el grafo de McGee o grafo de jaula (3,7) , con 24 vértices. ^[15] Los grafos cúbicos de 11 cruces más pequeños incluyen el grafo de Coxeter con 28 vértices. ^[16]

En 2009, Pegg y Exoo conjeturaron que el grafo cúbico más pequeño con número de cruce 13 es el grafo de Tutte-Coxeter y el grafo cúbico más pequeño con número de cruce 170 es el grafo de Tutte de 12 jaulas . ^{[15] [17]}

Conexiones con el ancho de bisección

El ancho de bisección de 2/3 de un gráfico simple es el número mínimo de aristas cuya eliminación da como resultado una partición del conjunto de vértices en dos conjuntos separados de modo que ningún conjunto tenga más de vértices. El cálculo es NP-hard. Leighton demostró que , siempre que tenga grados de vértice acotados. ^[18] Esta desigualdad fundamental se puede utilizar para derivar un límite inferior asintótico para , cuando se conoce , o una estimación del mismo. Además, esta desigualdad tiene aplicación algorítmica. Específicamente, Bhat y Leighton la utilizaron (por primera vez) para derivar un límite superior en el número de cruces de aristas en un dibujo que se obtiene mediante un algoritmo de aproximación de divide y vencerás para calcular . ^[19] ${\displaystyle b(G)}$ ${\displaystyle G}$ ${\displaystyle 2n/3}$ ${\displaystyle b(G)}$ ${\displaystyle cr(G)+n=\Omega (b^{2}(G))}$ ${\displaystyle G}$ ${\displaystyle cr(G)}$ ${\displaystyle b(G)}$ ${\displaystyle cr(G)}$

Complejidad y aproximación

En general, determinar el número de cruces de un grafo es difícil; Garey y Johnson demostraron en 1983 que es un problema NP-difícil . ^[20] De hecho, el problema sigue siendo NP-difícil incluso cuando se restringe a grafos cúbicos ^[21] y a grafos casi planares (grafos que se vuelven planares después de eliminar una sola arista). ^[22] Un problema estrechamente relacionado, determinar el número de cruces rectilíneos, es completo para la teoría existencial de los números reales . ^[23]

En el lado positivo, hay algoritmos eficientes para determinar si el número de cruces es menor que una constante fija k . En otras palabras, el problema es manejable con parámetros fijos . ^{[24] [25]} Sigue siendo difícil para k mayores , como k = | V |/2 . También hay algoritmos de aproximación eficientes para aproximar en grafos de grado acotado ^[26] que utilizan el marco general y previamente desarrollado de Bhat y Leighton. ^[19] En la práctica, se utilizan algoritmos heurísticos , como el algoritmo simple que comienza sin aristas y agrega continuamente cada nueva arista de una manera que produce la menor cantidad posible de cruces adicionales. Estos algoritmos se utilizan en el proyecto de computación distribuida Rectilinear Crossing Number . ^[27] ${\displaystyle cr(G)+n}$

La desigualdad del número de cruce

Para un grafo simple no dirigido G con n vértices y e aristas tales que e > 7 n el número de cruces es siempre al menos

${\displaystyle \operatorname {cr} (G)\geq {\frac {e^{3}}{29n^{2}}}.}$

Esta relación entre aristas, vértices y número de cruce fue descubierta independientemente por Ajtai , Chvátal , Newborn y Szemerédi , ^[28] y por Leighton. ^[18] Se conoce como desigualdad del número de cruce o lema de cruce.

La constante 29 es la más conocida hasta la fecha, y se debe a Ackerman. ^[29] La constante 7 se puede reducir a 4 , pero a costa de reemplazar 29 por la peor constante de 64. [ ^{28] [18]}

La motivación de Leighton para estudiar los números cruzados fue para aplicaciones al diseño VLSI en informática teórica. ^[18] Más tarde, Székely también se dio cuenta de que esta desigualdad producía pruebas muy simples de algunos teoremas importantes en geometría de incidencia , como el teorema de Beck y el teorema de Szemerédi-Trotter , ^[30] y Tamal Dey lo utilizó para demostrar límites superiores en conjuntos k geométricos . ^[31]

Variaciones

Si se requiere que los bordes se dibujen como segmentos de línea recta, en lugar de curvas arbitrarias, entonces algunos gráficos necesitan más cruces. El número de cruces rectilíneos se define como el número mínimo de cruces de un dibujo de este tipo. Siempre es al menos tan grande como el número de cruces, y es mayor para algunos gráficos. Se sabe que, en general, el número de cruces rectilíneos no puede limitarse por una función del número de cruces. ^[32] Los números de cruces rectilíneos para K ₅ a K ₁₂ son 1, 3, 9, 19, 36, 62, 102, 153 , (A014540) y se conocen valores hasta K _{27 , con} K ₂₈ requiriendo 7233 o 7234 cruces. El proyecto Rectilinear Crossing Number recopila más valores. ^[27]

Un grafo tiene un número de cruces local k si se puede dibujar con un máximo de k cruces por arista, pero no menos. Los grafos que se pueden dibujar con un máximo de k cruces por arista también se denominan k -planares. ^[33]

Otras variantes del número de cruces incluyen el número de cruces por pares (el número mínimo de pares de aristas que se cruzan en cualquier dibujo) y el número de cruces impares (el número de pares de aristas que se cruzan un número impar de veces en cualquier dibujo). El número de cruces impares es como máximo igual al número de cruces por pares, que es como máximo igual al número de cruces. Sin embargo, por el teorema de Hanani-Tutte , siempre que uno de estos números sea cero, todos lo son. ^[5] Schaefer (2014, 2018) examina muchas de estas variantes. ^{[34] [35]}

Véase también

• Planarización , un gráfico planar formado al reemplazar cada cruce por un nuevo vértice
• Problema de tres utilidades , el acertijo que pregunta si K _3,3 se puede dibujar con 0 cruces

Referencias

1. Purchase, Helen C.; Cohen, Robert F.; James, Murray I. (1995). "Validando la estética del dibujo de grafos". En Brandenburg, Franz-Josef (ed.). Dibujo de grafos, Simposio sobre dibujo de grafos, GD '95, Passau, Alemania, 20-22 de septiembre de 1995, Actas . Apuntes de clase en informática. Vol. 1027. Springer. págs. 435–446. doi : 10.1007/BFb0021827 . ISBN. 978-3-540-60723-6..
2. Turán, P. (1977). "Una nota de bienvenida". Revista de teoría de grafos . 1 : 7–9. doi :10.1002/jgt.3190010105.
3. Bronfenbrenner, Urie (1944). "La presentación gráfica de datos sociométricos". Sociometría . 7 (3): 283–289. doi :10.2307/2785096. JSTOR  2785096. La disposición de los sujetos en el diagrama, aunque en parte es aleatoria, se determina en gran medida mediante ensayo y error con el objetivo de minimizar el número de líneas que se cruzan.
4. Scheinerman, Edward R. ; Wilf, Herbert S. (1994). "El número de cruces rectilíneos de un gráfico completo y el "problema de los cuatro puntos" de Sylvester de probabilidad geométrica". American Mathematical Monthly . 101 (10): 939–943. doi :10.2307/2975158. JSTOR  2975158.
5. Pach, J. ; Tóth, G. (1998). "¿Cuál es, en cualquier caso, el número de cruce?". Actas del 39.º Simposio anual sobre fundamentos de la informática (FOCS 1998) . págs. 617–626. doi :10.1109/SFCS.1998.743512..
6. de Klerk, E.; Maharry, J.; Pasechnik, DV; Richter, B.; Salazar, G. (2006). "Límites mejorados para los números de cruce de Km,n y Kn". Revista SIAM de Matemáticas Discretas . 20 (1): 189–202. arXiv : math/0404142 . doi :10.1137/S0895480104442741. S2CID  1509054.
7. Pach, János ; Sharir, Micha (2009). "5.1 Cruces: el problema de la fábrica de ladrillos". Geometría combinatoria y sus aplicaciones algorítmicas: las conferencias de Alcalá . Encuestas y monografías matemáticas. Vol. 152. American Mathematical Society . págs. 126–127.
8. Zarankiewicz, K. (1954). "Sobre un problema de P. Turán sobre los gráficos". Fundamentos Mathematicae . 41 : 137-145. doi : 10.4064/fm-41-1-137-145 .
9. Guy, Richard K. (1969). "La decadencia y caída del teorema de Zarankiewicz". Técnicas de demostración en teoría de grafos (Proc. Second Ann Arbor Graph Theory Conf., Ann Arbor, Michigan, 1968) . Academic Press, Nueva York. págs. 63–69. MR  0253931..
10. Guy, RK (1960). "Un problema combinatorio". Nabla (Boletín de la Sociedad Matemática Malaya) . 7 : 68–72.
11. Saaty, TL (1964). "El número mínimo de intersecciones en grafos completos". Actas de la Academia Nacional de Ciencias de los Estados Unidos de América . 52 (3): 688–690. Bibcode :1964PNAS...52..688S. doi : 10.1073/pnas.52.3.688 . PMC 300329 . PMID  16591215. 
12. Pan, Shengjun; Richter, R. Bruce (2007). "El número de cruce de K ₁₁ es 100 ". Journal of Graph Theory . 56 (2): 128–134. doi :10.1002/jgt.20249. MR  2350621. S2CID  37155969..
13. Barát, János; Tóth, Géza (2009). "Hacia la conjetura de Albertson". arXiv : 0909.0413 [matemáticas.CO].
14. Weisstein, Eric W. "Gráfico que cruza números". MathWorld .
15. Pegg, ET ; Exoo, G. (2009). "Gráficos de números cruzados". Mathematica Journal . 11 (2). doi : 10.3888/tmj.11.2-2 .
16. Clancy, Kieran; Haythorpe, Michael; Newcombe, Alex; Pegg, Ed Jr. (2020). "No hay grafos cúbicos en 26 vértices con número de cruces 10 u 11". Graphs and Combinatorics . 36 (6): 1713–1721. arXiv : 1804.10336 . doi :10.1007/s00373-020-02204-6. MR  4163409. S2CID  253889498.
17. Exoo, G. "Dibujos rectilíneos de gráficos famosos".
18. Leighton, T. (1983). Problemas de complejidad en VLSI . Serie Fundamentos de la informática. Cambridge, MA: MIT Press.
19. Bhatt, Sandeep N.; Leighton, Frank Thomson (1984-04-01). "Un marco para resolver problemas de diseño de grafos VLSI". Revista de Ciencias de la Computación y de Sistemas . 28 (2): 300–343. doi :10.1016/0022-0000(84)90071-0. ISSN  0022-0000.
20. Garey, MR ; Johnson, DS (1983). "El número de cruce es NP-completo". Revista SIAM sobre métodos algebraicos y discretos . 4 (3): 312–316. doi :10.1137/0604033. MR  0711340.
21. Hliněný, P. (2006). "El cruce de números es difícil para los grafos cúbicos". Journal of Combinatorial Theory . Serie B. 96 (4): 455–471. doi : 10.1016/j.jctb.2005.09.009 . MR  2232384.
22. Cabello S. y Mohar B. (2013). "Agregar una arista a los grafos planares dificulta el número de cruces y la 1-planaridad". Revista SIAM de Computación . 42 (5): 1803–1829. arXiv : 1203.5944 . doi :10.1137/120872310. S2CID  6535755.
23. Schaefer, Marcus (2010). Complejidad de algunos problemas geométricos y topológicos (PDF) . Graph Drawing, 17th International Symposium, GS 2009, Chicago, IL, EE. UU., septiembre de 2009, Documentos revisados . Lecture Notes in Computer Science. Vol. 5849. Springer-Verlag. págs. 334–344. doi : 10.1007/978-3-642-11805-0_32 . ISBN . 978-3-642-11804-3..
24. Grohe, M. (2005). "Cálculo de números cruzados en tiempo cuadrático". Revista de Ciencias de la Computación y de Sistemas . 68 (2): 285–302. arXiv : cs/0009010 . doi :10.1016/j.jcss.2003.07.008. MR  2059096.
25. Kawarabayashi, Ken-ichi ; Reed, Bruce (2007). Cálculo de números de cruce en tiempo lineal . Actas del 29.° Simposio Anual de la ACM sobre Teoría de la Computación . págs. 382–390. doi :10.1145/1250790.1250848. ISBN 978-1-59593-631-8.
26. Even, Guy; Guha, Sudipto; Schieber, Baruch (2003). "Aproximaciones mejoradas de cruces en dibujos de gráficos y áreas de diseño VLSI". Revista SIAM de Computación . 32 (1): 231–252. doi :10.1137/S0097539700373520.
27. Oswin Aichholzer. "Proyecto de número de cruce rectilíneo". Archivado desde el original el 30 de diciembre de 2012., y el número de cruce rectilíneo en el Instituto de Tecnología de Software de la Universidad Tecnológica de Graz (2009).
28. Ajtai, M. ; Chvátal, V. ; Newborn, M.; Szemerédi, E. (1982). Subgrafos sin cruces . Teoría y práctica de la combinatoria. Estudios matemáticos de Holanda Septentrional. Vol. 60. págs. 9–12. MR  0806962.
29. Ackerman, Eyal (2013). "Sobre grafos topológicos con un máximo de cuatro cruces por arista" (PDF) . Archivado desde el original (PDF) el 14 de julio de 2014.
30. Székely, LA (1997). "Números cruzados y problemas de Erdős difíciles en geometría discreta". Combinatoria, probabilidad y computación . 6 (3): 353–358. doi :10.1017/S0963548397002976. MR  1464571. S2CID  36602807.
31. Dey, TK (1998). "Límites mejorados para conjuntos k planares y problemas relacionados". Geometría discreta y computacional . 19 (3): 373–382. doi : 10.1007/PL00009354 . MR  1608878.
32. Bienstock, Daniel; Dean, Nathaniel (julio de 1993). "Límites para números de cruce rectilíneos". Journal of Graph Theory . 17 (3): 333–348. doi :10.1002/jgt.3190170308.
33. Ringel, Gerhard (1965). "Ein Sechsfarbenproblem auf der Kugel". Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg (en alemán). 29 (1–2): 107–117. doi :10.1007/BF02996313. SEÑOR  0187232. S2CID  123286264.
34. Schaefer, Marcus (2014). "El número de cruce de grafos y sus variantes: una encuesta". The Electronic Journal of Combinatorics . 1000 . DS21. doi : 10.37236/2713 .
35. Schaefer, Marcus (2018). Cruce de números de gráficos . CRC Press.