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 3 / n 2 . 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]
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]
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]
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
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]
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
cruces. Esta fórmula da valores de 1, 3, 9, 18, 36, 60, 100, 150, 225, 315 para p = 5, ..., 14 ; 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]
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]
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]
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]
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
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]
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 5 a K 12 son 1, 3, 9, 19, 36, 62, 102, 153 , (A014540) y se conocen valores hasta K 27 , con K 28 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]
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.