Möbiův–Cantorův graf | |
---|---|
Pojmenoval podle | August Ferdinand Möbius a Z. Kantor |
Vrcholy | 16 |
žebra | 24 |
Poloměr | čtyři |
Průměr | čtyři |
obvod | 6 |
Automorfismy | 96 |
Chromatické číslo | 2 |
Chromatický index | 3 |
Rod | jeden |
Vlastnosti |
symetrický Hamiltonův bipartitní kubická jednotka vzdálenost Cayleyův graf dokonalý jednoduše orientovatelný |
Möbius-Cantorův graf je symetrický bipartitní kubický graf s 16 vrcholy a 24 hranami, pojmenovaný po Augustu Ferdinandu Möbiovi a Seligmanu Cantorovi (1857–1903). To může být definováno jako zobecněný Petersenův graf , to znamená, že je tvořen vrcholy osmiúhelníku spojeného s osmiúhelníkovou hvězdou, ve které je každý bod připojen ke třetímu bodu v řadě.
Möbius v roce 1828 [1] nastolil otázku existence dvojice mnohoúhelníků se stranami v každém s tou vlastností, že vrcholy jednoho mnohoúhelníku leží na přímkách procházejících stranami druhého a naopak. Pokud takový pár existuje, pak vrcholy a strany těchto polygonů musí tvořit projektivní konfiguraci . Neboť v euklidovské rovině neexistuje žádné řešení , ale v roce 1882 Kantor [2] našel pár polygonů tohoto typu při zobecnění problému, ve kterém body a hrany patří do komplexní projektivní roviny , tedy v Cantorově řešení. , souřadnice vrcholů mnohoúhelníku jsou komplexní čísla . Cantorovo řešení pro dvojici vzájemně vepsaných čtyřúhelníků v komplexní projektivní rovině se nazývá Möbiova-Cantorova konfigurace . Möbius-Kantorův graf má svůj název podle Möbius-Cantorovy konfigurace, protože je to Leviho graf této konfigurace. Graf má jeden vrchol pro každý konfigurační bod a jeden bod pro každou trojici a hrany spojují dva vrcholy, pokud jeden vrchol odpovídá bodu a druhý trojici obsahující tento bod.
Möbiův-Cantorův graf je podgrafem čtyřrozměrného grafu hyperkrychle a vzniká odstraněním osmi hran z hyperkrychle [3] . Vzhledem k tomu, že hyperkrychle je graf jednotkové vzdálenosti , Möbius-Cantorův graf lze také nakreslit v rovině se všemi stranami jednotkové délky, ačkoli takové znázornění by vedlo ke křížení hran.
Möbiův-Cantorův graf nelze vložit do roviny bez průsečíků, jeho číslo křížení je 4 a je to nejmenší kubický graf s takovým počtem křížení [4] . Kromě toho je v grafu uveden příklad grafu, jehož všechny podgrafy mají počet průsečíků dva a více odlišný od počtu průsečíků samotného grafu [5] . Je však toroidní - je zde zapuštěno do torusu , ve kterém jsou všechny jeho plochy šestiúhelníky [6] . Duální graf tohoto vložení je hyperoktaedrový graf .
Dochází k ještě symetričtějšímu vnoření Möbiova-Cantorova grafu do dvojitého torusu , což je pravidelná mapa a má šest osmihranných ploch, ve kterých lze všech 96 symetrií grafu realizovat jako symetrie vnoření [7] . 96prvková skupina symetrie vkládání má Cayleyův graf , který lze vložit do dvojitého torusu. V roce 1984 se ukázalo, že se jedná o jedinou skupinu rodu dva [8] .
Socha DeWitta Godfreyho a Duana Martineze ve formě dvojitého torusu s vloženým Möbius-Kantorovým grafem byla vystavena v Technickém muzeu Slovinska na 6. slovinské mezinárodní konferenci o teorii grafů v roce 2007. V roce 2013 byla na Colgate University vystavena rotující verze sochy .
Möbius-Cantorův graf připouští vložení do trojitého torusu (torus třetího druhu), který dává pravidelnou mapu se čtyřmi 12-gonálními plochami; [6] .
V roce 2004 byla v rámci studia možných chemických uhlíkových struktur studována rodina všech vnoření Möbiova-Cantorova grafu ve dvourozměrných varietách , v důsledku čehož se ukázalo, že existuje 759 neekvivalentních vložení [9]. .
Grupa automorfismu Möbiova-Cantorova grafu je grupa řádu 96 [10] . Působí tranzitivně na vrcholy a hrany, takže Möbiův-Cantorův graf je symetrický . Má automorfismy, které mapují jakýkoli vrchol na jakýkoli jiný a jakoukoli hranu na jakoukoli jinou. Podle Fosterova seznamu je Möbiův-Cantorův graf jediným symetrickým grafem s 16 vrcholy a nejmenším kubickým symetrickým grafem, který není tranzitivní na vzdálenost [11] . Möbius-Cantorův graf je také grafem Cayleyho .
Zobecněný Petersenův graf je vertex-tranzitivní tehdy a jen tehdy a , nebo když , a hranově tranzitivní pouze v následujících sedmi případech: [12] . Möbiův-Cantorův graf je tedy jedním z těchto sedmi hranově tranzitivních zobecněných Petersenových grafů. Jeho symetrické zapuštění do dvojitého torusu je jednou ze sedmi pravidelných kubických map, u nichž je celkový počet vrcholů dvojnásobkem počtu vrcholů ploch [13] . Mezi sedmi symetrickými zobecněnými Petersenovými grafy jsou kubický graf , Petersenův graf , dvanáctistěnný graf , Desarguesův graf a Naurův graf .
Charakteristický polynom Möbiova-Cantorova grafu je roven: