Heawoodův graf - Heawood graph
| Heawoodův graf | |
|---|---|
 | |
| Pojmenoval podle | Percy John Heawood |
| Vrcholy | 14 |
| Hrany | 21 |
| Poloměr | 3 |
| Průměr | 3 |
| Obvod | 6 |
| Automorfismy | 336 (PGL2(7) ) |
| Chromatické číslo | 2 |
| Chromatický index | 3 |
| Rod | 1 |
| Tloušťka knihy | 3 |
| Číslo fronty | 2 |
| Vlastnosti | Bipartitní Krychlový Klec Přechodná vzdálenost Vzdálenost-pravidelná Toroidní Hamiltonian Symetrický Orientačně jednoduché |
| Tabulka grafů a parametrů | |
V matematický pole teorie grafů, Heawoodův graf je neorientovaný graf se 14 vrcholy a 21 hranami, pojmenovanými podle Percy John Heawood.[1]
Kombinatorické vlastnosti
Graf je krychlový a všechny cykly v grafu mají šest nebo více hran. Každý menší kubický graf má kratší cykly, takže tento graf je 6-klec, nejmenší kubický graf obvod 6. Je to vzdálenost-tranzitivní graf (viz Podporovat sčítání lidu ) a proto vzdálenost pravidelná.[2]
Existuje 24 perfektní shody v grafu Heawood; pro každou shodu sada hran, které nejsou ve shodě, tvoří a Hamiltonovský cyklus. Například obrázek ukazuje vrcholy grafu umístěného na cyklu, přičemž vnitřní úhlopříčky cyklu tvoří shodu. Rozdělením okrajů cyklu na dvě shody můžeme rozdělit Heawoodův graf na tři perfektní shody (tj. 3-barevné jeho okraje ) osmi různými způsoby.[2] Každé dvě dokonalé shody a každé dva Hamiltonovské cykly lze do sebe navzájem transformovat symetrií grafu.[3]
V grafu Heawood je 28 cyklů šesti vrcholů. Každý 6-cyklus je nesouvislý s přesně třemi dalšími 6-cykly; mezi těmito třemi 6 cykly je každý symetrický rozdíl ostatních dvou. Graf s jedním uzlem na 6 cyklů a jednou hranou pro každou disjunktní dvojici 6 cyklů je Coxeterův graf.[4]
Geometrické a topologické vlastnosti
Heawoodův graf je a toroidní graf; to znamená, že může být vložen bez křížení do a torus. Jedno vložení tohoto typu umístí jeho vrcholy a hrany do trojrozměrného prostoru Euklidovský prostor jako množina vrcholů a hran nekonvexního mnohostěnu s topologií torusu, Szilassi mnohostěn.
Název grafu je Percy John Heawood, který v roce 1890 dokázal, že při každém dělení torusu na polygony mohou být polygonální oblasti vybarveny maximálně sedmi barvami.[5][6] Heawoodův graf tvoří dělení torusu se sedmi vzájemně sousedícími oblastmi, což ukazuje, že tato vazba je těsná.
Heawoodův graf je Leviho graf z Fano letadlo, graf představující výskyty mezi body a čarami v dané geometrii. S touto interpretací odpovídá 6 cyklů v Heawoodově grafu trojúhelníky v rovině Fano. Graf Heawood je také Prsa budování skupiny SL3(F2).
Graf Heawood má číslo křížení 3 a je nejmenší kubický graf s tímto křížením (sekvence A110507 v OEIS ). Včetně grafu Heawood je 8 odlišných grafů řádu 14 s křížením číslo 3.
Heawoodův graf je nejmenší kubický graf s Colin de Verdière graf invariantní μ = 6. [7]
Heawoodův graf je a graf jednotkové vzdálenosti: může být vložen do roviny tak, že sousední vrcholy jsou přesně ve vzdálenosti jeden od sebe, bez dvou vrcholů vložených do stejného bodu a bez vrcholu vloženého do bodu v hraně.[8]
Algebraické vlastnosti
The skupina automorfismu Heawoodova grafu je isomorfní s projektivní lineární skupina PGL2(7), skupina objednávky 336.[9] Působí přechodně na vrcholy, na hrany a na oblouky grafu. Proto je Heawoodův graf a symetrický graf. Má automatorfismy, které berou jakýkoli vrchol na jakýkoli jiný vrchol a jakoukoli hranu na jakoukoli jinou hranu. Silněji, graf Heawood je 4-oblouk-tranzitivní.[10]Podle Podporovat sčítání lidu, Heawoodův graf, označovaný jako F014A, je jediný kubický symetrický graf na 14 vrcholech.[11][12]
Má to tloušťka knihy 3 a číslo fronty 2.[13]
The charakteristický polynom Heawoodova grafu je . Je to jediný graf s tímto charakteristickým polynomem, což z něj dělá graf určený svým spektrem.
Galerie
The Szilassi mnohostěn.
Graf Heawood má číslo křížení 3.
The chromatický index Heawoodova grafu je 3.
The chromatické číslo Heawoodova grafu je 2.
Vložení grafu Heawood do torusu (zobrazeno jako čtverec s periodické okrajové podmínky ) rozdělení do sedmi vzájemně sousedících oblastí
Heawoodův graf a související mapa vložené do torusu.
Video Heawood Graph na Torusu
Reference
- ^ Weisstein, Eric W. "Heawood Graph". MathWorld.
- ^ A b Brouwer, Andries E. "Graf Heawood". Doplnění a opravy ke knize Distance-Regular Graphs (Brouwer, Cohen, Neumaier; Springer; 1989). Externí odkaz v
| práce =(Pomoc) - ^ Abreu, M .; Aldred, R. E. L .; Funk, M .; Jackson, Bill; Labbate, D .; Sheehan, J. (2004), "Grafy a digrafy se všemi 2 faktory izomorfní", Journal of Combinatorial Theory, Řada B, 92 (2): 395–404, doi:10.1016 / j.jctb.2004.09.004, PAN 2099150.
- ^ Dejter, Italo J. (2011), „From the Coxeter graph to the Klein graph“, Journal of Graph Theory, arXiv:1002.1960, doi:10,1002 / jgt.20597.
- ^ Brown, Ezra (2002). „Mnoho jmen (7,3,1)“ (PDF). Matematický časopis. 75 (2): 83–94. doi:10.2307/3219140. JSTOR 3219140. Archivovány od originál (PDF) dne 2012-02-05. Citováno 2006-10-27.
- ^ Heawood, P. J. (1890). "Věty o zbarvení mapy". Čtvrtletní J. Math. Oxford Ser. 24: 322–339.
- ^ Hein van der Holst (2006). „Grafy a překážky ve čtyřech rozměrech“ (PDF). Journal of Combinatorial Theory, Řada B. 96 (3): 388–404. doi:10.1016 / j.jctb.2005.09.004.
- ^ Gerbracht, Eberhard H.-A. (2009). "Vkládání vzdálenosti jedenácti jednotek grafu Heawood". arXiv:0912.5395. Bibcode:2009arXiv0912.5395G. Citovat deník vyžaduje
| deník =(Pomoc). - ^ Bondy, J. A.; Murty, USA (1976). Teorie grafů s aplikacemi. New York: Severní Holandsko. p.237. ISBN 0-444-19451-7. Archivovány od originál dne 13. 4. 2010. Citováno 2019-12-18.
- ^ Conder a Morton (1995). "Klasifikace trojmocných symetrických grafů malé objednávky". Australasian Journal of Combinatorics. 11: 146.
- ^ Royle, G. „Krychlové symetrické grafy (Foster Census).“ Archivováno 2008-07-20 na Wayback Machine
- ^ Conder, M. a Dobcsányi, P. „Trivalentní symetrické grafy až do 768 vrcholů.“ J. Combin. Matematika. Kombinovat. Comput. 40, 41-63, 2002.
- ^ Jessica Wolz, Inženýrské lineární rozložení se SAT. Diplomová práce, University of Tübingen, 2018