Hranolový graf - Prism graph

V matematický pole teorie grafů, a hranolový graf je graf který má jeden z hranoly jako jeho kostra.

Příklady

Jednotlivé grafy lze pojmenovat podle přidruženého tělesa:

Trojhranný hranol graf - 6 vrcholů, 9 hran
Krychlový graf - 8 vrcholů, 12 hran
Pětiúhelníkový hranol graf - 10 vrcholů, 15 hran
Šestihranný hranol graf - 12 vrcholů, 18 hran
Heptagonální hranol graf - 14 vrcholů, 21 okrajů
Osmiboký hranol graf - 16 vrcholů, 24 hran
...

Y₃ = GP (3,1)	Y₄ = Q₃ = GP (4,1)	Y₅ = GP (5,1)	Y₆ = GP (6,1)	Y₇ = GP (7,1)	Y₈ = GP (8,1)

Ačkoli geometricky hvězdné polygony také tvoří tváře jiné posloupnosti (samoprotínajících se a nekonvexních) hranolových mnohostěnů, grafy těchto hvězdných hranolů jsou izomorfní s hranolovými grafy a netvoří samostatnou sekvenci grafů.

Konstrukce

Hranolové grafy jsou příklady zobecněné Petersenovy grafy, s parametry GP (n, 1). Mohou být také konstruovány jako kartézský součin a graf cyklu s jediným okrajem.^[1]

Stejně jako u mnoha vertex-tranzitivních grafů mohou být hranolové grafy také konstruovány jako Cayleyovy grafy. Objednávka-n dihedrální skupina je skupina symetrií pravidelného n-gon v rovině; působí na n-gon rotací a odrazy. Může být generován dvěma prvky, rotací o úhel 2 $π$ /n a jediný odraz a jeho Cayleyův graf s touto generující sadou je hranolový graf. Skupina abstraktně má prezentace ${ displaystyle langle r, f mid r ^ {n}, f ^ {2}, (rf) ^ {2} rangle}$ (kde r je rotace a F je odraz nebo převrácení) a Cayleyův graf má r a F (nebo r, r⁻¹, a F) jako jeho generátory.^[1]

The n-gonal hranolové grafy s lichými hodnotami n mohou být konstruovány jako oběhové grafy ${ displaystyle C_ {2n} ^ {2, n}}$ .Tato konstrukce však nefunguje pro sudé hodnotyn.^[1]

Vlastnosti

Graf an n-gonal hranol má 2n vrcholy a 3n hrany. Oni jsou pravidelný, kubické grafy Vzhledem k tomu, že hranol má symetrii, která bere každý vrchol k druhému vrcholu, jsou hranolové grafy vertex-tranzitivní grafy.Tak jako polyedrické grafy, jsou taky 3-vrchol připojený rovinné grafy. Každý hranolový graf má a Hamiltonovský cyklus.^[2]

Mezi všemi propojené kubické grafy, hranolové grafy mají v rámci konstantního faktoru největší možný počet 1-faktorizace. 1-faktorizace je rozdělení hranové sady grafu do tří dokonalých shod, nebo ekvivalentně zbarvení hran grafu se třemi barvami. Každý propojený n-vertex kubický graf má Ó(2^n/2) 1-faktorizace a hranolové grafy mají Ω(2^n/2) 1-faktorizace.^[3]

Počet klenout se nad stromy z n-gonal hranolový graf je dán vzorcem^[4]

{ displaystyle { frac {n} {2}} { bigl (} (2 + { sqrt {3}}) ^ {n} + (2 - { sqrt {3}}) ^ {n} - 2) { bigr.}}

Pro n = 3, 4, 5, ... tato čísla jsou

75, 384, 1805, 8100, 35287, 150528, ... (sekvence A006235 v OEIS ).

The n-gonal hranolové grafy pro sudé hodnoty n jsou dílčí kostky. Tvoří jednu z mála známých nekonečných rodin krychlový dílčí kostky a (kromě čtyř sporadických příkladů) jediné vrcholné kubické dílčí kostky.^[5]

Pětiúhelníkový hranol je jedním z zakázané nezletilé pro grafy šířka stromu tři.^[6] Trojúhelníkový hranolový a krychlový graf mají šířku stromu přesně tři, ale všechny větší hranolové grafy mají šířku stromu čtyři.

