LCF kód

Az LCF-kód a Lederberg által kifejlesztett és Coxeter és Frucht által kibővített  jelölés a kombinatorikus matematikában, hogy olyan köbös gráfokat ábrázoljon , amelyek hamiltoni [2] [3] . Mivel a gráfok Hamilton-féleek, a csúcsok a körön helyezkedhetnek el , amely minden csúcshoz két élt határoz meg. A harmadik él most már leírható a pozíciók számával, hogy az él vége az elejétől számítva (plusz az óramutató járásával megegyező és mínusz az óramutató járásával ellentétes). Az eredmény gyakran ismétlődő számsor, ilyenkor csak ezt az ismétlődő részt írjuk ki, és az ismétlések számát egy felső indexszel (például fokszámmal) jelzik. Például Nauru grófjának [1] az LCF kódja [5, −9, 7, −7, 9, −5] 4 . Ugyanazon gráfnak különböző LCF kódja lehet attól függően, hogy a csúcsok hogyan helyezkednek el a körön (a gráfnak a Hamilton-ciklus több változata is lehet).

A szögletes zárójelben lévő számokat modulo -nak tekintjük , ahol  a gráf csúcsainak száma. A modulo 0, 1 és a számok nem engedélyezettek [4] , mert nem egyezhetnek egyetlen harmadik éllel sem.

Az LCF kód hasznos a Hamilton-féle köbös gráfok tömör leírásához, különösen az alábbi táblázatban felsoroltakhoz. Ezenkívül egyes gráfszoftver-csomagok olyan segédprogramokat is tartalmaznak, amelyekkel LCF-kódjukból lehet gráfot létrehozni [5] .

Példák

Név Csúcsok LCF kód
tetraéder gráf négy [2] 4
6 [3] 6
kocka grafikon nyolc [3,-3] 4
Wagner gróf nyolc [4] 8 vagy [4,-3,3,4] 2
Bidiakis kocka 12 [6,4,-4] 4 vagy [6,-3,3,6,3,-3] 2 vagy [-3,6,4,-4,6,3,-4,6,-3, 3,6,4]
Franklin grófja 12 [5,-5] 6 vagy [-5,-3,3,5] 3
Fruhta gróf 12 [-5,-2,-4,2,5,-2,2,5,-2,-5,4,2]
Csonka tetraéder gráf 12 [2,6,-2] 4
Heawood grófja tizennégy [5,-5] 7
Möbius Graph - Kántor 16 [5,-5] 8
Pappa gróf tizennyolc [5,7,-7,7,-7,-5] 3
Desargues gróf húsz [5,-5,9,-9] 5
dodekaéder gráf húsz [10.7.4,-4,-7.10,-4.7,-7.4] 2
McGee gróf 24 [12,7,-7] 8
Csonka kockagrafikon 24 [2,9,-2,2,-9,-2] 4
Csonka oktaéder grafikonja 24 [3,-7,7,-3] 6
Nauru grófja 24 [5,-9,7,-7,9,-5] 4
Gróf F26A 26 [-7, 7] 13
Thatta-Coxeter grófja harminc [-13,-9,7,-7,9,13] 5
Dick gróf 32 [5,-5,13,-13] 8
Earl of Grey 54 [-25,7,-7,13,-13,25] 9
Csonka dodekaéder gráf 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
Harris grófja 70 [-29,-19,-13,13,21,-27,27,33,-13,13,19,-21,-33,29] 5
Harris-Wong gróf 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]
10 sejtes Balaban 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]
Foster grófja 90 [17,-9,37,-37,9,-17] 15
Biggs-Smith grófja 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]
11 sejtes Balaban 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]
Ljubljana grófja 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
12 cellás Tatta 126 [17, 27, -13, -59, -35, 35, -11, 13, -53, 53, -27, 21, 57, 11, -21, -57, 59, -17] 7

Általánosított LCF kód

Az LCF kód bonyolultabb változatát Coxeter, Fruht és Powers javasolta egy későbbi munkájában [6] . Különösen egy „anti-palidromikus” kódot javasoltak - ha a szögletes zárójelben lévő számok második fele az első rész fordított sorrendje a megfordított jelekkel, akkor a második részt pontosvesszővel és kötőjellel helyettesítik. A Nauru gráf teljesíti ezt a feltételt, ezért kódja [5, −9, 7, −7, 9, −5] 4 általánosítható [5, −9, 7; −] 4 [7] .

Jegyzetek

  1. ↑ 1 2 D. Eppstein , A Nauru-gráf sok arca Archiválva az eredetiből 2011. július 21-én. a LiveJournal honlapján, 2007.
  2. ↑ Tomaž Pisanski, Brigitte Servatius. Konfigurációk grafikus nézőpontból. - Springer, 2013. - ISBN 9780817683641 .
  3. ↑ R. Frucht. A háromértékű Hamilton-gráfok kanonikus ábrázolása // Journal of Graph Theory. - 1976. - 1. évf. , szám. 1 . — S. 45–60 . - doi : 10.1002/jgt.3190010111 .
  4. ↑ Klavdija Kutnar, Dragan Marusic. 4. rendű csúcstranzitív gráfok Hamiltonitása //  European Journal of Combinatorics. - T. 29 , sz. 2 (2008. február) . - S. 423-438, 2. szakasz .
  5. ↑ például: Maple archiválva 2012. március 2-án a Wayback Machine -nél , a NetworkX archiválva : 2012. március 2-án a Wayback Machine -nél , az R archiválva : 2009. augusztus 21-én a Wayback Machine -nél , és a sage archiválva : 2017. március 27-én a Wayback Machine -nél .
  6. ↑ Coxeter, Frucht, Powers, 1981 , p. 54
  7. ↑ Coxeter, Frucht, Powers, 1981 , p. 12

Linkek