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]⁴.^[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 S₄ a S₃ 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 k² ≡ ± 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 ${ displaystyle G (4,1)}$, Petersenův graf ${ displaystyle G (5,2)}$, Möbius – Kantorův graf ${ displaystyle G (8,3)}$, dodekahedrální graf ${ displaystyle G (10,2)}$ a Desargues graf ${ displaystyle G (10,3)}$.

Nauruův graf je a Cayleyův graf z S₄, 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á

${ displaystyle (x-3) (x-2) ^ {6} (x-1) ^ {3} x ^ {4} (x + 1) ^ {3} (x + 2) ^ {6} ( x + 3), }$

dělat to integrální graf — Graf, jehož spektrum skládá se výhradně z celých čísel.

Topologické vlastnosti

Symetrické uložení grafu Nauru na povrchu rodu 4 se šesti dodecagonálními tvářemi.

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

Nauruový graf jako graf jednotkové vzdálenosti od Žitnik, Horvat & Pisanski (2010).

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 Dih₆ 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