En la teoría de grafos , el número de cruce cr ( G ) de un grafo G es el número más bajo de los pasos de borde de un plano de dibujo de la gráfica G . Por ejemplo, una gráfica es plana si y solo si su número de cruce es cero. La determinación del número de cruces sigue siendo de gran importancia en el dibujo de gráficos , ya que los estudios de usuarios han demostrado que dibujar gráficos con pocos cruces facilita que las personas entiendan el dibujo. [1]
El estudio del número de cruces se originó en el problema de la fábrica de ladrillos de Turán , en el que Pál Turán solicitó un plan de fábrica que minimizara el número de cruces entre vías que conectan los hornos de ladrillos con los sitios de almacenamiento. Matemáticamente, este problema se puede formalizar pidiendo el número de cruce de un gráfico bipartito completo , [2] El mismo problema surgió independientemente en sociología aproximadamente al mismo tiempo, en conexión con la construcción de sociogramas . [3] La fórmula conjeturada de Turán para los números de cruce de gráficos bipartitos completos no se ha probado, al igual que una fórmula análoga para los gráficos completos .
La desigualdad del número de cruce establece que, para gráficos donde el número e de aristas es suficientemente mayor que el número n de vértices , el número de cruce es al menos proporcional a e 3 / n 2 . Tiene aplicaciones en diseño VLSI y geometría de incidencia .
Sin más reservas, el número de cruce permite dibujos en los que los bordes pueden representarse mediante curvas arbitrarias. Una variación de este concepto, el número de cruce rectilíneo , requiere que todos los bordes sean segmentos de línea recta y puede diferir del número de cruce. En particular, el número de cruces rectilíneos de un gráfico 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
A los efectos de definir el número de cruce, un dibujo de un gráfico no dirigido es un mapeo desde los vértices del gráfico hasta los puntos disjuntos en el plano y desde los bordes del gráfico hasta las curvas que conectan sus dos puntos finales. Ningún vértice debe mapearse en una arista de la que no sea un punto final, y siempre que dos aristas tengan curvas que se crucen (excepto en un punto final compartido), sus intersecciones deben formar un conjunto finito de cruces adecuados, donde las dos curvas son 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 gráfico es entonces el mínimo, sobre todos esos dibujos, del número de cruces en un dibujo. [5]
Algunos autores agregan más restricciones a la definición de un dibujo, por ejemplo, que cada par de bordes tiene como máximo un punto de intersección (un punto final o cruce compartido). Para el número de cruce como se definió anteriormente, estas restricciones no hacen ninguna diferencia, porque un dibujo de cruce mínimo no puede tener bordes con múltiples puntos de intersección. Si dos bordes 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 bordes 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 bordes que se cruzan en lugar del número de cruces. [5]
Casos especiales
En abril de 2015, se conocen números cruzados para muy pocas familias de gráficos. En particular, a excepción de unos pocos casos iniciales, el número de cruces de gráficos completos, gráficos completos bipartitos y productos de ciclos siguen siendo desconocidos, aunque ha habido algunos avances en los límites inferiores. [6]
Gráficos bipartitos completos
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 carretas llenas de ladrillos de los hornos a los lugares de almacenamiento. La fábrica tenía pistas de cada horno a cada sitio de almacenamiento, y los vagones eran más difíciles de empujar en los puntos donde las pistas se cruzaban, de donde Turán fue llevado a preguntarle a su problema de fábrica de ladrillos: ¿cómo pueden los hornos, los sitios de almacenamiento y las pistas estar dispuesto para minimizar el número total de cruces? Matemáticamente, los hornos y los sitios de almacenamiento se pueden formalizar como los vértices de un gráfico bipartito completo , con las pistas como sus bordes. Un diseño de fábrica se puede representar como un dibujo de este gráfico, por lo que el problema es: ¿cuál es el número mínimo posible de cruces en un dibujo de un gráfico 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 de
para el número de cruce del gráfico bipartito completo K m, n . Se ha conjeturado que este límite es el número óptimo de cruces para todos los gráficos bipartitos completos. [9]
Gráficos completos y coloración de gráficos
El problema de determinar el número de cruces del gráfico 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 cruce, que Richard K. Guy publicó en 1960. [10] Es decir, se sabe que siempre existe un dibujo con
cruces. Esta fórmula da valores de 1, 3, 9, 18, 36, 60, 100, 150 para p = 5, ..., 12 ; consulte la secuencia A000241 en la Enciclopedia en línea de secuencias de números enteros . La conjetura es que no puede haber un dibujo mejor, por lo que esta fórmula da el número óptimo de cruces para las gráficas completas. Thomas L. Saaty hizo una formulación independiente de la misma conjetura en 1964. [11]
Saaty verificó además que esta fórmula da el número óptimo de cruces para p ≤ 10 y Pan y Richter demostraron que también es óptimo para p = 11, 12 . [12]
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 cruces. Es decir, si la fórmula conjeturada para el número de cruces del gráfico completo es correcta, entonces cada gráfico 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áficos cúbicos
Se conocen las gráficas cúbicas más pequeñas con números de cruce 1–8 y 11 (secuencia A110507 en la OEIS ). El gráfico cúbico de 1 cruce más pequeño es el gráfico bipartito completo K 3,3 , con 6 vértices. El gráfico cúbico de 2 cruces más pequeño es el gráfico de Petersen , con 10 vértices. El gráfico cúbico de 3 cruces más pequeño es el gráfico de Heawood , con 14 vértices. El gráfico cúbico de 4 cruces más pequeño es el gráfico de Möbius-Kantor , con 16 vértices. El gráfico cúbico de 5 cruces más pequeño es el gráfico de Pappus , con 18 vértices. El gráfico cúbico de 6 cruces más pequeño es el gráfico de Desargues , con 20 vértices. Ninguno de los cuatro gráficos cúbicos de 7 cruces, con 22 vértices, es bien conocido. [14] Los gráficos cúbicos de 8 cruces más pequeños incluyen el gráfico de Nauru y el gráfico de McGee o gráfico de jaula (3,7) , con 24 vértices. [15] Los gráficos cúbicos de 11 cruces más pequeños incluyen el gráfico de Coxeter con 28 vértices. [dieciséis]
En 2009, Pegg y Exoo conjeturaron que el gráfico cúbico más pequeño con el número de cruce 13 es el gráfico de Tutte-Coxeter y el gráfico cúbico más pequeño con el número de cruce 170 es el de 12 jaulas de Tutte . [15] [17]
Complejidad y aproximación
En general, es difícil determinar el número de cruces de un gráfico; Garey y Johnson demostraron en 1983 que es un problema NP-difícil . [18] De hecho, el problema sigue siendo NP-hard incluso cuando se restringe a gráficas cúbicas [19] ya gráficas casi planas (gráficas que se vuelven planas después de eliminar un solo borde). [20] Un problema estrechamente relacionado, la determinación del número de cruce rectilíneo, está completo para la teoría existencial de los reales . [21]
En el lado positivo, existen algoritmos eficientes para determinar si el número de cruce es menor que una constante k fija . En otras palabras, el problema es manejable con parámetros fijos . [22] [23] Sigue siendo difícil para k más grandes , como k = | V | / 2 . También existen algoritmos de aproximación eficientes para aproximar cr ( G ) en gráficos de grado acotado. [24] En la práctica , se utilizan algoritmos heurísticos , como el algoritmo simple que comienza sin bordes y agrega continuamente cada nuevo borde de una manera que produce la menor cantidad de cruces adicionales posibles. Estos algoritmos se utilizan en el proyecto de computación distribuida Rectilinear Crossing Number . [25]
La desigualdad del número de cruce
Para un grafo simple no dirigido G con n vértices ye aristas tales que e > 7 n el número de cruce es siempre al menos
Esta relación entre los bordes, los vértices y el número de cruce fue descubierta de forma independiente por Ajtai , Chvátal , Newborn y Szemerédi , [26] y por Leighton . [27] Se conoce como desigualdad de números cruzados o lema cruzado.
La constante 29 es la más conocida hasta la fecha y se debe a Ackerman. [28] La constante 7 se puede reducir a 4 , pero a expensas de reemplazar 29 con la peor constante de 64 . [26] [27]
La motivación de Leighton al estudiar los números cruzados fue la aplicación al diseño de VLSI en la informática teórica. [27] Más tarde, Székely también se dio cuenta de que esta desigualdad producía demostraciones muy simples de algunos teoremas importantes en la geometría de incidencia , como el teorema de Beck y el teorema de Szemerédi-Trotter , [29] y Tamal Dey lo usó para demostrar los límites superiores de la geometría k - conjuntos . [30]
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 cruce y es más grande para algunos gráficos. Los números de cruces rectilíneos para K 5 a K 12 son 1, 3, 9, 19, 36, 62, 102, 153 , ( A014540 ) y se conocen valores hasta K 27 , y K 28 requiere cruces 7233 o 7234. El proyecto Rectilinear Crossing Number recopila más valores. [25]
Un gráfico tiene un número de cruce local k si se puede dibujar con un máximo de k cruces por borde, pero no menos. Los gráficos que se pueden dibujar con un máximo de k cruces por borde también se denominan k -planar. [31]
Otras variantes del número de cruce incluyen el número de cruce por pares (el número mínimo de pares de bordes que se cruzan en cualquier dibujo) y el número de cruce impar (el número de pares de bordes que se cruzan un número impar de veces en cualquier dibujo). El número de cruce impar es como máximo igual al número de cruce por pares, que es como máximo igual al número de cruce. Sin embargo, según el teorema de Hanani-Tutte , siempre que uno de estos números es cero, todos lo son. [5] Schaefer ( 2014 , 2018 ) analiza muchas de estas variantes. [32] [33]
Ver también
- Planarización , un gráfico plano formado al reemplazar cada cruce por un nuevo vértice
- Problema de tres utilidades , el rompecabezas que pregunta si K 3,3 se puede dibujar con 0 cruces
Referencias
- ^ Compra, Helen C .; Cohen, Robert F .; James, Murray I. (1995). "Validación de la estética del dibujo de gráficos". En Brandeburgo, Franz-Josef (ed.). Dibujo gráfico, Simposio sobre dibujo gráfico, GD '95, Passau, Alemania, 20-22 de septiembre de 1995, Actas . Apuntes de conferencias en Ciencias de la Computación. 1027 . Saltador. págs. 435–446. doi : 10.1007 / BFb0021827 ..
- ^ Turán, P. (1977). "Una nota de bienvenida". Revista de teoría de grafos . 1 : 7-9. doi : 10.1002 / jgt.3190010105 .
- ^ 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 es aleatoria en parte, está determinada en gran medida por ensayo y error con el objetivo de minimizar el número de líneas que se cruzan.
- ^ Scheinerman, Edward R .; Wilf, Herbert S. (1994). "El número de cruce rectilíneo de una gráfica completa y el" problema de cuatro puntos "de probabilidad geométrica de Sylvester. American Mathematical Monthly . 101 (10): 939–943. doi : 10.2307 / 2975158 . JSTOR 2975158 .
- ^ a b c Pach, J .; Tóth, G. (1998). "¿Qué número de cruce es, de todos modos?". Actas del 39º Simposio Anual sobre Fundamentos de las Ciencias de la Computación (FOCS 1998) . págs. 617–626. doi : 10.1109 / SFCS.1998.743512 ..
- ^ de Klerk, E .; Maharry, J .; Pasechnik, DV; Richter, B .; Salazar, G. (2006). "Límites mejorados para los números de cruce de K m, n y K n " . Revista SIAM de Matemática Discreta . 20 (1): 189–202. arXiv : matemáticas / 0404142 . doi : 10.1137 / S0895480104442741 . S2CID 1509054 .
- ^ 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. 152 . Sociedad Matemática Estadounidense . págs. 126-127.
- ^ Zarankiewicz, K. (1954). "Sobre un problema de P. Turán en cuanto a gráficos" . Fundamenta Mathematicae . 41 : 137-145. doi : 10.4064 / fm-41-1-137-145 .
- ^ Guy, Richard K. (1969). "El declive y caída del teorema de Zarankiewicz". Técnicas de prueba en teoría de grafos (Proc. Segunda Conf. Teoría de Grafos de Ann Arbor, Ann Arbor, Michigan, 1968) . Academic Press, Nueva York. págs. 63–69. Señor 0253931 ..
- ^ a b Guy, RK (1960). "Un problema combinatorio". Nabla (Boletín de la Sociedad Matemática Malaya) . 7 : 68–72.
- ^ Saaty, TL (1964). "El número mínimo de intersecciones en gráficos completos" . Actas de la Academia Nacional de Ciencias de los Estados Unidos de América . 52 (3): 688–690. Código Bibliográfico : 1964PNAS ... 52..688S . doi : 10.1073 / pnas.52.3.688 . PMC 300329 . PMID 16591215 .
- ^ Pan, Shengjun; Richter, R. Bruce (2007). "El número de cruce de K 11 es 100 ". Revista de teoría de grafos . 56 (2): 128-134. doi : 10.1002 / jgt.20249 . Señor 2350621 ..
- ^ Barát, János; Tóth, Géza (2009). "Hacia la conjetura de Albertson". arXiv : 0909.0413 [ math.CO ].
- ^ Weisstein, Eric W. "Graph Crossing Number" . MathWorld .
- ^ a b Pegg, ET ; Exoo, G. (2009). "Gráficos de números de cruce". Revista Mathematica . 11 (2). doi : 10.3888 / tmj.11.2-2 .
- ^ Haythorpe, Michael; Newcombe, Alex (2018), No hay gráficos cúbicos en 26 vértices con el número de cruce 11 , arXiv : 1804.10336
- ^ Exoo, G. "Dibujos rectilíneos de gráficos famosos" .
- ^ Garey, MR ; Johnson, DS (1983). "El número de cruce es NP-completo". Revista SIAM de Métodos Algebraicos y Discretos . 4 (3): 312–316. doi : 10.1137 / 0604033 . Señor 0711340 .
- ^ Hliněný, P. (2006). "Cruzar el número es difícil para los gráficos cúbicos". Revista de teoría combinatoria . Serie B. 96 (4): 455–471. doi : 10.1016 / j.jctb.2005.09.009 . Señor 2232384 .
- ^ Cabello S. y Mohar B. (2013). "Agregar un borde a los gráficos planos dificulta el cruce de números y 1-planaridad". Revista SIAM de Computación . 42 (5): 1803–1829. arXiv : 1203.5944 . doi : 10.1137 / 120872310 . S2CID 6535755 .
- ^ Schaefer, Marcus (2010). Complejidad de algunos problemas geométricos y topológicos (PDF) . Dibujo gráfico, 17º Simposio Internacional, GS 2009, Chicago, IL, EE. UU., Septiembre de 2009, artículos revisados . Apuntes de conferencias en Ciencias de la Computación. 5849 . Springer-Verlag. págs. 334–344. doi : 10.1007 / 978-3-642-11805-0_32 . ISBN 978-3-642-11804-3..
- ^ Grohe, M. (2005). "Cálculo de números de cruce en tiempo cuadrático". Revista de Ciencias de la Computación y Sistemas . 68 (2): 285-302. arXiv : cs / 0009010 . doi : 10.1016 / j.jcss.2003.07.008 . Señor 2059096 .
- ^ Kawarabayashi, Ken-ichi ; Reed, Bruce (2007). Calcular el número de cruce en tiempo lineal . Actas del 29º Simposio Anual ACM sobre Teoría de la Computación . págs. 382–390. doi : 10.1145 / 1250790.1250848 . ISBN 978-1-59593-631-8.
- ^ Incluso, Guy; Guha, Sudipto; Schieber, Baruch (2003). "Aproximaciones mejoradas de cruces en dibujos gráficos y áreas de diseño VLSI". Revista SIAM de Computación . 32 (1): 231–252. doi : 10.1137 / S0097539700373520 .
- ^ a b Oswin Aichholzer. "Proyecto Rectilinear Crossing Number" . Archivado desde el original el 30 de diciembre de 2012.y Rectilinear Crossing Number en el Instituto de Tecnología de Software de Graz, Universidad de Tecnología (2009).
- ^ a b Ajtai, M .; Chvátal, V .; Recién nacido, M .; Szemerédi, E. (1982). Subgrafos libres de cruces . Teoría y práctica de la combinatoria. Estudios de Matemáticas de Holanda Septentrional. 60 . págs. 9-12. Señor 0806962 .
- ^ a b c Leighton, T. (1983). Problemas de complejidad en VLSI . Serie Fundamentos de la Computación. Cambridge, MA: MIT Press.
- ^ Ackerman, Eyal (2013). "Sobre gráficos topológicos con un máximo de cuatro cruces por borde" (PDF) . Archivado desde el original (PDF) el 14 de julio de 2014.
- ^ Székely, LA (1997). "Cruce de números y problemas duros de Erd hards en geometría discreta". Combinatoria, Probabilidad y Computación . 6 (3): 353–358. doi : 10.1017 / S0963548397002976 . Señor 1464571 .
- ^ Dey, TK (1998). "Límites mejorados para conjuntos k planos y problemas relacionados" . Geometría discreta y computacional . 19 (3): 373–382. doi : 10.1007 / PL00009354 . Señor 1608878 .
- ^ 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 .
- ^ Schaefer, Marcus (2014). "El número de cruce del gráfico y sus variantes: una encuesta" . La Revista Electrónica de Combinatoria . DS21.
- ^ Schaefer, Marcus (2018). Cruce de números de gráficos . Prensa CRC.