En las matemáticas del dibujo de grafos , el problema de la fábrica de ladrillos de Turán pide el número mínimo de cruces en un dibujo de un grafo bipartito completo . El problema recibe su nombre de Pál Turán , quien lo formuló mientras se veía obligado a trabajar en una fábrica de ladrillos durante la Segunda Guerra Mundial. [1]
Se ha conjeturado que un método de dibujo descubierto por Kazimierz Zarankiewicz da la respuesta correcta para cada grafo bipartito completo, y la afirmación de que esto es cierto se conoce como la conjetura del número de cruce de Zarankiewicz . La conjetura permanece abierta, con solo algunos casos especiales resueltos. [2]
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 que unían cada horno con cada lugar de almacenamiento, y era más difícil empujar los vagones en los puntos donde las vías se cruzaban. Turán se inspiró en esta situación para preguntarse cómo se podría rediseñar la fábrica para minimizar el número de cruces entre estas vías. [1]
Matemáticamente, este problema se puede formalizar como pedir un dibujo gráfico de un grafo bipartito completo , cuyos vértices representan hornos y lugares de almacenamiento, y cuyos bordes representan las vías desde cada horno hasta cada lugar de almacenamiento. El grafo debe dibujarse en el plano con cada vértice como un punto, cada borde como una curva que conecta sus dos puntos finales y ningún vértice colocado sobre un borde al que no sea incidente. Se cuenta un cruce siempre que dos bordes que están disjuntos en el grafo tienen una intersección no vacía en el plano. La pregunta es entonces, ¿cuál es el número mínimo de cruces en un dibujo de este tipo? [2] [3]
La formulación de Turán de este problema es a menudo reconocida como uno de los primeros estudios de los números cruzados de grafos . [4] (Otra formulación independiente del mismo concepto ocurrió en sociología, en métodos para dibujar sociogramas , [5] y un rompecabezas mucho más antiguo, el problema de las tres utilidades , puede verse como un caso especial del problema de la fábrica de ladrillos con tres hornos y tres instalaciones de almacenamiento. [6] ) Los números cruzados han ganado desde entonces mayor importancia, como un objeto central de estudio en el dibujo de grafos [7] y como una herramienta importante en el diseño VLSI [8] y la geometría discreta . [9]
Tanto Zarankiewicz como Kazimierz Urbanik vieron a Turán hablar sobre el problema de la fábrica de ladrillos en diferentes charlas en Polonia en 1952, [3] y publicaron de forma independiente intentos de solución del problema, con fórmulas equivalentes para el número de cruces. [10] [11] Como ambos demostraron, siempre es posible dibujar el grafo bipartito completo K m,n (un grafo con m vértices en un lado, n vértices en el otro lado y mn aristas que conectan los dos lados) con un número de cruces igual a
La construcción es sencilla: se colocan m vértices en el eje x del plano, evitando el origen , con un número igual o casi igual de puntos a la izquierda y a la derecha del eje y . De manera similar, se colocan n vértices en el eje y del plano, evitando el origen, con un número igual o casi igual de puntos por encima y por debajo del eje x . Luego, se conecta cada punto del eje x mediante un segmento de línea recta a cada punto del eje y . [3]
Sin embargo, sus pruebas de que esta fórmula es óptima, es decir, que no puede haber dibujos con menos cruces, eran erróneas. La brecha no fue descubierta hasta once años después de su publicación, casi simultáneamente por Gerhard Ringel y Paul Kainen . [12] Sin embargo, se conjetura que la fórmula de Zarankiewicz y Urbanik es óptima. Esto ha llegado a conocerse como la conjetura del número de cruces de Zarankiewicz. Aunque se sabe que algunos casos especiales de ella son ciertos, el caso general permanece abierto. [2]
Como K m,n y K n,m son isomorfos, basta considerar el caso en que m ≤ n . Además, para m ≤ 2 la construcción de Zarankiewicz no da cruces, lo que por supuesto no se puede superar. Por lo tanto, los únicos casos no triviales son aquellos para los que m y n son ambos ≥ 3 .
El intento de Zarankiewicz de demostrar la conjetura, aunque no es válida para el caso general de K m , n , funciona para el caso m = 3 . Desde entonces se ha extendido a otros valores pequeños de m , y se sabe que la conjetura de Zarankiewicz es verdadera para los grafos bipartitos completos K m,n con m ≤ 6 . [13] También se sabe que la conjetura es verdadera para K 7,7 , K 7,8 y K 7,9 . [14] Si existe un contraejemplo, es decir, un grafo K m,n que requiere menos cruces que el límite de Zarankiewicz, entonces en el contraejemplo más pequeño tanto m como n deben ser impares. [13]
Para cada elección fija de m , la verdad de la conjetura para todo K m,n puede verificarse probando solo un número finito de elecciones de n . [15] De manera más general, se ha demostrado que cada grafo bipartito completo requiere un número de cruces que es (para grafos suficientemente grandes) al menos el 83% del número dado por el límite de Zarankiewicz. Cerrar la brecha entre este límite inferior y el límite superior sigue siendo un problema abierto. [16]
Si se requiere que los bordes se dibujen como segmentos de línea recta, en lugar de curvas arbitrarias, entonces algunos grafos necesitan más cruces de los que necesitarían si se dibujaran con bordes curvos. Sin embargo, el límite superior establecido por Zarankiewicz para el número de cruces de grafos bipartitos completos se puede lograr utilizando solo bordes rectos. Por lo tanto, si la conjetura de Zarankiewicz es correcta, entonces los grafos bipartitos completos tienen un número de cruces rectilíneos igual a su número de cruces. [17]
La disposición de los sujetos en el diagrama, aunque en parte aleatoria, está determinada en gran medida por ensayo y error con el objetivo de minimizar el número de líneas que se cruzan.
