PROFILPELAJAR.COM

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 K_m,n teljes páros gráf metszési számára kérdez rá.^[1]

A gráfok metszési számának meghatározása nagyon nehéz feladat, részben a lehetséges lerajzolások óriási száma és áttekinthetetlensége miatt. Precízen ezért csak nagyon kicsi vagy nagyon speciális gráfok metszési számát sikerült meghatározni.^[2]

Története

A metszési szám vizsgálatát 1944-ben Turán Pál kezdeményezte egy gyakorlati probléma kapcsán. Munkaszolgálatosként téglával megrakott vasúti kocsikat kellett tologatniuk a kemencéktől a raktárépületekig. A komoly nehézséget a kereszteződések okozták. Ha n kemence és m raktárépület van, továbbá minden kemence és raktár között van sín, akkor a legjobb esetben $cr(K_{m,n})$ kereszteződés van.^[2]

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

cr(K_{m,n})\leq \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.^[4] 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.^[4]

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

{\textrm {cr}}(K_{n})={\frac {1}{4}}\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.^[5]

A Michael O. Albertson által 2007-ben megfogalmazott Albertson-sejtés szerint az összes n kromatikus számú gráf közül a K_n 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.^[6]

Variációk

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.^[7]

Komplexitás

Általánosan tekintve, egy gráf metszési számának meghatározása nehéz feladat, részben a lehetséges lerajzolások óriási száma és áttekinthetetlensége miatt. Precízen ezért csak nagyon kicsi vagy nagyon speciális gráfok metszési számát sikerült meghatározni.^[2] Garey és Johnson 1983-ban megmutatták, hogy NP-teljes probléma.^[8] Valójában ha a problémát korlátozzuk a 3-reguláris gráfokra, még úgy is NP-teljes marad.^[9]

Általában viszonylag könnyű egy gráf legjobb lerajzolásának megsejtése, az alsó korlát bizonyítása, ami gondot okoz.^[2] Legtöbbször sok lépésben, egyre kifinomultabb leszámlálásokon keresztül lehet közeledni a célhoz.^[2]^[10]^[11]^[12]^[13]

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

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.^[15] 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^[16] elosztott számítási projekt is.

3-reguláris gráfok metszési számai

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 K_3,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 Papposz-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.^[17] 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.^[18]^[19]

A metszésiszám-egyenlőtlenség

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,^[20] valamint Leighton,^[21] 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>7n,\,

akkor

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

A 29-es konstans az eddig ismert legjobb eredmény, Ackerman érte el^[22] (a korábbi, 33,75-ös konstans, e > 7,5 n esetre Pach és Tóth eredménye;^[23]); a 7-es 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^[24] felismerte, hogy az egyenlőtlenség az illeszkedési geometria 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.^[25]

Olyan gráfokra, melyek girthparamétere 2r-nél nagyobb és e ≥ 4n Pach, Spencer és Tóth^[26] 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

