Nauru graf - Nauru graph - Wikipedia
Nauru graf | |
---|---|
![]() Nauruový graf je hamiltoniánský. | |
Vrcholy | 24 |
Hrany | 36 |
Poloměr | 4 |
Průměr | 4 |
Obvod | 6 |
Automorfismy | 144 (S.4× S.3) |
Chromatické číslo | 2 |
Chromatický index | 3 |
Tloušťka knihy | 3 |
Číslo fronty | 2 |
Vlastnosti | Symetrický Krychlový Hamiltonian Integrální Cayleyův graf Bipartitní |
Tabulka grafů a parametrů |
V matematický pole teorie grafů, Nauru graf je symetrický bipartitní kubický graf s 24 vrcholy a 36 hranami. Pojmenoval ji David Eppstein po dvanácticípé hvězdě v vlajka Nauru.[1]
Má to chromatické číslo 2, chromatický index 3, průměr 4, poloměr 4 a obvod 6.[2] Je to také 3-připojen k vrcholu a 3-připojeno k okraji graf. Má to tloušťka knihy 3 a číslo fronty 2.[3]
Nauruový graf vyžaduje alespoň osm křížení při jakémkoli jeho vykreslení v rovině. Je to jeden z pěti neizomorfních grafů, které jsou svázány jako nejmenší kubický graf, který vyžaduje osm křížení. Dalším z těchto pěti grafů je McGeeův graf, také známý jako (3-7) -klec.[4][5]
Konstrukce
Graf Nauru je Hamiltonian a lze je popsat v LCF notace : [5, −9, 7, −7, 9, −5]4.[1]
Nauruův graf lze také zkonstruovat jako zobecněný Petersenův graf G(12, 5), který je tvořen vrcholy a dodekagon připojen k vrcholům dvanáctibodové hvězdy, ve které je každý bod hvězdy spojen s body vzdálenými pět kroků od ní.
K dispozici je také kombinatorická konstrukce grafu Nauru. Vezměte tři rozlišitelné objekty a umístěte je do čtyř odlišitelných polí, ne více než jeden objekt na pole. Existuje 24 způsobů, jak tak rozdělit objekty, což odpovídá 24 vrcholům grafu. Pokud je možné přejít z jednoho stavu do jiného stavu přesunutím přesně jednoho objektu z jeho současného umístění do prázdného pole, pak jsou vrcholy odpovídající dvěma stavům spojeny hranou. Výsledný graf přechodu stavu je graf Nauru.
Algebraické vlastnosti
Skupina automorfismu na Nauru grafu je skupina řádu 144.[6] Je izomorfní s přímý produkt z symetrické skupiny S4 a S3 a působí přechodně na vrcholy, na hrany a na oblouky grafu. Proto je graf Nauru a symetrický graf (i když ne vzdálenost tranzitivní ). Má automatorfismy, které berou jakýkoli vrchol na jakýkoli jiný vrchol a jakoukoli hranu na jakoukoli jinou hranu. Podle Podporovat sčítání lidu, Nauruův graf je jediný kubický symetrický graf na 24 vrcholech.[2]
Zobecněný Petersenův graf G(n, k) je vrcholem tranzitivní právě tehdy n = 10 a k = 2 nebo pokud k2 ≡ ± 1 (modn) a je hraniční tranzitivní pouze v následujících sedmi případech: (n, k) = (4,1), (5,2), (8,3), (10,2), (10,3), (12,5), (24,5).[7] Nauruův graf je tedy jedním z pouhých sedmi symetrických generalizovaných Petersenových grafů. Mezi těmito sedmi grafy jsou krychlový graf , Petersenův graf , Möbius – Kantorův graf , dodekahedrální graf a Desargues graf .
Nauruův graf je a Cayleyův graf z S4, symetrická skupina permutací na čtyřech prvcích, generovaná třemi různými způsoby záměny prvního prvku za jeden ze tří ostatních: (1 2), (1 3) a (1 4).
The charakteristický polynom grafu Nauru se rovná
dělat to integrální graf — Graf, jehož spektrum skládá se výhradně z celých čísel.
Symetrické zapuštění do torusu vytvořeného slepením protilehlých okrajů pravidelného šestiúhelníku
Zobecněný Petersenův graf, barevný a označený jako Cayleyův graf S4
Matice sousedství. Každá hrana je reprezentována dvěma symetricky umístěnými položkami ve stejné barvě
1-planární kresba s 8 kříženími
24 orientací válcování osmistěn na trojúhelníková mřížka, nakreslený na hexagonálním torusu
Topologické vlastnosti

