Rovinná krytina

Rovinné pokrytí konečného grafu G  je konečné pokrytí grafu G , které je rovinným grafem . Každý graf, který lze vložit do projektivní roviny , má rovinný kryt. Nevyřešená domněnka Seiya Negami tvrdí, že pouze tyto grafy mají rovinné kryty [1] .

Existence rovinné krytiny je vlastnost uzavřená pod nezletilými [2] , a proto může být popsána konečným počtem zakázaných nezletilých , ale přesný soubor zakázaných nezletilých není znám. Ze stejných důvodů existuje polynomiální časový algoritmus pro testování, zda daný graf má rovinné pokrytí, ale není znám žádný explicitní popis tohoto algoritmu.

Definice

Krycí zobrazení z jednoho grafu C do druhého grafu H lze popsat funkcí f z vrcholů C do vrcholů H , která pro každý vrchol v z C vytváří bijekci mezi okolím v a okolím f ( v ) [3] . Je -li H souvislý graf , každý vrchol H musí mít stejný počet vrcholů v předobraze C [2] . Toto číslo se nazývá počet vrstev mapy a C se nazývá krycí graf G . Pokud jsou C i H konečné a C je rovinný graf , C se nazývá rovinné krytí H.

Příklady

Graf pravidelného dvanáctistěnu má symetrii , která mapuje každý vrchol na vrchol antipodální. Na množinu antipodálních párů vrcholů a jejich přilehlosti lze také pohlížet jako na graf, Petersenův graf . Dvanáctstěn tvoří rovinný obal tohoto nerovinného grafu [4] . Tento příklad ukazuje, že ne každý graf s rovinným pokrytím je sám rovinný. Když rovinný graf pokrývá nerovinný graf, musí být počet vrstev sudý [5] [6] .

Graf k -gonálního hranolu má 2k vrcholů a je rovinný se dvěma k -gonálními plochami a k ​​čtvercovými plochami. Je-li k  =  ab , a , pak má graf pokrytí a-vrstvy zobrazením na b - hranol, ve kterém jsou dva vrcholy k -hranolu mapovány na stejný vrchol b -hranolu, pokud oba patří ke stejnému k -gonálních ploch a vzdálenost od jedné k druhé je násobkem b . Například dvanáctihranný hranol může tvořit 2vrstvý kryt šestibokého hranolu , 3vrstvý kryt krychle nebo 4vrstvý kryt trojúhelníkového hranolu . Tyto příklady ukazují, že graf může mít mnoho různých rovinných krytů a může být rovinným krytem pro mnoho grafů. Navíc tyto příklady ukazují, že vlákno rovinné krytiny může být libovolně velké. Nepokrývají pouze hranoly, například šestiúhelníkový hranol může pokrýt i nerovinný komunální graf K 3,3 identifikací antipodálních párů vrcholů [7] .

Operace pro zachování obalu

Pokud má graf H rovinné pokrytí, pak totéž platí pro libovolný menší graf grafu H [2] . Menší G grafu H lze vytvořit odstraněním hran a vrcholů z H a stažením hran do H . Krycí graf C lze transformovat stejným způsobem - pro každý odstraněný vrchol z H odstraníme jeho předobraz v C a pro každou staženou hranu nebo vrchol z H jeho předobraz zmenšíme na C . Výsledkem těchto operací na C bude menší část C , která pokrývá G . Protože každý moll rovinného grafu je sám rovinný, dává to rovinné pokrytí moll G .

Vzhledem k tomu, že grafy s planárními kryty jsou při operaci odebírání nezletilých uzavřeny, vyplývá z Robertson-Seymourova teorému, že je lze popsat konečnou množinou zakázaných nezletilých [8] . Graf je pro tuto vlastnost zakázaný, pokud nemá rovinné pokrytí, ale všechny jeho podřadné položky rovinné kryty mají. Tento popis lze použít k prokázání existence polynomiálního časového algoritmu , který testuje existenci rovinného krytu hledáním každého zakázaného minoru a vrací „rovinný kryt existuje“, pokud toto hledání nenalezne žádné [9] . Protože však není znám přesný soubor zakázaných nezletilých pro tuto vlastnost, není tento důkaz existence konstruktivní a nevede k výslovnému popisu množiny zakázaných nezletilých nebo algoritmu na nich založeném [10]

Další operací na grafech , která zachovává existenci rovinného pokrytí, je transformace hvězda-trojúhelník , která nahradí libovolný vrchol třetího stupně v H trojúhelníkem jeho tří sousedů [2] . Inverzní transformace, transformace delta-hvězda, však nutně nezachovává rovinné kryty.

Navíc disjunktní sjednocení dvou grafů, které mají pokrytí, bude mít také obal vytvořený jako disjunktní sjednocení krycích grafů. Pokud mají dvě krytiny stejné vlákno, bude to také vlákno jejich spojení.

Negamiho hypotéza

Nevyřešené úlohy z matematiky : Jakýkoli souvislý graf s rovinným pokrytím má vložení do projektivní roviny?

Pokud má graf H zapuštění do promítací roviny , pak nutně má rovinné pokrytí dané inverzním obrazem H v orientovatelném dvojitém krytu promítací roviny, což je koule. Negami [11] dokázal opak, že má-li souvislý graf H dvouvrstvé rovinné pokrytí, pak H musí mít vnoření v projektivní rovině [11] [12] . Předpoklad, že H je souvislý, je zde nutný, protože disjunktní sjednocení projektivně rovinných grafů nemusí být projektivně rovinné [13] , ale stále má rovinný kryt, disjunktní sjednocení orientovatelných dvojitých krytů.

