En teoría de grafos , el número de cruces cr( G ) de un gráfico G es el número más bajo de cruces de aristas de un dibujo plano del gráfico G. Por ejemplo, una gráfica es plana si y sólo si su número de cruce es cero. Determinar el 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 comprendan el dibujo. [1]
El estudio de los números de cruces tuvo su origen en el problema de la fábrica de ladrillos de Turán , en el que Pál Turán pidió un plan de fábrica que minimizara el número de cruces entre las vías que conectaban los hornos de ladrillos con los lugares 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ó de forma independiente en sociología aproximadamente al mismo tiempo, en relación con la construcción de sociogramas . [3] La fórmula conjeturada por 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 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 matizaciones, 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]
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 a puntos disjuntos en el plano, y desde los bordes del gráfico a curvas que conectan sus dos puntos finales. No se debe asignar ningún vértice a una arista de la que no sea un punto final, y siempre que dos aristas tengan curvas que se intersequen (que no sean en un punto final compartido), sus intersecciones deben formar un conjunto finito de cruces adecuados, donde las dos curvas sean transversales . Un cruce se cuenta por separado para cada uno de estos puntos de cruce, para cada par de aristas que se cruzan. El número de cruces de un gráfico es entonces el mínimo, entre todos los 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 cruce definido anteriormente, estas restricciones no suponen ninguna diferencia, porque un dibujo de cruce mínimo no puede tener aristas con múltiples puntos de intersección. Si se cruzan dos bordes con un punto final compartido, 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 definiciones variantes del número de cruces que, por ejemplo, cuentan sólo el número de pares de aristas que se cruzan en lugar del número de cruces. [5]
En abril de 2015, se conocen números de cruce para muy pocas familias de gráficos. En particular, excepto por unos pocos casos iniciales, el número de cruces de gráficos completos, gráficos completos bipartitos y productos de ciclos sigue siendo desconocido, aunque ha habido algunos avances en los límites inferiores. [6]
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 carros llenos de ladrillos desde los hornos hasta los lugares de almacenamiento. La fábrica tenía vías desde cada horno hasta cada sitio de almacenamiento, y los vagones eran más difíciles de empujar en los puntos donde las vías se cruzaban, por lo que Turán se vio obligado a preguntarle al problema de su fábrica de ladrillos: ¿cómo pueden los hornos, los sitios de almacenamiento y las vías? ¿Se organizará para minimizar el número total de cruces? Matemáticamente, los hornos y los sitios de almacenamiento pueden formalizarse como los vértices de un grafo bipartito completo , con las pistas como sus aristas. El diseño de una 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ó solucionar 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]
El problema de determinar el número de cruce 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 sólo 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 enteras . La conjetura es que no puede haber mejor dibujo, 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 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 gráficos con número cromático n , el gráfico completo K n tiene el mínimo número de cruces. Es decir, si la fórmula conjeturada para el número de cruce del gráfico completo es correcta, entonces cada n -gráfico cromático tiene un número de cruce al menos igual a la misma fórmula. Ahora se sabe que la conjetura de Albertson se cumple para n ≤ 16 . [13]
Se conocen los gráficos cúbicos más pequeños con los números cruzados del 1 al 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 dos 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]
El ancho de 2/3 de bisección 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. La informática es NP-difícil. 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 , o se conoce una estimación del mismo. Además, esta desigualdad tiene aplicación algorítmica. Específicamente, Bhat y Leighton lo usaron (por primera vez) para derivar un límite superior en el número de cruces de bordes en un dibujo que se obtiene mediante un algoritmo de aproximación de divide y vencerás para computación . [19]
En general, determinar el número de cruce de un gráfico es difícil; Garey y Johnson demostraron en 1983 que se trata de un problema NP-difícil . [20] De hecho, el problema sigue siendo NP-difícil incluso cuando se limita a gráficos cúbicos [21] y a gráficos casi planos (gráficos que se vuelven planos después de eliminar un solo borde). [22] Un problema estrechamente relacionado, la determinación del número de cruce rectilíneo, está completo para la teoría existencial de los reales . [23]
En el lado positivo, existen algoritmos eficientes para determinar si el número de cruce 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 más grandes , como k = | V |/2 . También existen algoritmos de aproximación eficientes para aproximar gráficos 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 de cruces adicionales posibles. Estos algoritmos se utilizan en el proyecto de computación distribuida Rectilinear Crossing Number . [27]
Para un gráfico simple no dirigido G con n vértices y e aristas tales que e > 7 n, el número de cruce es siempre al menos
Esta relación entre aristas, vértices y el número de cruce fue descubierta de forma independiente por Ajtai , Chvátal , Newborn y Szemerédi , [28] y por Leighton. [18] Se conoce como desigualdad de números 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 con la peor constante de 64 . [28] [18]
La motivación de Leighton al estudiar los números cruzados fue las 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 la usó para demostrar los límites superiores de k geométrico - conjuntos . [31]
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 mayor en algunas gráficas. Se sabe que, en general, el número de cruce rectilíneo no puede estar limitado por una función del número de cruce. [32] Los números de cruce 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 7233 o 7234. cruces. El proyecto Rectilinear Crossing Number recopila más valores. [27]
Un gráfico tiene un número de cruce local k si se puede dibujar con un máximo de k cruces por arista, pero no menos. Las gráficas que se pueden dibujar con como máximo k cruces por arista también se denominan k -planares. [33]
Otras variantes del número de cruce incluyen el número de cruce por pares (el número mínimo de pares de aristas que se cruzan en cualquier dibujo) y el número de cruce impar (el número de pares de aristas 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. [34] [35]
La disposición de los temas en el diagrama, aunque en parte aleatoria, se determina en gran medida mediante prueba y error con el objetivo de minimizar el número de líneas que se cruzan.
