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 ( PGL 2 (7) ) |
| Chromatické číslo | 2 |
| Chromatický index | 3 |
| Rod | 1 |
| Tloušťka knihy | 3 |
| Číslo fronty | 2 |
| Vlastnosti |
Bipartitová kubická klec Vzdálenost-přechodná Vzdálenost-pravidelná toroidní hamiltoniánská symetrická Orientačně jednoduchá |
| Tabulka grafů a parametrů | |
V matematickém poli teorie grafů je heawoodův graf je neorientovaný graf s 14 vrcholy a 21 hran, pojmenované po Percy John Heawood .
Kombinatorické vlastnosti
Graf je kubický 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 obvodu 6. Je to graf přechodný na vzdálenost (viz sčítání Foster ), a proto je vzdálenost pravidelná .
V grafu Heawood je 24 dokonalých shody ; pro každou shodu tvoří sada hran, které nejsou v shody, 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 hrany ) osmi různými způsoby. Každé dvě dokonalé shody a každé dva Hamiltonovské cykly lze do sebe navzájem transformovat symetrií grafu.
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 .
Geometrické a topologické vlastnosti
Heawoodův graf je toroidní graf ; to znamená, že může být vložen bez křížení do torusu . Jedno vložení tohoto typu umisťuje jeho vrcholy a hrany do trojrozměrného euklidovského prostoru jako množinu vrcholů a hran nekonvexního mnohostěnu s topologií torusu, Szilassiho mnohostěnu .
Graf je pojmenován po Percymu Johnovi Heawoodovi , který v roce 1890 dokázal, že při každém dělení torusu na polygony lze polygonální oblasti obarvit nejvýše sedmi barvami. 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 graf Levi z Fano roviny , graf představující výskyt mezi bodů a čar v tomto geometrii. S touto interpretací odpovídá 6 cyklů v grafu Heawood trojúhelníkům v rovině Fano. Heawoodův graf je také stavbou Tits skupiny SL 3 (F 2 ) .
Heawoodův graf má křížení číslo 3 a je nejmenším kubickým grafem 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 invariantem grafu Colina de Verdièra μ = 6.
Heawoodův graf je jednotkový graf 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ě.
Algebraické vlastnosti
Skupina automorfismu Heawoodova grafu je izomorfní s projektivní lineární skupinou PGL 2 (7), skupinou řádu 336. Působí přechodně na vrcholy, na okraje a na oblouky grafu. Proto je Heawoodův graf symetrický graf . Má automatorfismy, které berou jakýkoli vrchol na jakýkoli jiný vrchol a jakoukoli hranu na jakoukoli jinou hranu. Silněji je graf Heawood 4-obloukový tranzitivní . Podle sčítání Foster , Heawoodův graf, označovaný jako F014A, je jediný kubický symetrický graf na 14 vrcholech.
Má tloušťku knihy 3 a frontu číslo 2.
Charakteristický polynom na heawoodův graf je . Je to jediný graf s tímto charakteristickým polynomem, což z něj dělá graf určený svým spektrem.
Galerie
Graf Heawood má křížení číslo 3.
Chromatický index v heawoodův graf je 3.
Barevnost v heawoodův graf je 2.
Vložení grafu Heawood do torusu (znázorněného jako čtverec s periodickými okrajovými podmínkami ), který jej rozděluje do sedmi vzájemně sousedících oblastí
Heawoodův graf a související mapa vložené do torusu.
Video Heawood Graph na Torusu
