Planární kryt - Planar cover

Graf C je rovinný obal grafu H. Krycí mapa je označena barvami vrcholů.

v teorie grafů, a rovinný kryt konečný graf G je konečný krycí graf z G to je samo o sobě a rovinný graf. Každý graf, který může být vložený do projektivní rovina má rovinný kryt; nevyřešená domněnka Seiya Negami uvádí, že jsou to jediné grafy s rovinnými kryty.[1]

Existence rovinného krytu je a malá uzavřená vlastnost grafu,[2] a tak je lze charakterizovat konečně mnoha zakázané nezletilé, ale přesná sada zakázaných nezletilých není známa. Ze stejného důvodu existuje a polynomiální čas algoritmus pro testování, zda má daný graf planární krytí, ale explicitní popis tohoto algoritmu není znám.

Definice

A krycí mapa z jednoho grafu C do jiného grafu H lze popsat funkcí F z vrcholů C na vrcholy H že pro každý vrchol proti z C, dává bijekce mezi sousedé z proti a sousedé z F(proti).[3] Li H je připojený graf, každý vrchol H musí mít stejný počet předběžných obrázků C;[2] toto číslo se nazývá vrstva mapy a C se nazývá a krycí graf z G. Li C a H jsou obě konečné a C je rovinný graf, pak C se nazývá rovinné krytí H.

Příklady

Identifikace dvojic protilehlých vrcholů dvanáctistěn dává krycí mapu Petersenův graf

Graf dvanáctistěn má symetrie který mapuje každý vrchol na antipodální vrchol. Na množinu antipodálních párů vrcholů a jejich sousedství lze nahlížet jako na graf Petersenův graf. Dvanáctistěn tvoří rovinný obal tohoto neplanárního grafu.[4] Jak ukazuje tento příklad, ne každý graf s rovinným krytem je rovinný. Pokud však rovinný graf pokrývá nerovinný graf, vrstva musí být sudé číslo.[5]

The dodecagonal hranol může tvořit dvouvrstvý kryt šestihranný hranol, třívrstvý kryt krychle, nebo čtyřvrstvý potah trojúhelníkový hranol.

Graf a k-gonal hranol má 2k vrcholy a je rovinný se dvěma k-gon tváře a k čtyřúhelníkové tváře. Li k = ab, s A ≥ 2 a b ≥ 3, pak má A- pokrýt mapu do a b-přední hranol, ve kterém dva vrcholy k-prism jsou mapovány na stejný vrchol b- hranol, pokud oba patří ke stejnému k-gonal face and the distance from one to the other is a multiple ofb. Například dodecagonal hranol může tvořit dvouvrstvý kryt šestihranný hranol, třívrstvý kryt krychle nebo čtyřvrstvý potah trojúhelníkový hranol. Tyto příklady ukazují, že graf může mít mnoho různých rovinných obalů a může být rovinným obalem pro mnoho dalších grafů. Navíc ukazují, že vrstva rovinného krytu může být libovolně velká. Nejsou jedinými kryty zahrnujícími hranoly: například šestihranný hranol může pokrýt i nerovinný graf, obslužný graf K.3,3, identifikací antipodálních párů vrcholů.[6]

Operace zachování krytu

Pokud graf H má rovinný kryt, stejně tak každý graf minor z H.[2] Nezletilý G z H mohou být vytvořeny odstraněním hran a vrcholů z Ha smršťováním okrajů H. Krycí graf C lze transformovat stejným způsobem: pro každou odstraněnou hranu nebo vrchol v H, odstranit jeho preimage v Ca pro každou smrštěnou hranu nebo vrchol v H, zazmluvněte jeho preimage v C. Výsledek použití těchto operací na C je nezletilá z C který pokrývá G. Jelikož každá menší rovinný graf je rovinný, poskytuje rovinné pokrytí menší G.

