Cod LCF

Un cod LCF  este o notație în matematică combinatorie dezvoltată de Lederberg și extinsă de Coxeter și Frucht pentru a reprezenta grafice cubice care sunt hamiltoniene [2] [3] . Deoarece graficele sunt hamiltoniene, vârfurile pot fi plasate pe un cerc care definește două muchii pentru fiecare vârf. A treia muchie poate fi descrisă acum prin numărul de poziții în care capătul muchiei este de la început (plus în sensul acelor de ceasornic și minus în sens invers acelor de ceasornic). Adesea, rezultatul este o succesiune de numere care se repetă, caz în care numai această parte care se repetă este scrisă, iar numărul de repetări este afișat cu un superscript (cum ar fi un grad). De exemplu, Contele de Nauru [1] are codul LCF [5, −9, 7, −7, 9, −5] 4 . Același grafic poate avea coduri LCF diferite în funcție de modul în care sunt situate vârfurile pe cerc (graficul poate avea mai multe variante ale ciclului hamiltonian).

Numerele dintre paranteze pătrate sunt considerate modulo , unde  este numărul de vârfuri ale graficului. Numerele modulo 0, 1 și nu sunt permise [4] deoarece nu se potrivesc cu nicio a treia muchie.

Un cod LCF este util pentru o descriere concisă a graficelor cubice hamiltoniene, în special a celor enumerate în tabelul de mai jos. În plus, unele pachete software pentru grafice includ utilitare pentru crearea unui grafic din codul său LCF [5] .

Exemple

Nume Vârfurile Cod LCF
grafic tetraedric patru [2] 4
6 [3] 6
grafic cub opt [3,-3] 4
Contele Wagner opt [4] 8 sau [4,-3,3,4] 2
Cubul de Bidiakis 12 [6,4,-4] 4 sau [6,-3,3,6,3,-3] 2 sau [-3,6,4,-4,6,3,-4,6,-3, 3,6,4]
Contele de Franklin 12 [5,-5] 6 sau [-5,-3,3,5] 3
contele Fruhta 12 [-5,-2,-4,2.5,-2,2.5,-2,-5,4,2]
Graficul tetraedric trunchiat 12 [2,6,-2] 4
Contele de Heawood paisprezece [5,-5] 7
Möbius Graph - Cantor 16 [5,-5] 8
Contele Pappa optsprezece [5,7,-7,7,-7,-5] 3
Contele Desargues douăzeci [5,-5,9,-9] 5
graficul dodecaedru douăzeci [10.7.4,-4,-7.10,-4.7,-7.4] 2
Contele McGee 24 [12,7,-7] 8
Grafic cub trunchiat 24 [2,9,-2,2,-9,-2] 4
Graficul unui octaedru trunchiat 24 [3,-7,7,-3] 6
Contele de Nauru 24 [5,-9,7,-7,9,-5] 4
Numărul F26A 26 [-7, 7] 13
Contele de Thatta-Coxeter treizeci [-13,-9.7,-7.9.13] 5
Contele Dick 32 [5,-5,13,-13] 8
Contele de Grey 54 [-25,7,-7,13,-13,25] 9
Graficul dodecaedru trunchiat 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
Contele de Harris 70 [-29,-19,-13,13,21,-27,27,33,-13,13,19,-21,-33,29] 5
Contele 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]
Balaban cu 10 celule 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]
Contele de Foster 90 [17,-9,37,-37,9,-17] 15
Contele de 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]
Balaban cu 11 celule 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]
Contele de 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
Tatta cu 12 celule 126 [17, 27, -13, -59, -35, 35, -11, 13, -53, 53, -27, 21, 57, 11, -21, -57, 59, -17] 7

Cod LCF generalizat

O versiune mai complexă a codului LCF a fost propusă de Coxeter, Fruht și Powers într-o lucrare ulterioară [6] . În special, ei au propus un cod „anti-palidromic” - dacă a doua jumătate a numerelor din paranteze pătrate este succesiunea inversă a primei părți cu semnele inversate, atunci a doua parte este înlocuită cu punct și virgulă și liniuță. Graficul Nauru satisface această condiție, deci codul său [5, −9, 7, −7, 9, −5] 4 poate fi generalizat ca [5, −9, 7; −] 4 [7] .

Note

  1. ↑ 1 2 D. Eppstein , The many faces of the Nauru graph Arhivat din original pe 21 iulie 2011. pe site-ul LiveJournal, 2007.
  2. ↑ Tomaž Pisanski, Brigitte Servatius. Configurații dintr-un punct de vedere grafic. - Springer, 2013. - ISBN 9780817683641 .
  3. ↑ R. Frucht. O reprezentare canonică a graficelor hamiltoniene trivalente // Journal of Graph Theory. - 1976. - Vol. 1 , număr. 1 . — S. 45–60 . - doi : 10.1002/jgt.3190010111 .
  4. ↑ Klavdija Kutnar, Dragan Marusic. Hamiltonicitatea graficelor vertex-tranzitive de ordinul 4 p  // European Journal of Combinatorics. - T. 29 , nr. 2 (februarie 2008) . - S. 423-438, sectiunea 2. .
  5. ↑ de exemplu, Maple Arhivat 2 martie 2012 la Wayback Machine , NetworkX Arhivat 2 martie 2012 la Wayback Machine , R Arhivat 21 august 2009 la Wayback Machine și sage Arhivat 27 martie 2017 la Wayback Machine .
  6. ↑ Coxeter, Frucht, Puterile, 1981 , p. 54
  7. ↑ Coxeter, Frucht, Puterile, 1981 , p. 12

Link -uri