LCF notace - LCF notation
v kombinační matematika, LCF notace nebo LCF kód je nota vytvořená Joshua Lederberg a rozšířeno o H. S. M. Coxeter a Robert Frucht, pro zastoupení kubické grafy které obsahují a Hamiltonovský cyklus.[2][3] Samotný cyklus obsahuje dvě ze tří adjacencies pro každý vrchol a notace LCF určuje, jak daleko v cyklu je třetí soused každého souseda. Jeden graf může mít více různých reprezentací v LCF notaci.
Popis
V Hamiltonovském grafu mohou být vrcholy uspořádány v cyklu, což odpovídá dvěma hranám na vrchol. Třetí hranu z každého vrcholu lze potom popsat podle toho, o kolik pozic ve směru hodinových ručiček (kladných) nebo proti směru hodinových ručiček (záporných) vede. Základní formou notace LCF je pouze posloupnost těchto počtů pozic, počínaje libovolně zvoleným vrcholem a psaná v hranatých závorkách. Čísla v závorkách jsou interpretována modulo N, kde N je počet vrcholů. Vstupy shodné modulo N na 0, 1 nebo N - 1 se neobjevuje v tomto pořadí čísel,[4] protože by odpovídaly buď a smyčka nebo vícenásobné sousedství, z nichž ani jeden není povolen v jednoduchých grafech.
Vzor se často opakuje a počet opakování lze označit horním indexem v notaci. Například Nauru graf,[1] zobrazeno vpravo, má čtyři opakování se stejnými šesti posuny a může být reprezentováno notací LCF [5, −9, 7, −7, 9, −5]4. Jeden graf může mít několik různých LCF notací, v závislosti na volbách Hamiltonovského cyklu a počátečního vrcholu.
Aplikace
LCF notace je užitečná při publikování stručných popisů Hamiltonovských kubických grafů, jako jsou příklady níže. Některé softwarové balíčky pro manipulaci s grafy navíc obsahují nástroje pro vytvoření grafu z jeho LCF notace.[5]
Pokud je graf reprezentován notací LCF, je snadné otestovat, zda je graf bipartitní: to platí tehdy a jen tehdy, když jsou všechna vyrovnání v notaci LCF lichá.[6]
Příklady
| název | Vrcholy | LCF notace |
|---|---|---|
| Čtyřboká graf | 4 | [2]4 |
| Graf užitku | 6 | [3]6 |
| Krychlový graf | 8 | [3,−3]4 |
| Wagnerův graf | 8 | [4]8 nebo [4, -3,3,4]2 |
| Bidiakisova kostka | 12 | [6,4,−4]4 nebo [6, -3,3,6,3, -3]2 nebo [−3,6,4, −4,6,3, −4,6, −3,3,6,4] |
| Franklinův graf | 12 | [5,−5]6 nebo [−5, −3,3,5]3 |
| Frucht graf | 12 | [−5,−2,−4,2,5,−2,2,5,−2,−5,4,2] |
| Zkráceno čtyřboká graf | 12 | [2,6,−2]4 |
| Heawoodův graf | 14 | [5,−5]7 |
| Möbius – Kantorův graf | 16 | [5,−5]8 |
| Pappusův graf | 18 | [5,7,−7,7,−7,−5]3 |
| Nejmenší nulový symetrický graf[7] | 18 | [5,−5]9 |
| Desargues graf | 20 | [5,−5,9,−9]5 |
| Dodecahedral graf | 20 | [10,7,4,−4,−7,10,−4,7,−7,4]2 |
| McGeeův graf | 24 | [12,7,−7]8 |
| Zkráceno krychlový graf | 24 | [2,9,−2,2,−9,−2]4 |
| Zkráceno osmistěn graf | 24 | [3,−7,7,−3]6 |
| Nauru graf | 24 | [5,−9,7,−7,9,−5]4 |
| Graf F26A | 26 | [−7, 7]13 |
| Tutte – Coxeterův graf | 30 | [−13,−9,7,−7,9,13]5 |
| Dyckův graf | 32 | [5,−5,13,−13]8 |
| Šedý graf | 54 | [−25,7,−7,13,−13,25]9 |
| Zkráceno dodekahedrál graf | 60 | [30, −2, 2, 21, −2, 2, 12, −2, 2, −12, −2, 2, −21, −2, 2, 30, −2, 2, −12, −2, 2, 21, −2, 2, −21, −2, 2, 12, −2, 2]2 |
| Harriesův graf | 70 | [−29,−19,−13,13,21,−27,27,33,−13,13,19,−21,−33,29]5 |
| Harries – Wongův graf | 70 | [9, 25, 31, −17, 17, 33, 9, −29, −15, −9, 9, 25, −25, 29, 17, −9, 9, −27, 35, −9, 9, −17, 21, 27, −29, −9, −25, 13, 19, −9, −33, −17, 19, −31, 27, 11, −25, 29, −33, 13, −13, 21, −29, −21, 25, 9, −11, −19, 29, 9, −27, −19, −13, −35, −9, 9, 17, 25, −9, 9, 27, −27, −21, 15, −9, 29, −29, 33, −9, −25] |
| Balaban 10-klec | 70 | [−9, −25, −19, 29, 13, 35, −13, −29, 19, 25, 9, −29, 29, 17, 33, 21, 9,−13, −31, −9, 25, 17, 9, −31, 27, −9, 17, −19, −29, 27, −17, −9, −29, 33, −25,25, −21, 17, −17, 29, 35, −29, 17, −17, 21, −25, 25, −33, 29, 9, 17, −27, 29, 19, −17, 9, −27, 31, −9, −17, −25, 9, 31, 13, −9, −21, −33, −17, −29, 29] |
| Pěstounský graf | 90 | [17,−9,37,−37,9,−17]15 |
| Biggs – Smithův graf | 102 | [16, 24, −38, 17, 34, 48, −19, 41, −35, 47, −20, 34, −36, 21, 14, 48, −16, −36, −43, 28, −17, 21, 29, −43, 46, −24, 28, −38, −14, −50, −45, 21, 8, 27, −21, 20, −37, 39, −34, −44, −8, 38, −21, 25, 15, −34, 18, −28, −41, 36, 8, −29, −21, −48, −28, −20, −47, 14, −8, −15, −27, 38, 24, −48, −18, 25, 38, 31, −25, 24, −46, −14, 28, 11, 21, 35, −39, 43, 36, −38, 14, 50, 43, 36, −11, −36, −24, 45, 8, 19, −25, 38, 20, −24, −14, −21, −8, 44, −31, −38, −28, 37] |
| Klec Balaban 11 | 112 | [44, 26, −47, −15, 35, −39, 11, −27, 38, −37, 43, 14, 28, 51, −29, −16, 41, −11, −26, 15, 22, −51, −35, 36, 52, −14, −33, −26, −46, 52, 26, 16, 43, 33, −15, 17, −53, 23, −42, −35, −28, 30, −22, 45, −44, 16, −38, −16, 50, −55, 20, 28, −17, −43, 47, 34, −26, −41, 11, −36, −23, −16, 41, 17, −51, 26, −33, 47, 17, −11, −20, −30, 21, 29, 36, −43, −52, 10, 39, −28, −17, −52, 51, 26, 37, −17, 10, −10, −45, −34, 17, −26, 27, −21, 46, 53, −10, 29, −50, 35, 15, −47, −29, −41, 26, 33, 55, −17, 42, −26, −36, 16] |
| Lublaňský graf | 112 | [47, −23, −31, 39, 25, −21, −31, −41, 25, 15, 29, −41, −19, 15, −49, 33, 39, −35, −21, 17, −33, 49, 41, 31, −15, −29, 41, 31, −15, −25, 21, 31, −51, −25, 23, 9, −17, 51, 35, −29, 21, −51, −39, 33, −9, −51, 51, −47, −33, 19, 51, −21, 29, 21, −31, −39]2 |
| Tutte 12-klec | 126 | [17, 27, −13, −59, −35, 35, −11, 13, −53, 53, −27, 21, 57, 11, −21, −57, 59, −17]7 |
Rozšířená notace LCF
Složitější rozšířenou verzi notace LCF poskytli Coxeter, Frucht a Powers v pozdější práci.[8] Zejména zavedli „antipalindromickou“ notaci: pokud druhá polovina čísel mezi hranatými závorkami byla zadní stranou první poloviny, ale se změnami všech znaků, byla nahrazena středníkem a pomlčkou. Nauruův graf splňuje tuto podmínku s [5, −9, 7, −7, 9, −5]4, a tak lze psát [5, −9, 7; -]4 v rozšířené notaci.[9]
Reference
- ^ A b Eppstein, D., Mnoho tváří grafu Nauru, 2007.
- ^ Pisanski, Tomaž; Servatius, Brigitte (2013), „2.3.2 Kubické grafy a LCF notace“, Konfigurace z grafického hlediska, Springer, str. 32, ISBN 9780817683641.
- ^ Frucht, R. (1976), „Kánonické znázornění trojmocných Hamiltonovských grafů“, Journal of Graph Theory, 1 (1): 45–60, doi:10.1002 / jgt.3190010111, PAN 0463029.
- ^ Kutnar, Klavdija; Marušič, Dragan (2008), „Hamiltonicita vrcholných grafů řádu 4str", European Journal of Combinatorics, 29 (2): 423–438, arXiv:matematika / 0606585, doi:10.1016 / j.ejc.2007.02.002, PAN 2388379. Viz část 2.
- ^ např. Javor, NetworkX Archivováno 02.03.2012 na Wayback Machine, igraf, a šalvěj.
- ^ Coxeter, Harold Scott MacDonald; Frucht, Roberto; Powers, David L. (1981), Nulové symetrické grafy, Academic Press, Inc. [Harcourt Brace Jovanovich, vydavatelé], New York-London, s. 13, ISBN 0-12-194580-4, PAN 0658666.
- ^ Coxeter, Frucht & Powers (1981), Obr. 1.1, s. 5.
- ^ Coxeter, Frucht & Powers (1981), str. 54.
- ^ Coxeter, Frucht & Powers (1981), str. 12.
externí odkazy
- Weisstein, Eric W. „LCF Notation“. MathWorld.
- Ed Pegg Jr. (29. prosince 2003), Matematické hry: Krychlové symetrické grafy, Mathematical Association of America
- „Hamiltonovské kubické grafy z LCF notace“ - Interaktivní aplikace JavaScript, postavená s D3js knihovna