Número de cruce (teoría de grafos)

Un diagrama del grafo de Heawood con tres cruces. Este es el mínimo número de cruces entre todos los diagramas de este grafo, por lo que el grafo tiene número de cruce cr(G) = 3.

En teoría de grafos, el número de cruce cr(G), también llamado número de cruzamiento, de un grafo G es el menor número de cruces de aristas en un diagrama plano del grafo G. Por ejemplo, un grafo es plano si y solo si su número de cruce es cero.

El estudio de los números de cruce tuvo su origen en el problema de la fábrica de ladrillos de Turán, en el cual Pál Turán buscó determinar el número de cruce del grafo bipartito completo K_m,n.​ Sin embargo, el mismo problema de minimizar cruces fue también considerado en sociología aproximadamente al mismo tiempo que Turán, en conexión con la construcción de sociogramas.​ Sigue siendo de gran importancia en diagramado de grafos.

Sin otra especificación, el número de cruce permite diagramas en los que las aristas pueden ser representadas por curvas arbitrarias; el número de cruce rectilineo 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 rectilineo de un grafo completo es esencialmente el mismo que el número mínimo de cuadriláteros convexos determinados por un conjunto de "n" puntos en posición general, estrechamente relacionado con el Problema del final feliz.​

Historia

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 cargadas de ladrillos de los hornos a los almacenes. La fábrica tenía vías que iban de cada horno a cada almacén, y los vagones eran más difíciles de empujar en los puntos donde las vías se cruzaban, lo que llevó a Turán a plantearse su problema de la fábrica de ladrillos: ¿cuál es el número mínimo posible de cruces en un diagrama de un grafo bipartito completo?​

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

$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 grafo bipartito completo K_m,n. La conjetura de que esta desigualdad es en realidad una igualdad hoy se conoce como conjetura del número de cruce de Zarankiewicz. El error en la prueba de la cota inferior no fue descubierto hasta once años después de su publicación, casi simultáneamente por Gerhard Ringel y Paul Kainen; ver​

El problema de determinar el número de cruce del grafo completo fue plantado por primera vez por Anthony Hill, y aparece impreso en 1960.​ Hill y su colaborador John Ernest eran dos artistas constructivistas fascinados por las matemáticas, quienes no solo formularon este problema sino que también originaron un límite superior conjetural para este número de cruce, publicado por Richard K. Guy en 1960.,​ a saber

$cr(K_{p})\leq (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 ,$

que da valores de $1,3,9,18,36,60,100,150$ para $p=1,\ldots ,12;$ ver secuencia​ en la OEIS. Una formulación independiente de la conjetura fue hecha por Thomas L. Saaty en 1964.​ Saaty verificó además que el límite superior es alcanzado por $p\leq 10$ y Pan y Richter mostraron que también es alcanzado por $p=11,p=12.$ Si solo se permiten segmentos de línea recta, se necesitarán mas cruces. Los números de cruce rectilíneos para K₅ hasta K₁₂ son 1, 3, 9, 19, 36, 62, 102, 153,​ y se conocen los valores hasta K₂₇, con K₂₈ requiriendo o 7233 o 7234 cruces. Valores posteriores son recogidos en el Rectilinear Crossing Number project.​ Curiosamente, no se sabe si los números de cruce ordinarios y rectilíneos son los mismos para grafos bipartitos completos. Si la conjetura Zarankiewicz es correcta, entonces la fórmula para el número de cruce del grafo completo es asintóticamente correcta;​ es decir,

$\lim _{p\to \infty }\;cr(K_{p})\;64/p^{4}=1.$

Hasta enero de 2012, se conocen los números de cruce de muy pocas familias de grafos. En particular, a excepción de algunos casos iniciales, el número de cruce de grafos completos, grafos bipartitos completos y productos de ciclos siguen siendo desconocidos. Ha habido algunos avances en cotas inferiores, según lo informado por de Klerk et al. (2006).​

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 conjetura de Guy-Saaty sobre el número de cruce del grafo completo es válida, cada grafo n-cromático tiene un número de cruce por lo menos igual al de la fórmula en la conjetura. Se sabe que esto es válido para n ≤ 16.​