↑ Turán, P. (1977). „A Note of Welcome”. J. Graph Theory 1, 7–9. o. DOI:10.1002/jgt.3190010105.
↑ ^a ^b ^c ^d ^e Tóth Géza: Gráfok metszési számai és a k-halmaz probléma. Doktori disszertáció PDF
↑ Zarankiewicz, K. (1954). „On a Problem of P. Turán Concerning Graphs”. Fund. Math. 41, 137–145. o.
↑ ^a ^b (1960) „A combinatorial problem”. Nabla (Bulletin of the Malayan Mathematical Society) 7, 68–72. o.
↑ Klerk, E. de, Maharry, J., Pasechnik, D.V., Richter, B., & Salazar, G. (2006). Improved bounds for the crossing numbers of K_m,n and K_n. Archiválva 2011. július 18-i dátummal a Wayback Machine-ben SIAM Journal on Discrete Mathematics 20(1), 189-202, 2006
↑ (2009) „Towards the Albertson Conjecture”. arXiv:0909.0413.
↑ (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.
↑ 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.
↑ 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.
↑ L. Lovász, K. Vesztergombi, U. Wagner, E. Welzl: Convex quadrilaterals and k-sets. In: Towards a theory of geometric graphs, Contemporary Math. 342 Amer. Math. Soc., Providence, RI, 2004, 139–148.
↑ B. Abrego, S. Fernández-Merchant: A lower bound for the rectilinear crossing number, Graphs and Combin. 21 (2005), 293–300.
↑ J. Balogh, G. Salazar: k-sets, convex quadrilaterals, and the rectilinear crossing number of Kn, Discrete Comput. Geom. 35 (2006), 671–690.
↑ O. Aichholzer, J. García, D. Orden, P. Ramos: New lower bounds for the number of (≤ k)-edges and the rectilinear crossing number of Kn, arXiv:math.CO/0608610 v2, 2006.
↑ 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.
↑ (2003) „Improved Approximations of Crossings in Graph Drawings and VLSI Layout Areas”. SIAM J. Comput 32 (1), 231–252. o. DOI:10.1137/S0097539700373520.
↑ Rectilinear Crossing Number on the Institute for Software Technology at Graz, University of Technology (2009).
↑ Weisstein, Eric W.: Graph Crossing Number (angol nyelven). Wolfram MathWorld
↑ Exoo, G. "Rectilinear Drawings of Famous Graphs".
↑ Pegg, E. T. and Exoo, G. "Crossing Number Graphs." Mathematica J. 11, 2009.
↑ Ajtai, M.; Chvátal, V.; Newborn, M.; Szemerédi, E. (1982). „Crossing-free subgraphs”. Theory and Practice of Combinatorics 60: 9–12. MathSciNet:0806962.
↑ Leighton, T.. Complexity Issues in VLSI, Foundations of Computing Series. Cambridge, MA: MIT Press (1983)
↑ Ackerman, Eyal: On topological graphs with at most four crossings per edge, 2013. [2014. július 14-i dátummal az eredetiből archiválva].
↑ Pach, J.; Tóth, G. (1997). „Graphs drawn with few crossings per edge”. Combinatorica 17, 427–439. o. DOI:10.1007/BF01215922. MathSciNet:1606052.
↑ 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.
↑ 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.
↑ (2000) „New bounds on crossing numbers”. Discrete and Computational Geometry 24 (4), 623–644. o.

[1] Turán, P. (1977). „A Note of Welcome”. J. Graph Theory 1, 7–9. o. DOI:10.1002/jgt.3190010105.

[TG-2] Tóth Géza: Gráfok metszési számai és a k-halmaz probléma. Doktori disszertáció PDF

[3] Zarankiewicz, K. (1954). „On a Problem of P. Turán Concerning Graphs”. Fund. Math. 41, 137–145. o.

[nabla-4] (1960) „A combinatorial problem”. Nabla (Bulletin of the Malayan Mathematical Society) 7, 68–72. o.

[5] Klerk, E. de, Maharry, J., Pasechnik, D.V., Richter, B., & Salazar, G. (2006). Improved bounds for the crossing numbers of K_m,n and K_n. Archiválva 2011. július 18-i dátummal a Wayback Machine-ben SIAM Journal on Discrete Mathematics 20(1), 189-202, 2006

[6] (2009) „Towards the Albertson Conjecture”. arXiv:0909.0413.

[7] (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.

[8] 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.

[9] 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.

[10] L. Lovász, K. Vesztergombi, U. Wagner, E. Welzl: Convex quadrilaterals and k-sets. In: Towards a theory of geometric graphs, Contemporary Math. 342 Amer. Math. Soc., Providence, RI, 2004, 139–148.

[11] B. Abrego, S. Fernández-Merchant: A lower bound for the rectilinear crossing number, Graphs and Combin. 21 (2005), 293–300.

[12] J. Balogh, G. Salazar: k-sets, convex quadrilaterals, and the rectilinear crossing number of Kn, Discrete Comput. Geom. 35 (2006), 671–690.

[13] O. Aichholzer, J. García, D. Orden, P. Ramos: New lower bounds for the number of (≤ k)-edges and the rectilinear crossing number of Kn, arXiv:math.CO/0608610 v2, 2006.

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

[15] (2003) „Improved Approximations of Crossings in Graph Drawings and VLSI Layout Areas”. SIAM J. Comput 32 (1), 231–252. o. DOI:10.1137/S0097539700373520.

[16] Rectilinear Crossing Number on the Institute for Software Technology at Graz, University of Technology (2009).

[17] Weisstein, Eric W.: Graph Crossing Number (angol nyelven). Wolfram MathWorld

[18] Exoo, G. "Rectilinear Drawings of Famous Graphs".

[19] Pegg, E. T. and Exoo, G. "Crossing Number Graphs." Mathematica J. 11, 2009.

[20] Ajtai, M.; Chvátal, V.; Newborn, M.; Szemerédi, E. (1982). „Crossing-free subgraphs”. Theory and Practice of Combinatorics 60: 9–12. MathSciNet:0806962.

[21] Leighton, T.. Complexity Issues in VLSI, Foundations of Computing Series. Cambridge, MA: MIT Press (1983)

[ackerman-22] Ackerman, Eyal: On topological graphs with at most four crossings per edge, 2013. [2014. július 14-i dátummal az eredetiből archiválva].

[pt-23] Pach, J.; Tóth, G. (1997). „Graphs drawn with few crossings per edge”. Combinatorica 17, 427–439. o. DOI:10.1007/BF01215922. MathSciNet:1606052.

[24] 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.

[25] 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.

[26] (2000) „New bounds on crossing numbers”. Discrete and Computational Geometry 24 (4), 623–644. o.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

PROFILPELAJAR.COM

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

Története

Variációk

Komplexitás

3-reguláris gráfok metszési számai

A metszésiszám-egyenlőtlenség

Források

Read other articles:

Indonesian Choice Awards 2018

Холокост на Украине

Fyodor Kudryashov

TRIGA

Army of Africa (Spain)

كاستراكيون (فوكيس)

Affirm Films

Memorial (associazione)

Loose Women

Balilihan

Sweet Alibis

Canning railway station (India)

Cibitoke Province

Youth of America

Andrew Mellon

Стариков, Иван Валентинович

2001 Norwegian Football Cup

Aeropuerto de Aarhus

Paper Clip

You Are a Tourist