Pravidelné pokrytí grafu H  je pokrytí vyplývající ze grupy symetrie jeho krycího grafu – inverzní obrazy každého vrcholu v H tvoří orbitu grupy. Negami [14] dokázal, že do projektivní roviny lze vložit jakýkoli souvislý graf s rovinným pravidelným pokrytím [14] [15] . Na základě těchto dvou výsledků se domníval, že ve skutečnosti každý souvislý graf s rovinným pokrytím je projektivní [14] [16] . Od roku 2013 zůstala hypotéza nevyřešena [17] . Je také známá jako „ Negamiho domněnka“, protože ji lze přeformulovat jako tvrzení, že minimální počet vláken rovinné krytiny, pokud taková existuje, musí být buď 1 nebo 2 [18] .

Stejně jako grafy s rovinnými obaly mohou i grafy s vnořením do projektivní roviny popsat zakázaní nezletilí. V tomto případě je známa přesná množina zakázaných nezletilých, je jich 35. 32 z nich je souvislých a jeden z těchto 32 grafů se nutně objevuje jako minor v jakémkoli připojeném neprojektivním rovinném grafu [19] [20] . Když Negami předložil svou domněnku, bylo prokázáno, že 31 z těchto 32 zakázaných nezletilých buď nemá žádné rovinné kryty, nebo je lze redukovat transformací hvězda-trojúhelník na jednodušší grafy z tohoto seznamu [14] [18] [21] [22 ] [ 23] . Jediný zbývající graf, pro který to ještě nebylo provedeno, je K 1,2,2,2 , vrcholový graf se sedmi vrcholy, který tvoří kostru čtyřrozměrné oktaedrické pyramidy . Pokud ukážeme, že K 1,2,2,2 nemá žádné rovinné kryty, bude to úplný důkaz domněnky. Na druhou stranu, pokud domněnka není pravdivá, K 1,2,2,2 bude minimálním protipříkladem [24] .

Související domněnka Michaela Fellowse, již vyřešená, je o planárních emulátorech , zobecnění rovinných krytin, kde jsou sousedství grafu mapována spíše surjectivně než bijectivně [25] [26] [27] . Grafy s planárními emulátory, stejně jako grafy [29][28]s planárními kryty, jsou uzavřeny pod menšími a hvězdicovými transformacemi [30] . Tato domněnka platí pro regulární emulátory odvozené z automorfismů základního grafu pokrytí, podobně jako Negamiho výsledek [14] pro regulární planární pokrytí [26] . Ukázalo se však, že některé z 32 připojených zakázaných minorů pro projektivně rovinné grafy mají planární emulátory [31] [32] [17] . Fellowesova hypotéza proto není správná. Nalezení kompletní sady zakázaných nezletilých pro existenci planárních emulátorů zůstává otevřeným problémem [33] .

Poznámky

  1. ↑ Hliněny, 2010 , str. jeden.
  2. ↑ 1 2 3 4 Hliněný, 2010 , str. 2 Návrh 1.
  3. ↑ Hliněny, 2010 , str. 2 Definice.
  4. ↑ Inkmann, Thomas (2011 ): "Tato konstrukce je znázorněna na obrázku 1, kde je dvanáctistěn zobrazen jako rovinné dvojité pokrytí Petersenova grafu."
  5. ↑ Arciděkan, Richter, 1990 .
  6. ↑ Negami, 2003 .
  7. ↑ Zelinka, 1982 .
  8. ↑ Robertson, Seymour, 2004 .
  9. ↑ Robertson, Seymour, 1995 .
  10. ↑ Fellows, Langston (1988 ); Fellows, Koblitz (1992 ). Nekonstruktivnost algoritmické verifikace existence k - násobných rovinných pokrytí ukázali jako příklad Fellowes a Koblitz.
  11. ↑ 12. Negami , 1986 .
  12. ↑ Hliněny, 2010 , str. 2 Věta 2.
  13. ↑ Například dva Kuratowského grafy jsou projektivně rovinné, jakékoli spojení dvou z nich nikoliv ( Archdeacon 1981 ).
  14. ↑ 1 2 3 4 5 Negami, 1988 .
  15. ↑ Hliněny, 2010 , str. 3 Věta 3.
  16. ↑ Hliněny, 2010 , str. 4 Dohady 4.
  17. ↑ 1 2 Chimani, Derka, Hliněny, Klusáček, 2013 .
  18. ↑ 12 Huneke , 1993 .
  19. ↑ Hliněny, 2010 , str. čtyři.
  20. ↑ Seznam zakázaných projektivních planárních nezletilých lze nalézt v Archdeacon (1981 ). Negami Negami (1988 ) tvrdil odpovídající pozorování pro 103 neredukovatelných neprojektivních rovinných grafů z Glover, Huneke, Wang (1979 ).
  21. ↑ Hliněny, 1998 .
  22. ↑ Arciděkan, 2002 .
  23. ↑ Hliněny, 2010 , str. 4–6.
  24. ↑ Hliněny, 2010 , str. 6–9.
  25. ↑ Fellows, 1985 .
  26. ↑ 12 Kitakubo , 1991 .
  27. ↑ Hliněny, 2010 , str. 9 Definice, str.
  28. ↑ Hliněny, 2010 , str. 9 Návrh 13.
  29. ↑ Glineny tuto skutečnost připisuje Fellows a píše, že jeho důkaz není triviální
  30. ↑ Hliněny, 2010 , str. 9, domněnka 14.
  31. ↑ Hliněny, 2010 , str. 9–10.
  32. ↑ Rieck, Yamashita, 2010 .
  33. ↑ Hliněny, 2010 , str. deset.

Literatura

Sekundární zdroje o Negamiho dohadu

Hlavní zdroje na rovinných krytinách

Pomocná literatura