Número de cruce (teoría de grafos) - Crossing number (graph theory)

Un 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 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.

El estudio de los números 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 . El mismo problema surgió independientemente en sociología aproximadamente al mismo tiempo, en relación con la construcción de sociogramas . La fórmula conjeturada de Turán para los números de cruce de gráficos bipartitos completos sigue sin probarse, 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 ³ / n ² . 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 .

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.

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.

Casos especiales

En abril de 2015, se conocen números cruzados para muy pocas familias de gráficos. En particular, excepto en 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.

Gráficos 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 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 el problema de su 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 ?

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

${\ 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 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.

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. 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. 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 ; 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.

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 .

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 se cumple para n ≤ 16 .

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. 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. Los gráficos cúbicos de 11 cruces más pequeños incluyen el gráfico de Coxeter con 28 vértices.

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 .

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 . De hecho, el problema sigue siendo NP-difícil incluso cuando se restringe a gráficos cúbicos y gráficos casi planos (gráficos que se vuelven planos después de eliminar un solo borde). Un problema estrechamente relacionado, la determinación del número de cruce rectilíneo, es completo para la teoría existencial de los reales .

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 . 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. 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 el menor número posible de cruces adicionales. Estos algoritmos se utilizan en el proyecto de computación distribuida Rectilinear Crossing Number .

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

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

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 , y por Leighton . 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. La constante 7 se puede bajar a 4 , pero a expensas de reemplazar 29 por la peor constante de 64 .

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. Más tarde, Székely también se dio cuenta de que esta desigualdad dio pruebas muy sencillas de algunos teoremas importantes en la geometría de incidencia , tales como el teorema de Beck y el teorema de Szemerédi-Trotter , y Tamal Dey lo utilizó para probar los límites superiores sobre geométricas k conjuntos- .

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 ₅ a K ₁₂ son 1, 3, 9, 19, 36, 62, 102, 153 , ( A014540 ) y se conocen valores hasta K ₂₇ , y K ₂₈ requiere cruces 7233 o 7234. El proyecto Rectilinear Crossing Number recopila más valores.

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.

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. Schaefer ( 2014 , 2018 ) analiza muchas de estas variantes.

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