Csúcsszám

A gráfelméletben a csúcsgráf egy olyan gráf, amely egy csúcs eltávolításával síkba tehető . Az eltávolított csúcsot a gráf tetejének nevezzük. Vegye figyelembe, hogy egynél több csúcs lehet. Például egy K 5 vagy K 3,3 minimális nem síkbeli gráfban minden csúcs egy csúcs. A csúcsgráfok kezdetben sík gráfokat tartalmaznak, amelyekben minden csúcs egy csúcs. A nullgráf is apikálisnak számít, bár nincs eltávolítható csúcsa.

Az apex gráfok a minorok generálásának művelete alatt zártak , és nagy szerepet játszanak a gráf-moll elmélet számos más aspektusában, beleértve az unlinked beágyazást [1] , a Hadwiger-sejtést [2] , az YΔY-reduktív gráfokat [3] és a fa szélessége és grafikonátmérője [4] [5] .

Leírás és felismerés

A csúcsgráfok a minorok generálásának művelete alatt záródnak - bármely él összezsugorítása vagy egy csúcs vagy él törlése egy másik csúcsgráfhoz vezet. Valóban, ha G egy csúcsgráf v csúcsával , akkor a v csúcsot nem befolyásoló összehúzódás vagy eltávolítás megőrzi a gráf többi részének síkságát ( v csúcs nélkül ). ugyanez igaz a v -vel előforduló élek eltávolítására is . Ha a v - vel beeső élt összehúzzuk , a hatás megegyezik az él ellenkező végének eltávolításával. Ha magát a v csúcsot eltávolítjuk , akkor bármely más csúcsot csúcsnak tekinthetjük [6] .

Mivel a csúcsgráfokat a minorokat generáló művelet zárja le, a Robertson-Seymour tétel alapján tiltott gráfokkal jellemzik őket . Csak véges számú gráf létezik, amelyek nem csúcsgráfok, és nem tartalmaznak mellékesként egy másik nem csúcs gráfot. Ezek a gráfok tiltott mellékek a csúcsgráf tulajdonsághoz. Minden más G gráf akkor és csak akkor csúcs, ha a tiltott kiskorúak egyike sem kisebb G -nek . A tiltott kiskorúak közé tartozik hét gráf a Petersen családból , három szétválasztott gráf, amelyeket K 5 és K 3,3 diszjunkt egyesülései alkotnak , és sok más gráf. Az összes kitiltott kiskorú teljes listája továbbra is hiányos [6] [7] .

Annak ellenére, hogy a tiltott kiskorúak teljes listája nem ismert, lineáris időben ellenőrizhető, hogy egy adott gráf csúcs-e, és ha igen, akkor megkereshetjük a gráf csúcsát. Általánosabban fogalmazva, bármely rögzített k konstans esetén k - csúcsú gráfok (olyan gráfok, amelyekben egy gondosan kiválasztott legfeljebb k csúcsot tartalmazó halmaz törlése síkgráfhoz vezet [8] ) lineáris időben felismerhető . Ha azonban k nincs rögzítve, a probléma NP-teljessé válik [9] .

Kromatikus szám

Bármely csúcsgráf kromatikus száma nem haladja meg az ötöt – a csúcs nélküli síkgráfhoz legfeljebb négy szín szükséges a négyszín tétel szerint, és egy további szín is elegendő egy csúcshoz. Robertson, Seymour és Thomas [2] ezt a tényt arra használták fel, hogy bizonyítsák Hadwiger sejtésének k  = 6 esetét , azt az állítást, miszerint minden 6 kromatikus gráfnak van egy teljes gráfja K 6 mellékként – megmutatták, hogy minden minimális ellenpélda a sejtésnek csúcsgráfnak kell lennie, de nincsenek csúcsos 6-kromatikus gráfok, így nincs ilyen ellenpélda.

Megoldatlan problémák a matematikában : Minden 6-os csúcshoz kapcsolódó gráf csúcsok, amelyek nem tartalmaznak kisebbeket?

Jorgensen [10] úgy sejtette, hogy minden olyan 6 -os csúcshoz kapcsolódó gráfnak, amelynek nincs mellékpontja K6, csúcsnak kell lennie. Ha ez bebizonyosodna, a Hadwiger-sejtés Robertson–Seymour–Thomas eredménye a [2] egyenes következménye lenne . Jorgensen sejtése még nem igazolódott [11] . Ha azonban a sejtés hamis, akkor csak véges számú ellenpéldája van [12] .

Helyi faszélesség

