Csúcsgráf

A matematika, azon belül a gráfelmélet területén egy csúcsgráf (apex graph) olyan gráf, ami egyetlen csúcs eltávolításával síkbarajzolhatóvá tehető. A törölt csúcs a gráf csúcspontja (apex). A csúcsgráfnak több csúcspontja is lehet, például a K₅ és K_3,3 minimális nem síkbarajzolható gráfok minden csúcsa csúcspont. A nullgráfot szintén csúcsgráfnak szokás tekinteni, bár nincs benne eltávolítható csúcs.

A csúcsgráfok a minorképzés műveletére zártak, és a gráfminor-elméletben többfelé előkerülnek: a láncmentes beágyazás,^[1] Hadwiger-sejtés,^[2] YΔY-redukálható gráfok,^[3] illetve a faszélesség és átmérő közti kapcsolat esetében.^[4]

A csúcsgráfok a minorképzés műveletére zártak: egy csúcsgráf bármelyik élének összehúzásával, bármelyik él vagy csúcs eltávolításával egy másik csúcsgráfhoz jutunk. Tehát ha G egy csúcsgráf, melynek csúcspontja v, akkor bármely, v-t nem érintő összehúzás vagy eltávolítás megőrzi a maradék gráf síkba rajzolhatóságát, ahogy egy v-vel érintkező él eltávolítása is. Ha egy v-vel érintkező él összehúzásra kerül, a maradék gráffal ugyanaz történik, mintha az él másik végpontját eltávolítanánk. És ha magát v-t távolítjuk el, bármely másik csúcsot kinevezhetjük csúcspontnak.^[5]

A Robertson–Seymour-tétel alapján, mivel minorzárt gráfcsaládot alkotnak, a csúcsgráfok rendelkeznek tiltott minor-alapú osztályozással. Tehát csak véges sok olyan gráf létezik, ami nem csúcsgráf és nem tartalmaz másik nem-csúcsgráfot minorként. Ezeket a gráfokat nevezik a csúcsgráfok tiltott minorainak (obstrukcióhalmazának). Bármely G gráf akkor csúcsgráf, ha nem nem tartalmazza minorként valamelyik tiltott minort. Az obstrukcióhalmaz elemei közé tartozik a Petersen-gráfcsalád hét gráfja, három nem összefüggő gráf, ami két K₅ és egy K_3,3 közül kettő-kettőnek a diszjunkt uniójából származik, és több másik gráf. A tiltott minorok teljes listáját azonban még nem sikerült összeállítani, 2016-ban 263 ilyen gráf volt ismert.^[5][6]

Bár a tiltott minorok listája még nem teljes, annak tesztelése, hogy adott gráf csúcsgráf-e, lineáris időben megoldható. Általánosabban, bármely rögzített k konstansra, lineáris időben felismerhetők az ún. k-csúcsgráfok, azaz a gráfok, melyekből jól megválasztott legfeljebb k csúcs eltávolításával síkbarajzolható gráfhoz jutunk.^[7] Ha azonban k változó, a probléma NP-teljes.^[8]

Egy csúcsgráf kromatikus száma legfeljebb öt lehet: a síkbarajzolható alapgráf kromatikus száma a négyszíntétel alapján legfeljebb négy, a maradék egy csúcsponthoz pedig legfeljebb egy új színre van szükség. (Robertson, Seymour & Thomas 1993a) ennek a ténynek a felhasználásával bizonyították a Hadwiger-sejtés k = 6 esetét, miszerint minden 6-kromatikus gráf tartalmazza a K₆ teljes gráfot minorként: megmutatták, hogy bármely minimális ellenpéldának csúcsgráfnak kellene lennie, de mert 6-kromatikus csúcsgráf nem létezik, így az ellenpélda sem.

A matematika megoldatlan problémája: Minden 6-szorosan csúcsösszefüggő, ${\displaystyle K_{6}}$-minormentes gráf csúcsgráf? (A matematika további megoldatlan problémái)

(Jørgensen 1994) sejtése szerint minden 6-szorosan csúcsösszefüggő gráf csúcsgráf, ha nem tartalmazza a K₆-t minorként. Ha ezt sikerülne bizonyítani, abból a Hadwiger-sejtés korábban említett Robertson–Seymour–Thomas-féle eredménye is azonnal következne.^[2] A Jørgensen-sejtés egyelőre bizonyítatlan,^[9] ha azonban hamis, csak véges sok ellenpéldája létezhet.^[10]

