Wikipedia

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

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.

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

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 Km,n.[1]​ 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.[2]​ 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.[3]​

Historia

editar

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 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?[4]​

 
Un dibujo óptimo de K4,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)

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

 

para el número de cruce del grafo bipartito completo Km,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 (véase "Decline and fall of Zarankiewicz's Theorem").[6]​

El problema de determinar el número de cruce del grafo completo fue planteado por primera vez por Anthony Hill, y aparece impreso en 1960.[7]​ 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,[7]​ a saber:

 

que da valores de   para   (véase (sucesión A000241 en OEIS)).[8]​

Una formulación independiente de la conjetura fue hecha por Thomas L. Saaty en 1964.[9]​ Saaty verificó además que el límite superior es alcanzado por  ; y Pan y Richter demostraron que también es alcanzado por   Si solo se permiten segmentos de línea recta, se necesitarán más cruces. Los números de cruce rectilíneos para K5 hasta K12 son 1, 3, 9, 19, 36, 62, 102, 153,[10]​ y se conocen los valores hasta K27, con K28 requiriendo o 7233 o 7234 cruces. Valores posteriores son recogidos en el Rectilinear Crossing Number project.[11]​ Curiosamente, no se sabe si los números de cruce ordinarios y rectilíneos son los mismos para grafos bipartitos completos. Si la conjetura de Zarankiewicz es correcta, entonces la fórmula para el número de cruce del grafo completo es asintóticamente correcta;[12]​ es decir,

 

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).[13]​

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 Kn 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.[14]​

Complejidad

editar

En general, determinar el número de cruces de un gráfico es difícil; Garey y Johnson demostraron en 1983 que es un problema NP-difícil.[15]​ De hecho, el problema sigue siendo NP-difícil incluso cuando se restringe a grafos cúbicos[16]​ y a los gráficos casi planos[17]​ (gráficos que se vuelven planos después de eliminar un solo borde). Más específicamente, determinar el número de cruce rectilíneo es de complejidad completa para la teoría existencial de los reales.[18]​

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 de complejidad parametrizada.[19]​ Sigue siendo difícil para k más grandes, como |V|/2. También hay algoritmos de aproximación eficientes para estimar cr(G) en gráficos de grado acotado.[20]​ En la práctica, se utilizan algoritmos heurísticos, como el algoritmo simple que comienza sin bordes y agrega continuamente cada nuevo borde de manera que produzca la menor cantidad posible de cruces adicionales. Estos algoritmos se utilizan en el proyecto Rectilinear Crossing Number[21]​ mediante computación distribuida.

Número de cruce de gráficos cúbicos

editar

Los grafos cúbicos más pequeños con números de cruce del 1 al 8 se conocen como (sucesión A110507 en OEIS). El gráfico cúbico de 1 cruce más pequeño es el grafo bipartito completo K3,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 Papo, 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.[22]​ Los grafos cúbicos de 8 cruces más pequeños incluyen el grafo de Nauru y el grafo de McGee o (3,7)-jaula, con 24 vértices.

En 2009, Exoo conjeturó que el grafo cúbico más pequeño con el número de cruce 11 es el grafo de Coxeter, el grafo cúbico más pequeño con el número de cruce 13 es el grafo de Tutte-Coxeter y el grafo cúbico más pequeño con el número de cruce 170 es la 12-jaula de Tutte.[23]​[24]​

La desigualdad del número de cruce

editar

La muy útil desigualdad del número de cruce, descubierta independientemente por Ajtai, Chvátal, Newborn y Szemerédi[25]​ y por Leighton,[26]​ afirma que si un grafo G (no dirigido, sin bucles ni aristas múltiples) con n vértices y e aristas satisface

 

entonces se tiene que

 

La constante 29 es la más conocida hasta la fecha, y se debe a Ackerman.[27]​ La constante 7.5 se puede bajar a 4, pero a costa de reemplazar 29 con la peor constante de 64.

La motivación de Leighton para estudiar los números de cruce fue para aplicaciones al diseño de integración a muy gran escala en teoría de Ciencias de la Computación. Más tarde, Székely[28]​ también se dio cuenta de que esta desigualdad producía pruebas muy simples de algunos teoremas importantes en geometría de la incidencia, como el teorema de Beck y el teorema de Szemerédi-Trotter. Tamal Dey lo usó para probar los límites superiores en k-conjuntos geométricos.[29]​

Para gráficos con cintura mayor que 2r y e ≥ 4n, Pach, Spencer y Tóth[30]​ demostraron una mejora de esta desigualdad a:

 

Demostración de la desigualdad del número de cruce

editar

Primero se da una estimación preliminar: para cualquier grafo G con n vértices y e aristas, se tiene que

 

