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

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

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.

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.

Zarankiewicz megpróbálkozott Turán téglagyári problémájának megoldásával; 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})\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. 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.

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

$\text{cr}(K_n)=\frac{1}{4}\lfloor \frac{n}{2}\rfloor \lfloor \frac{n-1}{2}\rfloor \lfloor \frac{n-2}{2}\rfloor \lfloor \frac{n-3}{2}\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.

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.

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.

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. Garey és Johnson 1983-ban megmutatták, hogy NP-teljes probléma. Valójában ha a problémát korlátozzuk a 3-reguláris gráfokra, még úgy is NP-teljes marad.

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

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.

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. 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 elosztott számítási projekt is.

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

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 Sablon:OEIS. 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. 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.

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, valamint Leighton, 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

$\mathrm{cr}(G)\ge \frac{e^3}{29n^2}.$

A 29-es konstans az eddig ismert legjobb eredmény, Ackerman érte el (a korábbi, 33,75-ös konstans, e > 7,5 n esetre Pach és Tóth eredménye;); 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 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.

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

$\mathrm{cr}(G)\ge c_r\frac{e^{r+2}}{n^{r+1}}.$.