Sík burkolat

Egy G véges gráf síkbeli lefedése G  véges fedőgráfja , amely síkgráf . A projektív síkba beágyazható gráfok síkfedelűek. Seiya Negami megfejtetlen sejtése azt állítja, hogy csak ezeknek a gráfoknak van síkfedője [1] .

A síkburkolat megléte kiskorúak elől elzárt ingatlan [2] , ezért véges számú tiltott kiskorúval leírható , de a tiltott kiskorúak pontos halmaza nem ismert. Ugyanezen okok miatt létezik egy polinomiális idő algoritmus annak tesztelésére, hogy egy adott gráfnak van-e síkbeli lefedése, de ennek az algoritmusnak nincs egyértelmű leírása.

Definíció

Az egyik C gráfból egy másik H gráfba való fedőleképezés leírható egy f függvénnyel C csúcsaiból H csúcsaiba , amely C minden v csúcsára bijekciót hoz létre v szomszédsága és f szomszédsága között ( v ) [3] . Ha H egy összefüggő gráf , akkor H minden csúcsának ugyanannyi csúcsnak kell lennie a C előképében [2] . Ezt a számot a térkép rétegeinek számának, C -t pedig G fedőgráfjának nevezzük . Ha C és H is véges, és C síkgráf , akkor C - t H síkbeli fedőjének nevezzük .

Példák

A szabályos dodekaéder gráfjának szimmetriája van , amely minden csúcsot leképez egy antipodális csúcsra. Az antipodális csúcspárok és szomszédosságaik halmaza gráfként, a Petersen-gráfként is felfogható . A dodekaéder ennek a nem síkbeli gráfnak síkbeli borítását képezi [4] . Ez a példa azt mutatja, hogy nem minden gráf síkbeli lefedéssel önmagában sík. Ha egy síkgráf egy nem síkbeli gráfot fed le, a rétegek számának párosnak kell lennie [5] [6] .

A k -szögű prizma gráfjának 2k csúcsa van, és két k -szögű lappal és k négyzetlappal síkbeli. Ha k  =  ab , és , akkor a gráfnak van egy a -rétegű leképeződése egy b -oldalas prizmára, amelyben a k -prizma két csúcsa a b -prizma ugyanazon csúcsára van leképezve, ha mindkettő ugyanahhoz tartozik. k -szöglapok és az egyik és a másik közötti távolság b többszöröse . Például egy kétszögletű prizma képezhet egy hatszögletű prizma 2 rétegű, egy kocka 3 rétegű vagy egy háromszög prizma 4 rétegű borítását . Ezek a példák azt mutatják, hogy egy gráfnak sok különböző síkfedője lehet, és sok gráf síkbeli fedője lehet. Ezen túlmenően ezek a példák azt mutatják, hogy egy sík burkolat szála tetszőlegesen nagy lehet. Nem csak prizmákat fednek le, például egy hatszögletű prizma lefedhet egy nem síkbeli K 3,3 közösségi gráfot is antipodális csúcspárok azonosításával [7] .

Fedélvédő műveletek

Ha a H gráfnak síkbeli borítása van, akkor ugyanez igaz a H gráf bármely kisebb gráfjára [2] . A H gráf kisebb G -jét úgy alakíthatjuk ki, hogy H-ból eltávolítunk éleket és csúcsokat, és az éleket H -ba húzzuk össze . A C fedőgráf ugyanígy transzformálható - minden H -ből eltávolított csúcshoz eltávolítjuk a C -beli előképét , és minden H -ból összehúzott él vagy csúcs előképét C -re zsugorítjuk . Ezen műveletek eredménye C-n a C - nek egy mollja lesz , amely lefedi G -t . Mivel a síkgráf bármely mollja maga is sík, ez G molljának síkbeli lefedését adja .

