„Metszési szám (gráfelmélet)” változatai közötti eltérés

A Wikipédiából, a szabad enciklopédiából
Laptörténet interaktív böngészése
[ellenőrzött változat][ellenőrzött változat]
← Régebbi szerkesztésÚjabb szerkesztés →
Tartalom törölve Tartalom hozzáadva
VizuálisWikiszöveges
Syp (vitalap | szerkesztései)
járőrök
89 988 szerkesztés
Syp (vitalap | szerkesztései)
járőrök
89 988 szerkesztés
50. sor: 50. sor:


A 33,75-ös konstans az eddig ismert legjobb eredmény, Pach és Tóth eredménye;<ref name="pt">{{cite journal|author = Pach, J.; Tóth, G.|title=Graphs drawn with few crossings per edge|journal=Combinatorica|volume=17|year=1997|pages=427–439|id=[[MathSciNet]]:[http://www.ams.org/mathscinet-getitem?mr=1606052 1606052]|doi=10.1007/BF01215922}}</ref> 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.
A 33,75-ös konstans az eddig ismert legjobb eredmény, Pach és Tóth eredménye;<ref name="pt">{{cite journal|author = Pach, J.; Tóth, G.|title=Graphs drawn with few crossings per edge|journal=Combinatorica|volume=17|year=1997|pages=427–439|id=[[MathSciNet]]:[http://www.ams.org/mathscinet-getitem?mr=1606052 1606052]|doi=10.1007/BF01215922}}</ref> 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ára. Később [[Székely László (matematikus)|Székely]]<ref>{{cite journal|author=Székely, L. A.|title=Crossing numbers and hard Erdős problems in discrete geometry|journal=Combinatorics, Probability and Computing|volume=6|year=1997|pages=353–358|id=[[MathSciNet]]:[http://www.ams.org/mathscinet-getitem?mr=1464571 1464571]|doi=10.1017/S0963548397002976}}</ref> 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-halmaz]]ok felső korlátainak bizonyításában is.<ref>{{cite journal | author = Dey, T. L. | title = Improved bounds for planar ''k''-sets and related problems | journal = [[Discrete and Computational Geometry]] | volume = 19 | issue = 3 | year = 1998 | pages = 373–382 | doi = 10.1007/PL00009354 | id = [[MathSciNet]]:[http://www.ams.org/mathscinet-getitem?mr=1608878 1608878]}}</ref>


==Források==
==Források==

A lap 2010. október 9., 22:42-kori változata

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éspontjának lehetséges minimális száma. Egy gráf akkor és csak akkor síkbarajzolható gráf, ha a gráfra vonatkozó metszési szám éppen 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

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:

.

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

Jelenleg (2009. március) 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

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

Á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 az é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

A Tutte-féle 12-cage

Az 1-8 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 avagv (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

Az igen hasznos metszésiszám-egyenlőtlenség amit egymástól függetlenül Ajtai, Chvátal, Newborn és Szemerédi[15], valamint Leighton,[16] fedezett fel, azt állítja, hogy 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

akkor

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ára. 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]

Források

  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.  
A lap eredeti címe: „https://hu.wikipedia.org/w/index.php?title=Metszési_szám_(gráfelmélet)&oldid=8607843”