Anar al contingut

Número de creuament (teoria de grafos)

De L'Enciclopèdia, la wikipedia en valencià
Un diagrama del grafo de Heawood en tres creus. Est és el mínim número de creus entre tots els diagrames d'este grafo, per lo que el grafo té número de creuament cr(G) = 3

En teoria de grafos, el número de creuament cr(G), també cridat número de cruzamiento, d'un grafo G és el menor número de creus d'arestes en un diagrama pla del grafo G. Per eixemple, un grafo és pla si i solament si el seu número de creuament és zero.

L'estudi dels números de creuament va tindre el seu orige en el problema de la fàbrica de rajoles de Turán, en el qual Pál Turán va buscar determinar el número de creuament del grafo bipartito complet Km,n.[1] No obstant, el mateix problema de minimisar creus va ser també considerat en sociologia aproximadament al mateix temps que Turán, en conexió en la construcció de sociogramas. Seguix sent de gran importància en diagramado de grafos.

Sense una atra especificació, el número de creuament permet diagrames en els que les arestes poden ser representades per curves arbitràries; el número de creuament rectilineo requerix que totes les arestes siguen segments de llínea recta, i pot diferir del número de creuament. En particular, el número de creuament rectilineo d'un grafo complet és essencialment el mateix que el número mínim de quadrilàters convexos determinats per un conjunt de "n" punts en posició general, estretament relacionat en el problema del final feliç.[2]

Història

[editar | editar còdic]

Durant la Segona Guerra Mundial, el matemàtic hongarés Pál Turán es va vore obligat a treballar en una fàbrica de rajoles, espentant vagons carregades de rajoles dels forns als almagasens. La fàbrica tenia vies que anaven de cada forn a cada almagasén, i els vagons eren més difícils d'espentar en els punts a on les vies es creuaven, lo que va dur a Turán a plantejar-se el seu problema de la fàbrica de rajoles: ¿quin és el número mínim possible de creus en un diagrama d'un grafo bipartito complet?

Archiu:Zarankiewicz caps block 4 7.svg
Un dibuix òptim de K4,7 que mostra que el problema de la fàbrica de rajoles de Turán en 4 llocs d'almagasenament (punts grocs) i 7 forns (punts blaus) requerix 18 creus (punts rojos)

Zarankiewicz va intentar resoldre el problema de la fàbrica de rajoles de Turán;[3] la seua prova contenia un error, pero va establir un llímit superior vàlit de

cr(Km,n)≤⌊n2⌋⌊n−12⌋⌊m2⌋⌊m−12⌋

per al número de creuament del grafo bipartito complete Km,n. La conjectura de que esta desigualtat és en realitat una igualtat hui es coneix com a conjectura del número de creuament de Zarankiewicz. L'error en la prova de la cota inferior no va ser descobert fins a onze anys despuix de la seua publicació, casi simultàneament per Gerhard Ringel i Paul Kainen (vore "Decline and fall of Zarankiewicz's Theorem").[4]


El problema de determinar el número de creuament del grafo complet va ser plantejat per primera volta per Anthony Hill, i apareix imprés en 1960.[5] Hill i el seu colaborador John Ernest eren dos artistes constructivista fascinats per les matemàtiques, els qui no solament varen formular este problema sino que també varen originar un llímit superior conjetural per a este número de creuament, publicat per Richard K. Guy en 1960,[5] a saber:

cr(Kp)≤(1/4)⌊p2⌋⌊p−12⌋⌊p−22⌋⌊p−32⌋,

que dona valors de 1,3,9,18,36,60,100,150 per a p=1,…,12; (vore Plantilla:OEIS).[6]

Una formulació independent de la conjectura va ser feta per Thomas L. Saaty en 1964.[7] Saaty va verificar ademés que el llímit superior és alcançat per p≤10; i Pa i Richter varen demostrar que també és alcançat per p=11,p=12. Si solament es permeten segments de llínea recta, es necessitaran més creus. Els números de creuament rectilíneos per a K5 fins a K12 són 1, 3, 9, 19, 36, 62, 102, 153,[8] i es coneixen els valors fins a K27, en K28 requerint o 7233 o 7234 creus. Valors posteriors són arreplegats en el Rectilinear Crossing Number project.[9] Curiosament, no se sap si els números de creuament ordinaris i rectilíneos són els mateixos para grafos bipartitos complets. Si la conjectura de Zarankiewicz és correcta, llavors la fòrmula per al número de creuament del grafo complet és asintóticamente correcta;[10] és dir,

limp→∞cr(Kp)64/p4=1.