Mivel a síkborítású gráfok a kiskorúak elvételének művelete alatt záródnak, a Robertson-Seymour- tételből következik, hogy a tiltott kiskorúak véges halmazával írhatók le [8] . Egy gráf tiltott minor ehhez a tulajdonsághoz, ha nincs síkborítója, de minden mellékének síkborítója van. Ez a leírás használható egy olyan polinomiális idő algoritmus létezésének bizonyítására , amely minden tiltott kisebbre keresve teszteli a síkfedő létezését, és ha a keresés nem talál egyet sem, akkor a "síkfedés létezik" eredményt ad vissza [9] . Mivel azonban a tiltott kiskorúak pontos halmaza ehhez a tulajdonsághoz nem ismert, ez a létezés bizonyítéka nem építő jellegű, és nem vezet a tiltott kiskorúak halmazának kifejezett leírásához vagy az ezeken alapuló algoritmushoz [10]

Egy másik gráfokon végzett művelet, amely megőrzi a síkborítás létezését, a csillag-háromszög transzformáció , amely a H - beli bármely harmadik fokú csúcsot a három szomszédjából álló háromszögre cseréli [2] . Az inverz transzformáció, a delta-csillag transzformáció azonban nem feltétlenül őrzi meg a síkborításokat.

Sőt, két fedővel rendelkező gráf diszjunkt uniójának is lesz fedője, amely a fedőgráfok diszjunkt uniójaként jön létre. Ha két burkolatnak ugyanaz a szála, akkor ez lesz az egyesülésük szála is.

Negami hipotézise

Megoldatlan matematikai problémák : Bármely sík borítású kapcsolódó gráfnak van beágyazása a projektív síkban?

Ha egy H gráfnak van beágyazása a projektív síkban , akkor szükségszerűen síkbeli borítása van, amelyet H inverz képe ad a projektív sík orientálható kettős fedelében , amely egy gömb. Negami [11] ennek az ellenkezőjét bizonyította, hogy ha egy összefüggő H gráfnak kétrétegű síkborítása van, akkor H - nak beágyazottnak kell lennie a projektív síkban [11] [12] . Az a feltételezés, hogy H összefügg, azért szükséges, mert a projektív síkbeli gráfok diszjunkt uniója lehet, hogy nem projektíven sík [13] , de van egy síkfedője, az orientálható kettős fedések diszjunkt uniója.

A H gráf szabályos lefedése a fedőgráf szimmetriacsoportjából  származó borítás – a H -beli csúcsok inverz képei a csoport pályáját alkotják . Negami [14] bebizonyította, hogy bármely síkbeli szabályos lefedéssel rendelkező, összefüggő gráf beágyazható projektív síkba [14] [15] . E két eredmény alapján azt sejtette, hogy valójában minden síkbeli lefedéssel rendelkező gráf projektív [14] [16] . 2013-ig a hipotézis megoldatlan maradt [17] . Negami sejtésnek is nevezik , mivel újrafogalmazható úgy, hogy egy síkburkolat minimális rostszáma, ha van ilyen, 1 vagy 2 legyen [18] .

A síkborítású gráfokhoz hasonlóan a projektív síkban beágyazott gráfokat is leírhatják a tiltott kiskorúak. Ebben az esetben a tiltott kiskorúak pontos halmaza ismert, van belőlük 35. Ebből 32 összefüggő, és ebből a 32 gráfból egy szükségszerűen kiskorúként jelenik meg bármely összefüggő nem projektív síkgráfban [19] [20] . Amikor Negami előadta sejtését, bebizonyosodott, hogy ebből a 32 tiltott kiskorú közül 31-nek nincs síkfedője, vagy csillag-háromszög transzformációval egyszerűbb gráfokra redukálható ebből a listából [14] [18] [21] [22 ] [ 23] . Az egyetlen megmaradt gráf, amelynél ez még nem történt meg, a K 1,2,2,2 , egy hét csúcsú csúcsgráf, amely egy négydimenziós oktaéderes piramis vázát alkotja . Ha megmutatjuk, hogy K 1,2,2,2 -nek nincsenek síkfedői, ez a sejtés teljes bizonyítéka lesz. Másrészt, ha a sejtés nem igaz, akkor K 1,2,2,2 minimális ellenpélda lesz [24] .