Egy F gráfcsaládnak korlátos lokális faszélessége van, ha az F -beli gráfok funkcionális kapcsolatnak engedelmeskednek az átmérő és a faszélesség között – létezik olyan ƒ függvény, amely szerint a d átmérőjű F -beli gráf faszélessége nem haladja meg a ƒ( d ). A felső gráfok nem rendelkeznek korlátozott lokális faszélességgel – az n  ×  n rács egyes csúcsaihoz egy csúcsot összekötő gráf faszélessége n és átmérője 2, így a fa szélességét nem korlátozza e gráfok átmérőjének valamilyen függvénye. . A csúcsgráfok azonban szoros rokonságban állnak a korlátos lokális faszélességű gráfokkal – az F gráfok kisebb zárt családjai , amelyeknek a lokális faszélessége korlátozott, pontosan azok a családok, amelyek tiltott mellékpontjai valamilyen csúcsgráf [4] [5] . Azok a gráfok kisebb zárt családjai, amelyek mellék gráfként csúcsgráfot tartalmaznak, ismerten csúcsmollmentesek . E terminológia szerint a csúcsgráfok és a lokális faszélesség közötti kapcsolatot a következőképpen lehet újrafogalmazni: a vertex minoroktól mentes gráfcsaládok egybeesnek a korlátos lokális faszélességű mollba zárt gráfcsaládokkal.

A korlátos lokális faszélesség koncepciója képezi a kétdimenziós elmélet alapját , és lehetővé teszi számos algoritmikus probléma megoldását top minoroktól mentes gráfokon pontosan polinomiális idő algoritmussal, vagy fix paraméterű megoldható algoritmussal . , vagy a feladat egy közelítő sémapolinomidő segítségével közelíthető [4] [13] [14] . Az apikális minoroktól mentes gráfcsaládok esetében a strukturális gráftétel megerősített változata teljesül , ami további közelítő algoritmusokhoz vezet a gráfszínezéshez és az utazó eladó problémájához [15] . Ezen eredmények némelyike ​​azonban kiterjeszthető tetszőleges kisebb zárt gráfcsaládokra is, ha struktúratételeket használunk olyan gráfokra, amelyek olyan családokhoz kapcsolódnak, amelyek mentesek a csúcs minoroktól [16] .

Mellékletek

Ha egy G gráf egy csúcsgráf v csúcsával, és egyenlő a v csúcs összes szomszédjának lefedéséhez szükséges minimális lapszámmal egy G \{ v } síkbeli beágyazás alatt , akkor G beágyazható egy kétdimenziós nemzetségfelületbe . sok híd hozzáadásával a síkbeli beágyazáshoz azáltal, hogy összekapcsolja az összes olyan felületet, amelyhez v csatlakozni kell. Például, ha egy csúcsot adunk egy külső síkbeli gráfhoz (egy olyan gráfhoz, amelyben a ) sík gráfot kap. Ha a G \{ v } gráf 3-kapcsolatos, akkor a határa nem tér el az optimálistól konstans tényezőnél nagyobb mértékben – G felületbe ágyazásához legalább genus szükséges . Azonban a csúcsgráfok beágyazófelületének optimális genusának meghatározása NP-nehéz probléma [17] .

Ha SPQR fákat használunk a csúcs gráf síkbeli részének lehetséges beágyazódásainak kódolására, akkor lehetséges polinomiális időben kiszámítani a gráf beágyazását egy olyan síkra, amelyben a metszéspontokat csak a csúcscsúcsból kiinduló élek okozzák, és a teljes a kereszteződések száma minimális [18] . Ha tetszőleges metszéspontok megengedettek, akkor a metszéspontok számának minimalizálása NP-nehézsé válik, még a síkgráfhoz egyetlen él hozzáadásával képzett csúcsgráfok speciális esetében is [19] .

A csúcsgráfok háromdimenziós térben kapcsolódás nélkül beágyazhatók – beágyazhatók oly módon, hogy a gráf bármely ciklusa egy olyan lemez határa, amelyet a gráf más része nem metsz [20] . Ilyen típusú rajzot úgy kaphatunk, hogy a gráf sík részét egy síkra rajzoljuk, a grafikon tetejét a sík fölé helyezzük, és szegmensekkel összekötjük a szomszédaival. A hivatkozások nélküli beágyazható gráfok kiskorú-zárt családot alkotnak hét gráftal a Petersen családból , mint minimálisan tiltott kiskorúakból [1] . Így ezek a gráfok tiltott minorok a csúcsgráfoknál is. Vannak azonban olyan grafikonok, amelyek hivatkozás nélkül beágyazhatók, és nem csúcsosak.

YΔY-redukálhatóság

Egy összefüggő gráf YΔY-redukálható, ha egyetlen csúcsra redukálható lépések sorozatával, amelyek mindegyike Δ-Y vagy Y-Δ transzformáció , hurkot vagy több élt eltávolítva, egy csúcsot egy szomszéddal, és egy második fokú csúcsot és két szomszédos élét egy éllel helyettesítjük [3] .