Egy F gráfcsaládnak akkor van korlátos helyi faszélessége (bounded local treewidth), illetve rendelkezik az átmérő-faszélesség tulajdonsággal (diameter-treewidth property), ha a család gráfjainak faszélességét felülről korlátozza átmérőjük egy függvénye, tehát ha létezik olyan ƒ függvény, hogy egy F-beli, d átmérőjű gráf faszélessége legfeljebb ƒ(d). A csúcsgráfok nem rendelkeznek korlátos helyi faszélességgel: az n × n-es rácsgráf minden csúcsának a csúcsponttal való összekötésével kapott csúcsgráf faszélessége n, átmérője pedig 2, tehát a faszélesség nem lehet az átmérő függvénye által korlátozva. A csúcsgráfok családjának mégis köze van a korlátos helyi faszélességhez: a minorzárt F gráfcsaládnak pontosan akkor van korlátos helyi faszélességgel, ha az obstrukciós halmazában legalább egy csúcsgráf szerepel, azaz csúcsgráfminor-mentes.^[4] Tehát a csúcsgráfminor-mentes gráfcsaládok megegyeznek a korlátos helyi faszélességű minorzárt gráfcsaládokkal.

Az átmérő-faszélesség tulajdonság közeli kapcsolatban áll a bidimenzionalitás algoritmikus elméletével, és a csúcsgráfminor-mentes gráfok számos algoritmikus problémája megoldható polinom időben, vagy rögzített paraméter mellett kezelhető, vagy polinomiális approximációs sémával közelíthető.^[11] A csúcsgráfminor-mentes gráfokra a gráfminor-tétel egy erősebb változata alkalmazható, ami a gráfszínezési és utazó ügynök-problémák további approximációs algoritmusaihoz vezet.^[12] Ezeknek az eredményeknek némelyike kiterjeszthető tetszőleges minorzárt gráfcsaládokra az őket a csúcsgráfminor-mentes gráfokkal kapcsolatba hozó strukturális tételek segítségével.^[13]

Ha G csúcsgráfban v csúcspont és τ megegyezik G\{v} egy síkba rajzolásában a v összes szomszédjának lefedéséhez szükséges tartományok minimális számával, akkor G beágyazható egy τ − 1 génuszú kétdimenzós felületbe: egyszerűen hozzá kell adni a hidak ezen számát a síkba ágyazáshoz, amik összekötik azokat a tartományokat, melyekbe v bekötendő. Például egy külsíkgráfhoz (melynél τ = 1) egyetlen csúcsot adva síkbarajzolható gráfot kapunk. Ha G\{v} 3-szorosan összefüggő, akkor a génuszra vonatkozó korlát az optimálisnak konstansszorosa: G minden felületbe ágyazása legalább τ/160-as génuszt igényel. A csúcsgráf felületbe ágyazása optimális génuszának megállapítása azonban NP-nehéz.^[14]

Egy csúcsgráf síkbarajzolható részének lehetséges beágyazásait SPQR-fákkal kódolva ki lehet számítani a gráf olyan lerajzolását, melyben a metsző élek csak a csúcspont összefüggésében jönnek létre, így minimalizálva a metsző élek számát polinom idő alatt.^[15] Ha azonban tetszőleges metszést megengedünk, NP-nehéz feladat a metsző élek számának minimalizálása, még azon speciális csúcsgráfoknál is, melyek egy síkbarajzolható gráfhoz egyetlen él hozzáadásával jöttek létre.^[16]

A csúcsgráfok láncmentesen beágyazhatók a háromdimenziós térbe: beágyazhatók oly módon, hogy a gráf minden köre egy körlemez határán legyen, melyen a gráf más eleme nem hatol át.^[17] Egy ilyen beágyazás megkapható a gráf síkbarajzolható részének síkba rajzolásával, majd a csúcspont a sík fölé helyezésével és a csúcspont a szomszédaival való egyenes vonalú összekötésével. A láncmentesen beágyazható gráfok minorzárt családot alkotnak, melynek minimális tiltott minorai a Petersen-gráfcsalád;^[1] így ezek a gráfok a csúcsgráfok tiltott minorai is egyben. Léteznek azonban láncmentesen beágyazható gráfok, melyek nem csúcsgráfok.

