Metszési szám (gráfelmélet)

A Wikipédiából, a szabad enciklopédiából
A Heawood-gráf egy síkba rajzolása három metszéssel. Ez a lehetséges legkisebb számú metszéspont a gráf összes lerajzolása közül, ezért a gráf metszési száma cr(G) = 3.

A gráfelméletben egy G gráf cr(G)-vel jelölt metszési száma a G gráf összes síkbeli reprezentációja közül az élek metszéspontjainak lehetséges minimális száma. Egy gráf akkor és csak akkor síkbarajzolható gráf, ha a metszési száma 0.

A metszési szám először Turán téglagyári problémája néven (Turán's brick factory problem) merült föl, melyben Turán Pál a Km,n teljes páros gráf metszési számára kérdez rá.[1]

Története[szerkesztés | forrásszöveg szerkesztése]

Zarankiewicz megpróbálkozott Turán téglagyári problémájának megoldásával;[2] bizonyításában volt egy hiba, de sikerült a Km,n teljes páros gráf metszési számára érvényes felső becslést adnia:

cr(K_{m,n}) \le \lfloor n/2\rfloor\lfloor (n-1)/2\rfloor\lfloor m/2\rfloor\lfloor (m-1)/2\rfloor

A sejtés, hogy ez az egyenlőtlenség valójában egyenlőség, Zarankiewicz-sejtés néven is ismert.

A teljes gráf metszési számának meghatározását először Anthony Hill vetette fel, írásban 1960-ban jelent meg.[3] Hill és társa, John Ernest konstruktivista művészek voltak, akik nem elégedtek meg a problémafelvetéssel, hanem egy Richard Guy által 1960-ban publikált dolgozatban sejtésüket is megfogalmazták a metszési szám felső határára.[3]

Richard K. Guy (1972) sejtése szerint a Kn teljes gráf metszési száma

\textrm{cr}(K_n)=\frac14\left\lfloor\frac{n}{2}\right\rfloor\left\lfloor\frac{n-1}{2}\right\rfloor\left\lfloor\frac{n-2}{2}\right\rfloor\left\lfloor\frac{n-3}{2}\right\rfloor.

Jelenleg mindkét probléma megoldatlan, néhány speciális eset kivételével; az alsó határok megadásában történt néhány előrelépés, ahogy Klerk et al. jelenti 2006-ban[4].

A Michael O. Albertson által 2007-ben megfogalmazott Albertson-sejtés szerint az összes n kromatikus számú gráf közül a Kn teljes gráf rendelkezik a minimális metszési számmal. Tehát ha Richard Guy a teljes gráfok metszési számára vonatkozó sejtése igaz, minden n-kromatikus gráf metszési száma nagyobb vagy egyenlő a sejtésben szereplő képletnél. Jelenleg n ≤ 16-ra igazolt a sejtés érvényessége.[5]

Variációk[szerkesztés | forrásszöveg szerkesztése]

A metszési szám meghatározása megengedi, hogy a gráf éleit tetszőleges görbék jelöljék; az egyenes metszési szám (rectilinear crossing number) megköveteli, hogy az élek egyenes szakaszokként legyenek megrajzolva; értéke eltérhet a metszési számtól. Különösen, a teljes gráf egyenes metszési száma megegyezik az n általános helyzetű pontba rajzolható konvex négyszögek minimális számával, ami a Happy End-probléma közeli rokona.[6]

Komplexitás[szerkesztés | forrásszöveg szerkesztése]

Általánosan tekintve, egy gráf metszési számának meghatározása nehéz feladat; Garey és Johnson 1983-ban megmutatták, hogy NP-teljes probléma.[7] Valójában ha a problémát korlátozzuk a 3-reguláris gráfokra, még úgy is NP-teljes marad.[8]

A pozitív oldalt nézve, léteznek hatékony algoritmusok annak meghatározására, hogy a metszési szám kisebb-e egy k konstansnál – más szavakkal, a probléma az FPT-problémaosztályba (fixed-parameter tractable, rögzített paraméter mellett kezelhető) tartozik.[9]

Nagyobb k értékekre, pl. |V|/2 -re a feladat továbbra is nehéz marad. Korlátos fokszámú gráfok cr(G) értékének meghatározására léteznek hatékony közelítő algoritmusok.[10] A gyakorlatban heurisztikus algoritmusokat használnak, például egy egyszerű algoritmust, ami élek nélküli csúcspontokkal kezd, majd egyenként adja hozzá az új éleket olyan módon, hogy azok a lehető legkevesebbszer metsszék egymást. Ilyen algoritmust használ a Rectilinear Crossing Number[11] elosztott számítási projekt is.

3-reguláris gráfok metszési számai[szerkesztés | forrásszöveg szerkesztése]

A Tutte-féle 12-cage

Az 1 és 8 közötti metszési számokhoz tartozó legkisebb 3-reguláris gráfok ismertek (A110507 sorozat az OEIS-ben). Az 1 metszési számúak közül a legkisebb a K3,3 teljes páros gráf, 6 csúcsponttal. A legkisebb 2 metszési számú a Petersen-gráf, 10 csúcsponttal. A legkisebb 3 metszési számú 3-reguláris gráf a Heawood-gráf, 14 csúcsponttal. A legkisebb 4 metszési számú 3-reguláris gráf a Möbius–Kantor-gráf, 16 csúcsponttal. A legkisebb 5 metszési számú 3-reguláris gráf a Pappus-gráf, 18 csúcsponttal. A legkisebb 6 metszési számú 3-reguláris gráf a Desargues-gráf, 20 csúcsponttal. A négy darab 7 metszési számú 3-reguláris gráf közül egyik sem jól ismert, 22 csúcspontjuk van.[12] A legkisebb 8 metszési számú 3-reguláris gráf a McGee-gráf avagy (3,7)-cage gráf, 24 csúcsponttal.

Exoo 2009-es sejtése szerint a 11 metszési számú legkisebb 3-reguláris gráf a Coxeter-gráf, a 13 metszési számú pedig a Tutte–Coxeter-gráf a 170-esé pedig a Tutte 12-cage.[13][14]

A metszésiszám-egyenlőtlenség[szerkesztés | forrásszöveg szerkesztése]

Az igen hasznos metszésiszám-egyenlőtlenség, amit egymástól függetlenül fedezett fel Ajtai, Chvátal, Newborn és Szemerédi[15], valamint Leighton,[16] a következőt állítja: ha egy G (irányítatlan, hurkok és többszörös élek nélküli) gráfra n csúccsal és e élszámmal igaz, hogy

e > 7,5 n,\,

akkor

\operatorname{cr}(G) \geq \frac{e^3}{33,75 n^2}.\,

A 33,75-ös konstans az eddig ismert legjobb eredmény, Pach és Tóth eredménye;[17] a 7,5-ös konstans 4-re csökkenthető, de akkor a 33,75 helyére a gyengébb 64-es értéket kell írni.

Leightont a VLSI-tervezésben várható hasznosságuk motiválta a metszési számok tanulmányozásában. Később Székely[18] felismerte, hogy az egyenlőtlenség a geometriai véletlen területén néhány fontos tétel igen egyszerű bizonyításához vezetett, pl. a Beck-tétel és a Szemerédi–Trotter-tétel esetében; Tamal Dey felhasználta a geometriai K-halmazok felső korlátainak bizonyításában is.[19]

Olyan gráfokra, melyek girth paramétere 2r-nél nagyobb és e ≥ 4n Pach, Spencer és Tóth[20] a következőre javította az egyenlőtlenséget:

\operatorname{cr}(G) \geq c_r\frac{e^{r+2}}{n^{r+1}}.\,.

Források[szerkesztés | forrásszöveg szerkesztése]

  1. Turán, P. (1977.). „A Note of Welcome”. J. Graph Theory 1, 7–9. o. DOI:10.1002/jgt.3190010105.  
  2. Zarankiewicz, K. (1954.). „On a Problem of P. Turán Concerning Graphs”. Fund. Math. 41, 137–145. o.  
  3. ^ a b (1960.) „A combinatorial problem”. Nabla (Bulletin of the Malayan Mathematical Society) 7, 68–72. o.  
  4. Klerk, E. de, 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, 2006
  5. (2009.) „Towards the Albertson Conjecture”. arXiv:0909.0413.  
  6. (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. o. DOI:10.2307/2975158.  
  7. Garey, M. R.; Johnson, D. S. (1983.). „Crossing number is NP-complete”. SIAM J. Alg. Discr. Meth. 4, 312–316. o. DOI:10.1137/0604033. MathSciNet:0711340.  
  8. Hliněný, P. (2006.). „Crossing number is hard for cubic graphs”. Journal of Combinatorial Theory, Series B 96 (4), 455–471. o. DOI:10.1016/j.jctb.2005.09.009. MathSciNet:2232384.  
  9. Grohe, M. (2005.). „Computing crossing numbers in quadratic time”. J. Comput. System Sci. 68 (2), 285–302. o. DOI:10.1016/j.jcss.2003.07.008. MathSciNet:2059096.  ; (2007.) „Proceedings of the 29th Annual ACM Symposium on Theory of Computing”, 382–390. o. DOI:10.1145/1250790.1250848.  
  10. (2003.) „Improved Approximations of Crossings in Graph Drawings and VLSI Layout Areas”. SIAM J. Comput 32 (1), 231–252. o. DOI:10.1137/S0097539700373520.  
  11. Rectilinear Crossing Number on the Institute for Software Technology at Graz, University of Technology (2009).
  12. Weisstein, Eric W.: Graph Crossing Number (angol nyelven). Wolfram MathWorld
  13. Exoo, G. "Rectilinear Drawings of Famous Graphs".
  14. Pegg, E. T. and Exoo, G. "Crossing Number Graphs." Mathematica J. 11, 2009.
  15. Ajtai, M.; Chvátal, V.; Newborn, M.; Szemerédi, E. (1982). „Crossing-free subgraphs”. Theory and Practice of Combinatorics 60: 9–12. MathSciNet:0806962. 
  16. Leighton, T.. Complexity Issues in VLSI, Foundations of Computing Series. Cambridge, MA: MIT Press (1983) 
  17. Pach, J.; Tóth, G. (1997.). „Graphs drawn with few crossings per edge”. Combinatorica 17, 427–439. o. DOI:10.1007/BF01215922. MathSciNet:1606052.  
  18. Székely, L. A. (1997.). „Crossing numbers and hard Erdős problems in discrete geometry”. Combinatorics, Probability and Computing 6, 353–358. o. DOI:10.1017/S0963548397002976. MathSciNet:1464571.  
  19. Dey, T. L. (1998.). „Improved bounds for planar k-sets and related problems”. Discrete and Computational Geometry 19 (3), 373–382. o. DOI:10.1007/PL00009354. MathSciNet:1608878.  
  20. (2000.) „New bounds on crossing numbers”. Discrete and Computational Geometry 24 (4), 623–644. o.