Para probar esto, considérese un diagrama G que tiene exactamente cr(G) cruces. Cada uno de estos cruces se puede eliminar eliminando un borde de G. Así, se puede encontrar un grafo con al menos   aristas y n vértices sin cruces, y por lo tanto es un grafo plano. Pero según la fórmula de Euler entonces se deben tener  . De hecho, se tienen   para n ≥ 3.

Para obtener la desigualdad del número de cruce real, se usa un argumento probabilístico. Se deja que el parámetro 0 < p < 1 sea una probabilidad que se elija más tarde, y se construye un subgrafo aleatorio H de G permitiendo que cada vértice de G se encuentre en H independientemente con probabilidad p, y permitiendo que una arista de G se encuentre en H si y solo si sus dos vértices se eligieron para que se encuentren en H. Sea   el número de aristas de H y   sea el número de vértices.

Ahora considérese un diagrama de G con cr(G) cruces. Se puede suponer que cualquiera de los dos bordes en este diagrama con un vértice común son disjuntos, de lo contrario se podrían intercambiar las partes de intersección de los dos bordes y reducir el número de cruce en uno. Así, cada cruce en este diagrama involucra cuatro vértices distintos de G.

Dado que H es un subgrafo de G, este último diagrama contiene un diagrama de H. Sea ​​  el número de cruces de este grafo aleatorio. Por la desigualdad del número de cruce previa, se tiene que

 

Tomando estadísticamente esperanzas, se obtiene que

 

Como cada uno de los vértices n en G tenía una probabilidad p de estar en H, entonces  . De manera similar, dado que cada una de las aristas en G tiene una probabilidad   de permanecer en H (ya que ambos extremos necesita permanecer en H), entonces  . Finalmente, todo cruce en el diagrama de G tiene una probabilidad   de permanecer en H, ya que todo cruce involucra cuatro vértices, y por tanto  . Así, se tiene que

 

Si ahora se hace que p sea igual a 4n/e (que es menor que uno, ya que se supone que e es mayor que 4n), se obtiene después de un poco de álgebra que

 

Un ligero refinamiento de este argumento permite reemplazar 64 por 33.75 cuando "e" es mayor que 7.5 "n".[27]​

Véase también

editar

Referencias