Protože grafy s rovinnými kryty jsou uzavřeny za provozu odběru nezletilých, vyplývá to z Věta Robertson – Seymour že je lze charakterizovat konečnou množinou zakázané nezletilé.[7] Graf je pro tuto vlastnost zakázaný menší, pokud nemá rovinné krytí, ale všichni jeho nezletilí mají rovinné kryty. Tuto charakteristiku lze použít k prokázání existence a polynomiální čas algoritmus, který testuje existenci rovinného krytu tím, že vyhledá každého ze zakázaných nezletilých a vrátí, že planární kryt existuje, pouze pokud toto hledání nenalezne ani jednoho z nich.[8] Protože však není známa přesná sada zakázaných nezletilých pro tuto vlastnost, je to důkaz existence nekonstruktivní, a nevede k explicitnímu popisu souboru zakázaných nezletilých osob nebo algoritmu na nich založeném.[9]

Další operace grafu která zachovává existenci rovinného krytu je Transformace Y-Δ, který nahradí jakýkoli vrchol třetího stupně grafu H trojúhelníkem spojujícím jeho tři sousedy.[2] Rub této transformace, transformace Δ-Y, však nutně nezachovává rovinné kryty.

Navíc, a disjunktní unie dvou grafů, které mají kryty, bude mít také obal, vytvořený jako disjunktní spojení krycích grafů. Pokud mají dva kryty stejnou vrstvu navzájem, pak to bude také vrstva jejich spojení.

Negamiho domněnka

Question, Web Fundamentals.svgNevyřešený problém v matematice:
Má každý připojený graf s rovinným krytem zabudování do projektivní roviny?
(více nevyřešených úloh z matematiky)

Pokud graf H má vkládání do projektivní rovina, pak to nutně má rovinný kryt, daný preimage H v orientovatelný dvojitý kryt projektivní roviny, což je koule.Negami (1986) naopak prokázal, že pokud a připojený graf H má pak dvouvrstvý rovinný kryt H musí mít zapuštění do projektivní roviny.[10] Předpoklad, že H je zde připojeno, je to nutné, protože disjunktní spojení projektivně-planárních grafů nemusí samo o sobě být projektivně-planární[11] ale stále bude mít rovinný kryt, disjunktní spojení orientovatelných dvojitých krytů.

A pravidelné krytí grafu H je ten, který pochází z skupina symetrií jeho krycího grafu: preimages každého vrcholu v H jsou obíhat skupiny. Negami (1988) dokázal, že každý připojený graf s rovinným pravidelným krytem lze vložit do projektivní roviny.[12] Na základě těchto dvou výsledků se domníval, že ve skutečnosti je každý propojený graf s rovinným krytem projektivní.[13]Od roku 2013 zůstává tato domněnka nevyřešená.[14] Je také známý jako Negamiho „dohad 1–2 ∞“, protože jej lze přeformulovat jako tvrzení, že minimální vrstva rovinného krytu, pokud existuje, musí být buď 1 nebo 2.[15]

K.1,2,2,2, jediný možný minimální protiklad Negamiho domněnky

Stejně jako grafy s rovinnými kryty lze grafy s vložením projektivní roviny charakterizovat zakázanými nezletilými. V tomto případě je známa přesná sada zakázaných nezletilých: je jich 35. 32 z nich je spojených a jeden z těchto 32 grafů se nutně jeví jako vedlejší v každém připojeném neprojektivně-planárním grafu.[16] Od té doby, co Negami vyslovil domněnku, bylo prokázáno, že 31 z těchto 32 zakázaných nezletilých buď nemá rovinné kryty, nebo je lze snížit transformací Y-Δ na jednodušší graf na tomto seznamu.[17] Zbývající graf, pro který to ještě nebylo provedeno, je K.1,2,2,2, sedm vrcholů vrcholový graf který tvoří kostru čtyřrozměrného oktaedrická pyramida. Li K.1,2,2,2 mohlo by být prokázáno, že nemá žádné rovinné kryty, což by dokončilo důkaz domněnky. Na druhou stranu, pokud je domněnka nepravdivá, K.1,2,2,2 by nutně byl jeho nejmenším protikladem.[18]