Nauruův graf má dva různé vložení jako zobecněný pravidelný mnohostěn: topologická plocha rozdělená na hrany, vrcholy a plochy takovým způsobem, že existuje symetrie, která bere libovolné vlajka (incident trojnásobek vrcholu, hrany a obličeje) do jakékoli jiné vlajky.[8]
Jedno z těchto dvou vložení tvoří a torus, takže graf Nauru je a toroidní graf: skládá se z 12 hexagonálních ploch spolu s 24 vrcholy a 36 hranami Nauru grafu. The duální graf tohoto vložení je symetrický 6 pravidelný graf s 12 vrcholy a 36 hranami.
Druhé symetrické vložení Nauru grafu má šest dodecagonal tváře a tvoří povrch rod 4. Jeho duální není a jednoduchý graf, protože každá tvář sdílí tři hrany se čtyřmi dalšími tvářemi, ale a multigraf. Tento dual může být vytvořen z grafu regulárního osmistěn nahrazením každého okraje svazkem tří rovnoběžných okrajů.
Sada ploch kteréhokoli z těchto dvou embeddings je sada Petrie polygony druhého vložení.
Geometrické vlastnosti

Stejně jako u všech zobecněných Petersenových grafů může být Nauruův graf reprezentován body v rovině takovým způsobem, že sousední vrcholy jsou v jednotkové vzdálenosti od sebe; to znamená, že je graf jednotkové vzdálenosti.[9] To a hranoly jsou jedinými zobecněnými Petersenovými grafy G(n,p), které nelze tak reprezentovat tak, aby symetrie výkresu tvořily cyklickou skupinu řádu n. Namísto toho má její graf znázornění jednotkové vzdálenosti dihedrální skupina Dih6 jako jeho skupina symetrie.
Dějiny
První osoba, která psala o grafu Nauru, byla R. M. Foster, ve snaze shromáždit všechny kubické symetrické grafy.[10] Celý seznam kubických symetrických grafů je nyní pojmenován po něm Foster Census a v tomto seznamu je graf Nauru očíslovaný graf F24A, ale nemá žádný konkrétní název.[11] V roce 1950 H. S. M. Coxeter citoval graf podruhé, čímž poskytl hamiltonovskou reprezentaci použitou k ilustraci tohoto článku a popsal ji jako Leviho graf a projektivní konfigurace objevil Zachariáš.[12][13]
V roce 2003 Ed Pegg napsal do svého online MAA sloupce, že F24A si zaslouží jméno, ale nenavrhl ho.[14] A konečně, v roce 2007, David Eppstein použil toto jméno Nauru graf protože vlajka z Republika Nauru má 12bodovou hvězdu podobnou té, která se objevuje v konstrukci grafu jako zobecněný Petersenův graf.[1]
Reference
- ^ A b C Eppstein, D., Mnoho tváří grafu Nauru, 2007.
- ^ A b Conder, M. a Dobcsányi, P. „Trivalentní symetrické grafy až do 768 vrcholů.“ J. Combin. Matematika. Kombinovat. Comput. 40, 41-63, 2002.
- ^ Wolz, Jessica; Inženýrské lineární rozložení se SAT. Diplomová práce, University of Tübingen, 2018
- ^ Sloane, N. J. A. (vyd.). "Pořadí A110507 (počet uzlů v nejmenším krychlovém grafu s křížením číslo n)". The On-line encyklopedie celočíselných sekvencí. Nadace OEIS..
- ^ Pegg, E. T.; Exoo, G. (2009), „Crossing number graphs“, Mathematica Journal, 11, archivovány z originál dne 06.03.2019, vyvoláno 2010-01-02.
- ^ Royle, G. Data F024A Archivováno 06.03.2011 na Wayback Machine
- ^ Frucht, R.; Graver, J. E.; Watkins, M. E. (1971), „Skupiny zobecněných Petersenových grafů“, Sborník řízení Cambridge Philosophical Society, 70: 211–218, doi:10.1017 / S0305004100049811.
- ^ McMullen, Peter (1992), „Pravidelný mnohostěn typu {p, 3} s 2p vrcholy ", Geometriae Dedicata, 43 (3): 285–289, doi:10.1007 / BF00151518.
- ^ Žitnik, Arjana; Horvat, Boris; Pisanski, Tomaž (2010), Všechny zobecněné Petersenovy grafy jsou grafy jednotkových vzdáleností (PDF), Předtisky IMFM, 1109.
- ^ Foster, R. M. (1932), „Geometrické obvody elektrických sítí“, Transakce Amerického institutu elektrotechniků, 51: 309–317, doi:10.1109 / T-AIEE.1932.5056068.
- ^ Bouwer, I.Z .; Chernoff, W. W .; Monson, B .; Hvězda, Z (1988), Pěstounské sčítání, Charles Babbage Research Center.
- ^ Coxeter, H. S. M. (1950), „Self-dual configurations and regular graphs“, Bulletin of the American Mathematical Society, 56: 413–455, doi:10.1090 / S0002-9904-1950-09407-5.
- ^ Zacharias, M. (1941), "Untersuchungen über ebene Konfigurationen (124, 163)", Deutsche Mathematik, 6: 147–170.
- ^ Pegg, ed (2003), Krychlové symetrické grafy, Mathematical Association of America.