Související grafy

Mezi další nekonečné sekvence mnohostěnného grafu vytvořeného podobným způsobem z mnohostěnů s bázemi pravidelných mnohoúhelníků patří antiprism grafy (grafy antiprismy ) a grafy kol (grafy pyramidy ). Jiné vrcholné polyedrické grafy zahrnují Archimédovy grafy.

Pokud jsou dva cykly hranolového grafu přerušeny odstraněním jedné hrany ve stejné poloze v obou cyklech, výsledkem je žebříkový graf. Pokud jsou tyto dvě odstraněné hrany nahrazeny dvěma zkříženými hranami, výsledkem je nerovinný graf s názvem a Möbiový žebřík.^[7]

Reference

^ ^A ^b ^C Weisstein, Eric W. "Hranolový graf". MathWorld.
^ Přečtěte si, R. C. a Wilson, R. J. Atlas grafů, Oxford, Anglie: Oxford University Press, dotisk z roku 2004, kapitola 6 speciální grafy 261, 270.
^ Eppstein, David (2013), „Složitost neohýbaného trojrozměrného kreslení ortogonálního grafu“, Journal of Graph Algorithms and Applications, 17 (1): 35–55, arXiv:0709.4087, doi:10,7155 / jgaa.00283, PAN 3019198. Eppstein připisuje pozorování, že hranolové grafy mají téměř maximální počet 1-faktorizací, osobní komunikaci Greg Kuperberg.
^ Jagers, A. A. (1988), „Poznámka o počtu stromů v grafu hranolu“, International Journal of Computer Mathematics, 24 (2): 151–154, doi:10.1080/00207168808803639.
^ Marc, Tilen (2015), Klasifikace vrcholných přechodových kubických dílčích kostek, arXiv:1509.04565, Bibcode:2015arXiv150904565M.
^ Arnborg, Stefan; Proskurowski, Andrzej; Corneil, Derek G. (1990), „Zakázané nezletilé charakterizace dílčích 3-stromů“, Diskrétní matematika, 80 (1): 1–19, doi:10.1016 / 0012-365X (90) 90292-P, PAN 1045920.
^ Guy, Richard K.; Harary, Franku (1967), „Na žebřících Möbius“, Kanadský matematický bulletin, 10: 493–496, doi:10.4153 / CMB-1967-046-4, PAN 0224499.

[mathworld-1] A ^b ^C Weisstein, Eric W. "Hranolový graf". MathWorld.

[2] Přečtěte si, R. C. a Wilson, R. J. Atlas grafů, Oxford, Anglie: Oxford University Press, dotisk z roku 2004, kapitola 6 speciální grafy 261, 270.

[3] Eppstein, David (2013), „Složitost neohýbaného trojrozměrného kreslení ortogonálního grafu“, Journal of Graph Algorithms and Applications, 17 (1): 35–55, arXiv:0709.4087, doi:10,7155 / jgaa.00283, PAN 3019198. Eppstein připisuje pozorování, že hranolové grafy mají téměř maximální počet 1-faktorizací, osobní komunikaci Greg Kuperberg.

[4] Jagers, A. A. (1988), „Poznámka o počtu stromů v grafu hranolu“, International Journal of Computer Mathematics, 24 (2): 151–154, doi:10.1080/00207168808803639.

[5] Marc, Tilen (2015), Klasifikace vrcholných přechodových kubických dílčích kostek, arXiv:1509.04565, Bibcode:2015arXiv150904565M.

[6] Arnborg, Stefan; Proskurowski, Andrzej; Corneil, Derek G. (1990), „Zakázané nezletilé charakterizace dílčích 3-stromů“, Diskrétní matematika, 80 (1): 1–19, doi:10.1016 / 0012-365X (90) 90292-P, PAN 1045920.

[7] Guy, Richard K.; Harary, Franku (1967), „Na žebřících Möbius“, Kanadský matematický bulletin, 10: 493–496, doi:10.4153 / CMB-1967-046-4, PAN 0224499.

[1]

[2]

[3]

[4]

[5]

[6]

[7]