Michael Fellows egy, már megoldott, kapcsolódó sejtése a sík emulátorokról szól , a sík lefedések általánosításáról, ahol a gráfkörnyékek szürjektív, nem pedig bijektív módon vannak leképezve [25] [26] [27] . A síkbeli emulátorokkal rendelkező gráfok, akárcsak a síkborítású gráfok [29][28], a minorok és a csillag-háromszög transzformációk [30] alatt zárva vannak . A sejtés igaz a mögöttes fedőgráf automorfizmusaiból származó reguláris emulátorokra, hasonlóan Negami eredményéhez [14] a reguláris síkfedésekre [26] . Kiderült azonban, hogy a projektív síkgráfokhoz kapcsolt 32 tiltott minor közül néhány rendelkezik planáris emulátorral [31] [32] [17] . Ezért a Fellowes-hipotézis nem helytálló. A tiltott kiskorúak teljes készletének megtalálása a planáris emulátorok létezéséhez továbbra is nyitott probléma [33] .

Jegyzetek

  1. ↑ Hliněny, 2010 , p. egy.
  2. ↑ 1 2 3 4 Hliněný, 2010 , p. 2 1. javaslat.
  3. ↑ Hliněny, 2010 , p. 2 Definíció.
  4. ↑ Inkmann, Thomas (2011 ): "Ezt a konstrukciót az 1. ábra szemlélteti, ahol a dodekaéder a Petersen-gráf síkbeli kettős lefedéseként látható."
  5. ↑ Főesperes, Richter, 1990 .
  6. ↑ Negami, 2003 .
  7. ↑ Zelinka, 1982 .
  8. ↑ Robertson, Seymour, 2004 .
  9. ↑ Robertson, Seymour, 1995 .
  10. ↑ Fellows, Langston (1988 ); Fellows, Koblitz (1992 ). Fellowes és Koblitz példaként mutatta be a k -szeres síkborítások létezésének algoritmikus ellenőrzésének nonkonstruktivitását.
  11. ↑ Negami 12. , 1986 .
  12. ↑ Hliněny, 2010 , p. 2 2. tétel.
  13. ↑ Például két Kuratowski-gráf projektív síkbeli, kettőjük bármilyen uniója nem ( Archdeacon 1981 ).
  14. ↑ 1 2 3 4 5 Negami, 1988 .
  15. ↑ Hliněny, 2010 , p. 3 3. tétel.
  16. ↑ Hliněny, 2010 , p. 4 Sejtés 4.
  17. ↑ 1 2 Chimani, Derka, Hliněny, Klusáček, 2013 .
  18. ↑ 12 Huneke , 1993 .
  19. ↑ Hliněny, 2010 , p. négy.
  20. ↑ A tiltott projektív síkbeli kiskorúak listája megtalálható: Archdeacon (1981 ). Negami Negami (1988 ) megerősítette a megfelelő megfigyelést 103 irreducibilis, nem projektív síkgráfra vonatkozóan Glover, Huneke, Wang (1979 ).
  21. ↑ Hliněny, 1998 .
  22. ↑ Főesperes, 2002 .
  23. ↑ Hliněny, 2010 , p. 4–6.
  24. ↑ Hliněny, 2010 , p. 6–9.
  25. ↑ Fellows, 1985 .
  26. ↑ 12 Kitakubo , 1991 .
  27. ↑ Hliněny, 2010 , p. 9 Meghatározás, o.
  28. ↑ Hliněny, 2010 , p. 9 13. javaslat.
  29. ↑ Glineny ezt a tényt Fellowsnak tulajdonítja, és azt írja, hogy a bizonyítéka nem triviális
  30. ↑ Hliněny, 2010 , p. 9, sejtés 14.
  31. ↑ Hliněny, 2010 , p. 9–10.
  32. ↑ Rieck, Yamashita, 2010 .
  33. ↑ Hliněny, 2010 , p. tíz.

Irodalom

Másodlagos források a Negami-sejtésről

Fő források a síkburkolatokról

Kiegészítő irodalom