Tutte – Coxeterův graf - Tutte–Coxeter graph
| Tutte – Coxeterův graf | |
|---|---|
 | |
| Pojmenoval podle | W. T. Tutte H. S. M. Coxeter |
| Vrcholy | 30 |
| Hrany | 45 |
| Poloměr | 4 |
| Průměr | 4 |
| Obvod | 8 |
| Automorfismy | 1440 (Aut (S6)) |
| Chromatické číslo | 2 |
| Chromatický index | 3 |
| Tloušťka knihy | 3 |
| Číslo fronty | 2 |
| Vlastnosti | Krychlový Klec Mooreův graf Symetrický Vzdálenost-pravidelná Přechodná vzdálenost Bipartitní |
| Tabulka grafů a parametrů | |
V matematický pole teorie grafů, Tutte – Coxeterův graf nebo Tutte osm klec nebo Cremona – Richmondův graf je 3-běžný graf s 30 vrcholy a 45 hranami. Jako jedinečný nejmenší kubický graf z obvod 8 je to klec a a Mooreův graf. to je bipartitní a lze jej zkonstruovat jako Leviho graf z zobecněný čtyřúhelník Ž2 (známý jako Konfigurace Cremona – Richmond ). Název grafu je William Thomas Tutte a H. S. M. Coxeter; objevil ji Tutte (1947), ale jeho souvislost s geometrickými konfiguracemi zkoumali oba autoři ve dvojici společně publikovaných prací (Tutte 1958; Coxeter 1958a).
Všechny krychlový vzdálenost-pravidelné grafy jsou známy.[1] Tutte-Coxeter je jedním ze 13 takových grafů.
Má to číslo křížení 13,[2][3] tloušťka knihy 3 a číslo fronty 2.[4]
Konstrukce a automorfismy
Obzvláště jednoduchá kombinatorická konstrukce grafu Tutte – Coxeter je způsobena Coxeterem (1958b), založeným na práci Sylvestera (1844). V moderní terminologii použijte a kompletní graf na 6 vrcholech K.6. Má 15 hran a také 15 perfektní shody. Každý vrchol grafu Tutte – Coxeter odpovídá hraně nebo dokonalému přizpůsobení K.6a každá hrana grafu Tutte – Coxeter spojuje dokonalé přizpůsobení K.6 ke každé ze svých tří komponentních hran. Symetricky, každý okraj K.6 patří ke třem dokonalým párům. Mimochodem, toto rozdělení vrcholů na vrcholové hrany a odpovídající vrcholy ukazuje, že graf Tutte-Coxeter je bipartitní.
Na základě této konstrukce Coxeter ukázal, že graf Tutte – Coxeter je a symetrický graf; má to skupina z roku 1440 automorfismy, které lze identifikovat s automorfizmy skupiny permutací na šesti prvcích (Coxeter 1958b). The vnitřní automorfismy této skupiny odpovídá permutaci šesti vrcholů K.6 graf; tyto permutace působí na graf Tutte-Coxeter permutací vrcholů na každé straně jeho bipartice, přičemž každou ze dvou stran udržují fixovanou jako množinu. Kromě toho vnější automorfismy skupiny permutací vymění jednu stranu bipartice za druhou. Jak ukázal Coxeter, jakákoli cesta až pěti hran v grafu Tutte-Coxeter je ekvivalentní jakékoli jiné takové cestě jedním takovým automorfismem.
Tutte-Coxeterův graf jako budova
Tento graf je sférická budova přidružené k symplektické skupině (mezi touto a symetrickou skupinou existuje výjimečný izomorfismus ). Přesněji se jedná o graf výskytu a zobecněný čtyřúhelník.
Konkrétně lze graf Tutte-Coxeter definovat ze 4-dimenzionálního symplektický vektorový prostor PROTI přes jak následuje:
- vrcholy jsou buď nenulové vektory, nebo izotropní 2-dimenzionální podprostory,
- mezi nenulovým vektorem je hrana proti a izotropní 2-dimenzionální podprostor kdyby a jen kdyby .
Galerie
The chromatické číslo grafu Tutte – Coxeter je 2.
The chromatický index grafu Tutte – Coxeter je 3.
Reference
- ^ Brouwer, A.E .; Cohen, A. M .; a Neumaier, A. Distance-Regular Graphs. New York: Springer-Verlag, 1989.
- ^ Pegg, E. T.; Exoo, G. (2009). Msgstr "Křížení číselných grafů". Mathematica Journal. 11 (2). doi:10,3888 / tmj.11.2-2.CS1 maint: ref = harv (odkaz)
- ^ Exoo, G. "Přímočaré kresby slavných grafů".
- ^ Wolz, Jessica; Inženýrské lineární rozložení se SAT. Diplomová práce, University of Tübingen, 2018
- Coxeter, H. S. M. (1958a). "Akordy nevládaného kvadrika v PG (3,3)". Umět. J. Math. 10: 484–488. doi:10.4153 / CJM-1958-047-0.
- Coxeter, H. S. M. (1958b). "Dvanáct bodů v PG (5,3) s 95040 autotransformacemi". Sborník královské společnosti A. 247 (1250): 279–293. doi:10.1098 / rspa.1958.0184. JSTOR 100667. S2CID 121676627.
- Sylvester, J. J. (1844). „Základní výzkumy v analýze kombinatorické agregace“. Phil. Mag. Řada 3. 24: 285–295. doi:10.1080/14786444408644856.
- Tutte, W. T. (1947). "Rodina kubických grafů". Proc. Cambridge Philos. Soc. 43 (4): 459–474. doi:10.1017 / S0305004100023720.
- Tutte, W. T. (1958). "Akordy nevládaného kvadrika v PG (3,3)". Umět. J. Math. 10: 481–483. doi:10.4153 / CJM-1958-046-3.
externí odkazy
- François Labelle. „3D model 8-klece Tutte“.
- Weisstein, Eric W. "Levi Graph". MathWorld.
- Exoo, G. "Přímočaré kresby slavných grafů." [1]