Související domněnka od Michael Fellows, nyní vyřešen, se týká rovinných emulátory, zobecnění rovinných krytů, které mapuje sousedství grafů spíše surjektivně než bijektivně.[19] Grafy s rovinnými emulátory, stejně jako grafy s rovinnými kryty, jsou uzavřeny pod nezletilými a transformacemi Y-Δ.[20] V roce 1988, nezávisle na Negami, Fellows předpokládal, že grafy s planárními emulátory jsou přesně grafy, které lze vložit do projektivní roviny.[21] Domněnka platí pro pravidelný emulátory, pocházející z automomorfismů podkladového krycího grafu, výsledkem analogickým výsledku Negami (1988) pro pravidelné planární kryty.[22]Ukázalo se však, že několik z 32 připojených zakázaných nezletilých pro projektivně-planární grafy má planární emulátory.[23] Fellowsova domněnka je proto nepravdivá. Nalezení úplného souboru zakázaných nezletilých pro existenci planárních emulátorů zůstává otevřeným problémem.[24]

Poznámky

  1. ^ Hliněný (2010), str. 1
  2. ^ A b C d Hliněný (2010), Tvrzení 1, s. 2
  3. ^ Hliněný (2010), Definice, str. 2
  4. ^ Inkmann & Thomas (2011): "Tato konstrukce je znázorněna na obrázku 1, kde je dodekaedr zobrazen jako rovinný dvojitý kryt Petersenova grafu."
  5. ^ Arciděkan a Richter (1990); Negami (2003).
  6. ^ Zelinka (1982)
  7. ^ Robertson & Seymour (2004)
  8. ^ Robertson & Seymour (1995)
  9. ^ Fellows & Langston (1988); Fellows & Koblitz (1992). Nekonstruktivita algoritmického testování existence k-fold rovinné kryty jsou uvedeny výslovně jako příklad od Fellows a Koblitz.
  10. ^ Negami (1986); Hliněný (2010), Věta 2, s. 2
  11. ^ Například dva Kuratowského grafy jsou projektivně-planární, ale žádné spojení dvou z nich není (Arciděkan 1981 ).
  12. ^ Negami (1988); Hliněný (2010), Věta 3, s. 3
  13. ^ Negami (1988); Hliněný (2010), Domněnka 4, str. 4
  14. ^ Chimani a kol. (2013)
  15. ^ Huneke (1993)
  16. ^ Hliněný (2010), str. 4; seznam zakázaných projektivně-planárních nezletilých je z Arciděkan (1981). Negami (1988) místo toho uvedl odpovídající pozorování pro 103 neredukovatelných neprojektivních planárních grafů daných Glover, Huneke & Wang (1979).
  17. ^ Negami (1988); Huneke (1993); Hliněný (1998); Arciděkan (2002); Hliněný (2010), s. 4–6
  18. ^ Hliněný (2010), s. 6–9
  19. ^ Fellows (1985); Kitakubo (1991); Hliněný (2010), Definice, str. 9
  20. ^ Hliněný (2010), Tvrzení 13, s. 9. Hliněný to připočítá Fellows a píše, že jeho důkaz je netriviální.
  21. ^ Hliněný (2010), Domněnka 14, str. 9
  22. ^ Kitakubo (1991).
  23. ^ Hliněný (2010), s. 9–10; Rieck & Yamashita (2010); Chimani a kol. (2013)
  24. ^ Hliněný (2010), str. 10

Reference

Sekundární zdroje o Negamiho domněnce

  • Hliněný, Petr (2010), „20 let Negamiho planárního dohadu“ (PDF), Grafy a kombinatorika, 26 (4): 525–536, doi:10.1007 / s00373-010-0934-9, PAN  2669457, S2CID  121645. Čísla stránek v poznámkách odkazují na verzi předtisku.
  • Huneke, John Philip (1993), „dohad v teologii topologické grafy“, Teorie struktury grafů (Seattle, WA, 1991), Současná matematika, 147„Providence, RI: American Mathematical Society, s. 387–389, doi:10.1090 / conm / 147/01186, PAN  1224718.

Primární zdroje o plošných krytech

Podpůrná literatura