LCF kode

En LCF-kode  er en notation i kombinatorisk matematik udviklet af Lederberg og udvidet af Coxeter og Frucht til at repræsentere kubiske grafer , der er Hamiltonske [2] [3] . Da graferne er Hamiltonske, kan hjørnerne placeres på en cirkel , der definerer to kanter for hvert hjørne. Den tredje kant kan nu beskrives ved antallet af positioner, som enden af ​​kanten er fra begyndelsen (plus med uret og minus mod uret). Ofte er resultatet en gentagelse af tal, i hvilket tilfælde kun denne gentagne del skrives ud, og antallet af gentagelser vises med en hævet skrift (som en grad). For eksempel har jarlen af ​​Nauru [1] LCF-koden [5, −9, 7, −7, 9, −5] 4 . Den samme graf kan have forskellige LCF-koder afhængigt af hvordan toppunkterne er placeret på cirklen (grafen kan have flere varianter af Hamiltons cyklus).

Tal inden for firkantede parenteser betragtes som modulo , hvor  er antallet af grafens toppunkter. Tal modulo 0, 1 og er ikke tilladt [4] , fordi de ikke kan matche nogen tredje kant.

En LCF-kode er nyttig til en kortfattet beskrivelse af Hamiltonske kubiske grafer, især dem, der er anført i tabellen nedenfor. Derudover indeholder nogle grafsoftwarepakker hjælpeprogrammer til at skabe en graf ud fra dens LCF-kode [5] .

Eksempler

Navn Toppe LCF kode
tetraeder graf fire [2] 4
6 [3] 6
terninggraf otte [3,-3] 4
grev Wagner otte [4] 8 eller [4,-3,3,4] 2
Terning af Bidiakis 12 [6,4,-4] 4 eller [6,-3,3,6,3,-3] 2 eller [-3,6,4,-4,6,3,-4,6,-3, 3,6,4]
Jarl af Franklin 12 [5,-5] 6 eller [-5,-3,3,5] 3
Grev Fruhta 12 [-5,-2,-4,2,5,-2,2,5,-2,-5,4,2]
Afkortet tetraeder graf 12 [2,6,-2] 4
jarl af Heawood fjorten [5,-5] 7
Möbius Graph - Kantor 16 [5,-5] 8
Greve Pappa atten [5,7,-7,7,-7,-5] 3
Grev Desargues tyve [5,-5,9,-9] 5
dodekaeder graf tyve [10.7.4,-4,-7.10,-4.7,-7.4] 2
Grev McGee 24 [12,7,-7] 8
Trunkeret terninggraf 24 [2,9,-2,2,-9,-2] 4
Graf af et afkortet oktaeder 24 [3,-7,7,-3] 6
Greve af Nauru 24 [5,-9,7,-7,9,-5] 4
Tæl F26A 26 [-7, 7] 13
Greve af Thatta-Coxeter tredive [-13,-9.7,-7.9.13] 5
Grev Dick 32 [5,-5,13,-13] 8
Earl of Grey 54 [-25.7,-7.13,-13.25] 9
Afkortet dodekaeder 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
Jarl af Harris 70 [-29,-19,-13,13,21,-27,27,33,-13,13,19,-21,-33,29] 5
Grev Harris-Wong 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-cellers 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]
Jarl af Foster 90 [17,-9,37,-37,9,-17] 15
Jarl af Biggs-Smith 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-cellers 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]
Greve af Ljubljana 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-cellet Tatta 126 [17, 27, -13, -59, -35, 35, -11, 13, -53, 53, -27, 21, 57, 11, -21, -57, 59, -17] 7

Generaliseret LCF-kode

En mere kompleks version af LCF-koden blev foreslået af Coxeter, Fruht og Powers i et senere værk [6] . De foreslog især en "anti-palidromisk" kode - hvis den anden halvdel af tallene inden for firkantede parenteser er den omvendte rækkefølge af den første del med tegnene omvendt, så erstattes den anden del af et semikolon og en bindestreg. Nauru-grafen opfylder denne betingelse, så dens kode [5, −9, 7, −7, 9, −5] 4 kan generaliseres som [5, −9, 7; −] 4 [7] .

Noter

  1. ↑ 1 2 D. Eppstein , Nauru-grafens mange ansigter Arkiveret fra originalen den 21. juli 2011. på LiveJournals hjemmeside, 2007.
  2. ↑ Tomaž Pisanski, Brigitte Servatius. Konfigurationer fra et grafisk synspunkt. - Springer, 2013. - ISBN 9780817683641 .
  3. ↑ R. Frucht. En kanonisk repræsentation af trivalente Hamiltonske grafer // Journal of Graph Theory. - 1976. - Bind 1 , udgave. 1 . — S. 45–60 . - doi : 10.1002/jgt.3190010111 .
  4. ↑ Klavdija Kutnar, Dragan Marusic. Hamiltonicitet af vertex-transitive grafer af størrelsesorden 4 p  // European Journal of Combinatorics. - T. 29 , nej. 2 (februar 2008) . - S. 423-438, afsnit 2. .
  5. ↑ for eksempel, Maple Arkiveret 2. marts 2012 på Wayback Machine , NetworkX Arkiveret 2. marts 2012 på Wayback Machine , R Arkiveret 21. august 2009 på Wayback Machine og salvie Arkiveret 27. marts 2017 på Wayback Machine .
  6. ↑ Coxeter, Frucht, Powers, 1981 , s. 54
  7. ↑ Coxeter, Frucht, Powers, 1981 , s. 12

Links