Egy összefüggő gráf akkor YΔY-redukálható, ha a lépések egy sorozatával egyetlen csúcsra redukálható, ahol a lépések a következők lehetnek: Δ-Y vagy Y-Δ átalakítás, egy hurokél vagy többszörös él átalakítása, egyetlen szomszéddal rendelkező csúcs eltávolítása, kettő fokszámú csúcs és a belőle kiinduló élek cseréje egyetlen élre.^[3]

A csúcsgráfokhoz és a láncmentesen beágyazható gráfokhoz hasonlóan a YΔY-redukálható gráfok is zártak a minorképzés műveletére nézve. A láncmentesen beágyazható gráfokhoz hasonlóan az obstrukciós halmazukhoz tartozik a Petersen-gráfcsalád hét gráfja, mint tiltott minor, ami felvetette a kérdést, hogy vajon a két gráfcsalád megegyezik-e. Neil Robertson talált olyan csúcsgráfot, ami nem YΔY-redukálható, ezért az YΔY-redukálható gráfok obstrukciós halmazába további gráfoknak kell tartozniuk.^[3]

Az ábrán látható Robertson csúcsgráfja. A gráf előállítható akár egy rombododekaéder három fokszámú csúcsaihoz egy csúcspont hozzáadásával, vagy egy négydimenziós hiperkockagráf két átlósan szemközt lévő csúcsának összeolvasztásával. Mivel a rombododekaéder gráfja síkba rajzolható, a Robertson-féle gráf csúcsgráf. Háromszögmentes gráf, melynek minimális fokszáma négy, ezért az YΔY-redukciók nem változtathatják meg.^[3]

Egy csúcsgráfnak nem feltétlenül van egyetlen kijelölt csúcspontja. Például a minor-minimális nem síkbarajzolható gráfokban – a K₅-ben és a K_3,3-ban – bármely csúcs kiválasztható csúcspontként. Wagner (1967, 1970) definíciója szerint egy csaknem síkbarajzolható gráf (nearly planar graph) olyan, nem síkbarajzolható csúcsgráf, melyben bármelyik csúcs kiválasztható csúcspontként; tehát például a K₅ és K_3,3 csaknem síkbarajzolható. Elvégezte az ilyen gráfok osztályozását, négy részhalmazba osztva őket, melyek egyike azokból a gráfokból áll, melyek (a Möbius-létrákhoz hasonlóan) beágyazhatók a Möbius-szalagba úgy, hogy a szalag éle egybeesik a gráf egy Hamilton-körével. A négyszíntétel bizonyítása előtt sikerült bizonyítania, hogy a csaknem síkbarajzolható gráfok legfeljebb négy színnel színezhetők, kivéve a páratlan külső körrel rendelkező gráfokat, melyek egy kerékgráfból jönnek létre a központi csúcs két egymás melletti csúcsra való kicserélésével, melyekhez öt színre van szükség. Ráadásként bizonyította, hogy a kocka nyolc csúcsú komplementere kivételével az összes csaknem síkbarajzolható gráfnak létezik a projektív síkba való beágyazása.

Maga a „csaknem síkbarajzolható gráf” kifejezés erősen kétértelmű: használták már a csúcsgráfokra,^[18] a síkbarajzolható gráfokhoz egy él hozzáadásával kapott gráfokra,^[19] síkba rajzolt gráfok egyes tartományainak korlátos útszélességű „vortex”-ekre lecserélésével kapott gráfokra ^[20] és néhány más, kevésbé precízen definiált gráfcsaládra is.

Egy gráf akkor k-csúcsgráf, ha k vagy kevesebb csúcs eltávolítása után síkbarajzolható lesz. Az 1-csúcsgráf fogalma megegyezik a csúcsgráféval.

(Max & Mackall 2016) szerint egy gráf él-csúcsgráf, ha van olyan éle, melynek eltávolításával a gráf síkbarajzolható lesz, továbbá egy gráf összehúzás-csúcsgráf, ha van olyan éle, melynek összehúzásával a gráf síkbarajzolható lesz.

• Poliéder-hasáb (polyhedral pyramid), egy 4-dimenziós politóp, aminek csúcsai és élei olyan csúcsgráfot alkotnak, melyben a csúcs egy poliédergráf minden csúcsával szomszédos