Wikipédia

Csúcsgráf

matematikai fogalom a gráfelméletben

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 K5 és K3,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.

Egy csúcsgráf – a piros csúcs eltávolításával kapott részgráf síkba rajzolható.

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]

Jellemzés és felismerés szerkesztés

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 K5 és egy K3,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]

Kromatikus szám szerkesztés

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 K6 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ő,  -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 K6-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]

Helyi faszélesség szerkesztés

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]

Beágyazások szerkesztés

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.

YΔY-redukálhatóság szerkesztés

 
Robertson példája nem YΔY-redukálható csúcsgráfra.

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]

Csaknem síkbarajzolható gráfok szerkesztés

 
A 16 csúcsú Möbius-létra, a csaknem síkbarajzolható gráfok egy példánya.

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 K5-ben és a K3,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 K5 és K3,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.

Kapcsolódó gráfcsaládok szerkesztés

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.

Kapcsolódó szócikkek szerkesztés

  • 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

Jegyzetek szerkesztés

  1. ↑ a b (Robertson, Seymour & Thomas 1993b).
  2. ↑ a b (Robertson, Seymour & Thomas 1993a).
  3. ↑ a b c d (Truemper 1992).
  4. ↑ a b (Eppstein 2000); (Demaine & Hajiaghayi 2004).
  5. ↑ a b (Gupta & Impagliazzo 1991).
  6. ↑ Pierce (2014).
  7. ↑ (Kawarabayashi 2009).
  8. ↑ (Lewis & Yannakakis 1980).
  9. ↑ Jorgensen's Conjecture, <http://www.openproblemgarden.org/op/jorgensens_conjecture>. Hozzáférés ideje: 2016-11-13.
  10. ↑ Kawarabayashi et al. (2012).
  11. ↑ (Eppstein 2000); (Frick & Grohe 2001); (Demaine & Hajiaghayi 2005).
  12. ↑ (Demaine, Hajiaghayi & Kawarabayashi 2009).
  13. ↑ (Grohe 2003).
  14. ↑ (Mohar 2001).
  15. ↑ (Chimani et al. 2009).
  16. ↑ (Cabello & Mohar 2010).
  17. ↑ (Robertson, Seymour & Thomas 1993c).
  18. ↑ (Robertson, Seymour & Thomas 1993c); (Eppstein 2000).
  19. ↑ (Archdeacon & Bonnington 2004).
  20. ↑ (Abraham & Gavoille 2006).
A lap eredeti címe: „https://hu.wikipedia.org/w/index.php?title=Csúcsgráf&oldid=25416424”