editar
  1. ↑ Turán, P. (1977). «A Note of Welcome». J. Graph Theory 1: 7-9. doi:10.1002/jgt.3190010105. 
  2. ↑ Bronfenbrenner, Urie (1944). «The graphic presentation of sociometric data». Sociometry 7 (3): 283-289. JSTOR 2785096. «The arrangement of subjects on the diagram, while haphazard in part, is determined largely by trial and error with the aim of minimizing the number of intersecting lines.» 
  3. ↑ Scheinerman, Edward R.; Wilf, Herbert S. (1994). «The rectilinear crossing number of a complete graph and Sylvester's "four point problem" of geometric probability». American Mathematical Monthly 101 (10): 939-943. JSTOR 2975158. doi:10.2307/2975158. 
  4. ↑ Pach, János; Sharir, Micha (2009). «5.1 Crossings—the Brick Factory Problem». Combinatorial Geometry and Its Algorithmic Applications: The Alcalá Lectures. Mathematical Surveys and Monographs 152. American Mathematical Society. pp. 126-127. 
  5. ↑ Zarankiewicz, K. (1954). «On a Problem of P. Turán Concerning Graphs». Fund. Math. 41: 137-145. 
  6. ↑ Guy, R.K. (1969). «Decline and fall of Zarankiewicz's Theorem». Proof Techniques in Graph Theory (Ed. by F. Harary), Academic Press: 63-69. 
  7. ↑ a b Guy, R.K. (1960). «A combinatorial problem». Nabla (Bulletin of the Malayan Mathematical Society) 7: 68-72. 
  8. ↑ https://oeis.org/A000241
  9. ↑ Saaty, T.L. (1964). «The minimum number of intersections in complete graphs». Proceedings of the National Academy of Sciences of the United States of America 52: 688-690. doi:10.1073/pnas.52.3.688. 
  10. ↑ https://oeis.org/A014540
  11. ↑ Oswin Aichholzer. «Rectilinear Crossing Number project». Archivado desde el original el 30 de diciembre de 2012. Consultado el 19 de junio de 2019. 
  12. ↑ Kainen, P.C. (1968). «On a problem of P. Erdos». Journal of Combinatorial Theory 5: 374-377. doi:10.1016/s0021-9800(68)80013-4. 
  13. ↑ de Klerk, E.; Maharry, J.; Pasechnik, D. V.; Richter, B.; Salazar, G. (2006). «Improved bounds for the crossing numbers of Km,n and Kn». SIAM Journal on Discrete Mathematics 20 (1): 189-202. doi:10.1137/S0895480104442741. Archivado desde el original el 18 de julio de 2011. Consultado el 18 de agosto de 2014. 
  14. ↑ Barát, János; Tóth, Géza (2009). «Towards the Albertson Conjecture». arXiv:0909.0413  [math.CO]. 
  15. ↑ Garey, M. R.; Johnson, D. S. (1983). «Crossing number is NP-complete». SIAM J. Alg. Discr. Meth. 4 (3): 312-316. MR 0711340. doi:10.1137/0604033. 
  16. ↑ Hliněný, P. (2006). «Crossing number is hard for cubic graphs». Journal of Combinatorial Theory, Series B 96 (4): 455-471. MR 2232384. doi:10.1016/j.jctb.2005.09.009. 
  17. ↑ Cabello S. and Mohar B. (2013). «Adding One Edge to Planar Graphs Makes Crossing Number and 1-Planarity Hard». SIAM Journal on Computing 42 (5): 1803-1829. doi:10.1137/120872310. 
  18. ↑ Schaefer, Marcus (2010). «Complexity of some geometric and topological problems». Graph Drawing, 17th International Symposium, GS 2009, Chicago, IL, USA, September 2009, Revised Papers. Lecture Notes in Computer Science 5849. Springer-Verlag. pp. 334-344. ISBN 978-3-642-11804-3. doi:10.1007/978-3-642-11805-0_32. .
  19. ↑ Grohe, M. (2005). «Computing crossing numbers in quadratic time». J. Comput. System Sci. 68 (2): 285-302. MR 2059096. doi:10.1016/j.jcss.2003.07.008. ; Kawarabayashi, Ken-ichi; Reed, Bruce (2007). «Computing crossing number in linear time». Proceedings of the 29th Annual ACM Symposium on Theory of Computing. pp. 382-390. ISBN 978-1-59593-631-8. doi:10.1145/1250790.1250848. 
  20. ↑ Even, Guy; Guha, Sudipto; Schieber, Baruch (2003). «Improved Approximations of Crossings in Graph Drawings and VLSI Layout Areas». SIAM Journal on Computing 32 (1): 231-252. doi:10.1137/S0097539700373520. 
  21. ↑ Rectilinear Crossing Number on the Institute for Software Technology at Graz, University of Technology (2009).
  22. ↑ Weisstein, Eric W. «Graph Crossing Number». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research. 
  23. ↑ Exoo, G. «Rectilinear Drawings of Famous Graphs». 
  24. ↑ Pegg, E. T.; Exoo, G. (2009). «Crossing Number Graphs». Mathematica Journal 11. .
  25. ↑ Ajtai, M.; Chvátal, V.; Newborn, M.; Szemerédi, E. (1982). «Crossing-free subgraphs». Theory and Practice of Combinatorics. North-Holland Mathematics Studies 60. pp. 9-12. MR 0806962. 
  26. ↑ Leighton, T. (1983). Complexity Issues in VLSI. Foundations of Computing Series. Cambridge, MA: MIT Press. 
  27. ↑ a b Ackerman, Eyal (2013), On topological graphs with at most four crossings per edge, archivado desde el original el 14 de julio de 2014, consultado el 18 de agosto de 2014 . para obtener resultados anteriores con constantes menos ajustadas, consúltese Pach, János; Tóth, Géza (1997), «Graphs drawn with few crossings per edge», Combinatorica 17 (3): 427-439, MR 1606052, doi:10.1007/BF01215922 .; Pach, János; Radoičić, Radoš; Tardos, Gábor; Tóth, Géza (2006), «Improving the crossing lemma by finding more crossings in sparse graphs», Discrete and Computational Geometry 36 (4): 527-552, MR 2267545, doi:10.1007/s00454-006-1264-9 ..
  28. ↑ Székely, L. A. (1997). «Crossing numbers and hard Erdős problems in discrete geometry». Combinatorics, Probability and Computing 6 (3): 353-358. MR 1464571. doi:10.1017/S0963548397002976. 
  29. ↑ Dey, T. L. (1998). «Improved bounds for planar k-sets and related problems». Discrete and Computational Geometry 19 (3): 373-382. MR 1608878. doi:10.1007/PL00009354. 
  30. ↑ Pach, János; Spencer, Joel; Tóth, Géza (2000). «New bounds on crossing numbers». Discrete and Computational Geometry 24 (4): 623-644. doi:10.1007/s004540010011. 
Obtenido de «https://es.wikipedia.org/w/index.php?title=Número_de_cruce_(teoría_de_grafos)&oldid=161847939»