LCF-kod

En LCF-kod  är en notation i kombinatorisk matematik utvecklad av Lederberg och utökad av Coxeter och Frucht för att representera kubiska grafer som är Hamiltonska [2] [3] . Eftersom graferna är Hamiltonska, kan hörnen placeras på en cirkel som definierar två kanter för varje vertex. Den tredje kanten kan nu beskrivas med antalet positioner som kanten på kanten är från början (plus medurs och minus moturs). Ofta blir resultatet en repeterande sekvens av siffror, i vilket fall endast denna repeterande del skrivs ut, och antalet upprepningar visas med en upphöjd text (som en grad). Till exempel har Earl of Nauru [1] LCF-koden [5, −9, 7, −7, 9, −5] 4 . Samma graf kan ha olika LCF-koder beroende på hur hörnen är placerade på cirkeln (grafen kan ha flera varianter av Hamiltons cykel).

Siffror inom hakparenteser anses vara modulo , där  är antalet grafens hörn. Tal modulo 0, 1 och är inte tillåtna [4] eftersom de inte kan matcha någon tredje kant.

En LCF-kod är användbar för en kortfattad beskrivning av Hamiltonska kubikgrafer, särskilt de som listas i tabellen nedan. Dessutom innehåller vissa grafprogramvarupaket verktyg för att skapa en graf från dess LCF-kod [5] .

Exempel

namn Toppar LCF-kod
tetraedergraf _ fyra [2] 4
6 [3] 6
kubgraf åtta [3,-3] 4
Greve Wagner åtta [4] 8 eller [4,-3,3,4] 2
Kub av 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]
Earl av Franklin 12 [5,-5] 6 eller [-5,-3,3,5] 3
Greve Fruhta 12 [-5,-2,-4,2,5,-2,2,5,-2,-5,4,2]
Trunkerad tetraedergraf 12 [2,6,-2] 4
Earl av Heawood fjorton [5,-5] 7
Möbius Graph - Kantor 16 [5,-5] 8
Greve Pappa arton [5,7,-7,7,-7,-5] 3
Greve Desargues tjugo [5,-5,9,-9] 5
dodekaedergraf _ tjugo [10.7.4,-4,-7.10,-4.7,-7.4] 2
Greve McGee 24 [12,7,-7] 8
Trunkerad kubgraf 24 [2,9,-2,2,-9,-2] 4
Graf över en stympad oktaeder 24 [3,-7,7,-3] 6
Greve av Nauru 24 [5,-9,7,-7,9,-5] 4
Räkna F26A 26 [-7, 7] 13
Greve av Thatta-Coxeter trettio [-13,-9.7,-7.9.13] 5
Greve Dick 32 [5,-5,13,-13] 8
Earl of Grey 54 [-25.7,-7.13,-13.25] 9
Trunkerad dodekaedergraf 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
Earl av Harris 70 [-29,-19,-13,13,21,-27,27,33,-13,13,19,-21,-33,29] 5
Greve 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-cells 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]
Earl of Foster 90 [17,-9.37,-37.9,-17] 15
Earl of 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-cells 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 av 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-cells Tatta 126 [17, 27, -13, -59, -35, 35, -11, 13, -53, 53, -27, 21, 57, 11, -21, -57, 59, -17] 7

Generaliserad LCF-kod

En mer komplex version av LCF-koden föreslogs av Coxeter, Fruht och Powers i ett senare arbete [6] . I synnerhet föreslog de en "antipalidromisk" kod - om den andra hälften av siffrorna inom hakparenteser är den omvända sekvensen av den första delen med tecknen omvända, ersätts den andra delen av ett semikolon och ett bindestreck. Naurugrafen uppfyller detta villkor, så dess kod [5, −9, 7, −7, 9, −5] 4 kan generaliseras som [5, −9, 7; −] 4 [7] .

Anteckningar

  1. ↑ 1 2 D. Eppstein , Naurugrafens många ansikten Arkiverad från originalet den 21 juli 2011. på LiveJournals webbplats, 2007.
  2. ↑ Tomaž Pisanski, Brigitte Servatius. Konfigurationer från en grafisk synvinkel. - Springer, 2013. - ISBN 9780817683641 .
  3. ↑ R. Frucht. En kanonisk representation av trivalenta Hamiltonska grafer // Journal of Graph Theory. - 1976. - Vol. 1 , nummer. 1 . — S. 45–60 . - doi : 10.1002/jgt.3190010111 .
  4. ↑ Klavdija Kutnar, Dragan Marusic. Hamiltonicitet hos vertextransitiva grafer av ordning 4 p  // European Journal of Combinatorics. - T. 29 , nej. 2 (februari 2008) . - S. 423-438, avsnitt 2. .
  5. ↑ till exempel, Maple Arkiverad 2 mars 2012 på Wayback Machine , NetworkX Arkiverad 2 mars 2012 på Wayback Machine , R Arkiverad 21 augusti 2009 på Wayback Machine och Sage Arkiverad 27 mars 2017 på Wayback Machine .
  6. ↑ Coxeter, Frucht, Powers, 1981 , sid. 54
  7. ↑ Coxeter, Frucht, Powers, 1981 , sid. 12

Länkar