Fins a giner de 2012, es coneixen els números de creuament de molt poques famílies de grafos. En particular, a excepció d'alguns casos inicials, el número de creuament de grafos complets, grafos bipartitos complets i productes de cicles seguixen sent desconeguts. Hi ha hagut alguns alvanços en cotes inferiors, segons lo informat per de Klerk et al. (2006).[11]


La conjectura de Albertson, formulada per Michael O. Albertson en 2007, establix que, entre tots els grafos en número cromàtic n, el grafo complet Kn té el número mínim de creus. És dir, si la conjectura de Guy-Saaty sobre el número de creuament del grafo complet és vàlida, cada grafo n-cromàtic té un número de creuament per lo manco igual al de la fòrmula en la conjectura. Se sap que açò és vàlit per a n ≤ 16.[12]

Complexitat

[editar | editar còdic]

En general, determinar el número de creus d'un gràfic és difícil; Garey i Johnson varen demostrar en 1983 que és un problema NP-difícil.[13] De fet, el problema seguix sent NP-difícil inclús quan es restringix a grafos cúbics[14] i als gràfics casi plans[15] (gràfics que es tornen plans despuix d'eliminar una sola vora). Més específicament, determinar el número de creuament rectilíneo és de complexitat completa per a la teoria existencial dels número real.[16]

En el costat positiu, existixen algoritmes eficients per a determinar si el número de creuament és menor que una constant fixa k; en atres paraules, el problema és de complexitat parametrizada.[17] Seguix sent difícil per a k més grans, com |V|/2. També hi ha algoritmes d'aproximació eficients per a estimar cr(G) en gràfics de grau acotat.[18] En la pràctica, s'utilisen algoritmes heurístics, com l'algoritme simple que comença sense vores i agrega contínuament cada nova vora de manera que produïxca la menor cantitat possible de creus adicionals. Estos algoritmes s'utilisen en el proyecte Rectilinear Crossing Number[19] per mig de computació distribuïda.

Vore també

[editar | editar còdic]

Referències

[editar | editar còdic]
  1. ↑ (1977).J. Graph Theory.1
    7–9.doi:10.1002/jgt.3190010105.
  2. ↑ (1994).American Mathematical Monthly.101(10)
    939–943.doi:10.2307/2975158.
  3. ↑ (1954).Fund. Math..41
    137–145.
  4. ↑ (1969).Proof Techniques in Graph Theory (Ed. by F. Harary), Academic Press.
    63–69.
  5. ↑ 5,0 5,1 (1960).Nabla (Bulletin of the Malayan Mathematical Society).7
    68–72.
  6. ↑ https://oeis.org/A000241
  7. ↑ (1964).Proceedings of the National Academy of Sciences of the United States of America.52
    688–690.doi:10.1073/pnas.52.3.688.
  8. ↑ https://oeis.org/A014540
  9. ↑ Oswin Aichholzer. «Rectilinear Crossing Number project». Archivat des d'el original, el 30 de decembre de 2012. Consultat el 19 de juny de 2019.
  10. ↑ (1968).Journal of Combinatorial Theory.5
    374–377.doi:10.1016/s0021-9800(68)80013-4.
  11. ↑ (2006).SIAM Journal on Discrete Mathematics.20(1)
    189–202.doi:10.1137/S0895480104442741.Consultat el 18 d'agost de 2014.
  12. ↑ Plantilla:Cite arXiv
  13. ↑ Garey, M. R.; Johnson, D. S. (1983). “Crossing number is NP-complete”. SIAM J. Alg. Discr. Meth. 4 (3): 312–316. doi:10.1137/0604033.
  14. ↑ Hliněný, P. (2006). “Crossing number is hard for cubic graphs”. Journal of Combinatorial Theory, Series B 96 (4): 455–471. doi:10.1016/j.jctb.2005.09.009.
  15. ↑ Cabell 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.
  16. ↑ .
  17. ↑ Grohe, M. (2005). “Computing crossing numbers in quadratic clave”. J. Comput. System Sci. 68 (2): 285–302. doi:10.1016/j.jcss.2003.07.008.;
  18. ↑ “Improved Approximations of Crossings in Graph Drawings and VLSI Layout Areas” (2003). SIAM Journal on Computing 32 (1): 231–252. doi:10.1137/S0097539700373520.
  19. ↑ Rectilinear Crossing Number on the Institute for Software Technology at Graz, University of Technology (2009).


Referències

[editar | editar còdic]


Obtingut de «https://www.lenciclopedia.org/w/index.php?title=Número_de_creuament_(teoria_de_grafos)&oldid=812049»