A csúcsgráfokhoz és a linkek nélküli beágyazható gráfokhoz hasonlóan az YΔY-re redukálható gráfok is bezáródnak a minorok generálása során. A csatolás nélküli beágyazható gráfokhoz hasonlóan az YΔY-re redukálható gráfok hét gráfot tartalmaznak a Petersen családból , mint minimálisan tiltott kiskorúak, ami felveti a kérdést, hogy ezek a gráfok az egyetlen tiltott kiskorúak, és hogy az YΔY-re redukálható gráfok és a beágyazható gráfok családjai egybeesnek-e . Neil Robertson azonban példát hozott egy olyan csúcsgráfra, amely nem YΔY-redukálható. Mivel bármely csúcsgráf beágyazható hivatkozás nélkül, ez azt mutatja, hogy vannak olyan hivatkozás nélküli beágyazható gráfok, amelyek nem YΔY-re redukálhatók, és ezért vannak további tiltott minorok az YΔY-re redukálható gráfokhoz [3] .

A csúcs Robertson-gráf az ábrán látható. Ezt úgy kaphatjuk meg, hogy a csúcsot összekapcsoljuk a harmadik fokú rombikus dodekaéder összes csúcsával, vagy a négydimenziós hiperkocka gráf két ellentétes csúcsát összevonjuk . Mivel a rombikus dodekaéder gráfja sík, a Robertson-gráf csúcsa. A gráf nem tartalmaz háromszögeket , és minimum négyes foka van, ezért semmilyen YΔY-redukciós művelet [3] nem alkalmazható rá .

Szinte sík gráfok

Ha egy gráf csúcs, akkor nem feltétlenül van egyetlen csúcsa. Például a K 5 és K 3,3 kisebb-minimális nem síkbeli gráfokban bármelyik csúcs kiválasztható csúcsnak. Wagner [21] [22] egy majdnem sík gráfot nem síkbeli csúcsgráfként definiált , amelyben bármely csúcs szolgálhat csúcsként. Így K 5 és K 3,3 szinte sík gráfok. Megadta az ilyen gráfok osztályozását, négy családba osztotta őket. Az egyik család gráfokból áll, amelyek (a Möbius-létrákhoz hasonlóan ) beágyazhatók egy Möbius-csíkba oly módon, hogy a csík éle egybeesik a gráf Hamilton-ciklusával . Még a négyszín- tétel bizonyítása előtt bebizonyította, hogy bármely majdnem sík gráf legfeljebb négy színnel színezhető, kivéve azokat a gráfokat, amelyeket páratlan külső ciklusú kerékből alakítanak ki, a központi csúcsot két szomszédos csúcsra cserélve. egy ilyen grafikonhoz öt szín kell. Ezenkívül bebizonyította, hogy egy kivétellel (a kocka nyolc csúcsú komplementere ) minden majdnem sík gráfnak van beágyazása a projektív síkba .

A "majdnem sík gráf" kifejezés azonban nagyon kétértelmű – ugyanezt a kifejezést használták a csúcsgráfokra [20] [4] , a síkgráfhoz egyetlen él hozzáadásával létrehozott gráfokra [23] , a síkbeli beágyazásból kialakított gráfokra. egy gráf korlátozott számú lapjának, korlátozott útszélességű "örvényszele" [24] , valamint néhány más, kevésbé szigorúan meghatározott gráfkészlet helyettesítésével.

Jegyzetek

  1. ↑ 12 Robertson, Seymour, Thomas, 1993b .
  2. ↑ 1 2 3 Robertson, Seymour, Thomas, 1993a .
  3. ↑ 1 2 3 4 Truemper, 1992 .
  4. ↑ 1 2 3 4 Eppstein, 2000 .
  5. ↑ 1 2 Demaine, Hajiaghayi, 2004 .
  6. ↑ 1 2 Gupta, Impagliazzo, 1991 .
  7. ↑ Pierce, 2014 .
  8. ↑ Kawarabayashi, 2009 .
  9. ↑ Lewis, Yanakakis, 1980 .
  10. ↑ Jørgensen, 1994 .
  11. ↑ Jorgensen sejtése , < http://www.openproblemgarden.org/op/jorgensens_conjecture > . Letöltve: 2016. november 13. Archiválva : 2016. november 14. a Wayback Machine -nél . 
  12. ↑ Kawarabayashi, Norine, Thomas, Wollan, 2012 .
  13. ↑ Frick, Grohe, 2001 .
  14. ↑ Demaine, Hajiaghayi, 2005 .
  15. ↑ Demaine, Hajiaghayi, Kawarabayashi, 2009 .
  16. ↑ Grohe, 2003 .
  17. ↑ Mohar, 2001 .
  18. ↑ Chimani, Gutwenger, Mutzel, Wolf, 2009 .
  19. ↑ Cabello, Mohar, 2010 .
  20. ↑ 12 Robertson, Seymour, Thomas, 1993c .
  21. ↑ Wagner, 1967 .
  22. ↑ Wagner, 1970 .
  23. ↑ Archdeacon, Bonnington, 2004 .
  24. ↑ Abraham, Gavoille, 2006 .

Irodalom