LCF-koodi

LCF-koodi  on kombinatorisen matematiikan merkintä, jonka Lederberg on kehittänyt ja jonka Coxeter ja Frucht ovat laajentaneet edustamaan kuutiograafisia Hamiltonin [2] [3] . Koska graafit ovat Hamiltonin, pisteet voidaan sijoittaa ympyrään , joka määrittää kaksi reunaa kullekin kärjelle. Kolmas reuna voidaan nyt kuvata asemien lukumäärällä, joka reunan lopussa on alusta (plus myötäpäivään ja miinus vastapäivään). Usein tuloksena on toistuva numerosarja, jolloin vain tämä toistuva osa kirjoitetaan ulos ja toistojen määrä näytetään yläindeksillä (kuten asteella). Esimerkiksi Earl of Naurun [1] LCF-koodi on [5, −9, 7, −7, 9, −5] 4 . Samalla graafilla voi olla eri LCF-koodit riippuen siitä, miten kärjet sijaitsevat ympyrässä (graafissa voi olla useita Hamiltonin syklin muunnelmia).

Hakasulkeissa olevia lukuja pidetään moduloina , missä  on graafin kärkien lukumäärä. Numerot modulo 0, 1 ja eivät ole sallittuja [4] , koska ne eivät voi vastata mitään kolmatta reunaa.

LCF-koodi on hyödyllinen Hamiltonin kuutiograafien, erityisesti alla olevassa taulukossa lueteltujen, tiiviissä kuvauksessa. Lisäksi jotkin kuvaajaohjelmistopaketit sisältävät apuohjelmia graafin luomiseksi sen LCF-koodista [5] .

Esimerkkejä

Nimi Huiput LCF-koodi
tetraedrikuvaaja _ neljä [2] 4
6 [3] 6
kuutiokaavio kahdeksan [3,-3] 4
Kreivi Wagner kahdeksan [4] 8 tai [4,-3,3,4] 2
Bidiakiksen kuutio 12 [6,4,-4] 4 tai [6,-3,3,6,3,-3] 2 tai [-3,6,4,-4,6,3,-4,6,-3, 3,6,4]
Earl of Franklin 12 [5,-5] 6 tai [-5,-3,3,5] 3
Kreivi Fruhta 12 [-5,-2,-4,2,5,-2,2,5,-2,-5,4,2]
Katkaistu tetraedrikaavio 12 [2,6,-2] 4
Earl of Heawood neljätoista [5,-5] 7
Möbius Graph - Cantor 16 [5,-5] 8
Kreivi Pappa kahdeksantoista [5,7,-7,7,-7,-5] 3
Kreivi Desargues kaksikymmentä [5,-5,9,-9] 5
dodekaedrikaavio _ kaksikymmentä [10.7.4,-4,-7.10,-4.7,-7.4] 2
Kreivi McGee 24 [12,7,-7] 8
Katkaistu kuutiokaavio 24 [2,9,-2,2,-9,-2] 4
Kaavio katkaistusta oktaedrista 24 [3,-7,7,-3] 6
Naurun kreivi 24 [5,-9,7,-7,9,-5] 4
Laske F26A 26 [-7, 7] 13
Thatta-Coxeterin kreivi kolmekymmentä [-13,-9.7,-7.9.13] 5
Kreivi Dick 32 [5,-5,13,-13] 8
Earl of Grey 54 [-25,7,-7,13,-13,25] 9
Katkaistu dodekaedrikaavio 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 of Harris 70 [-29,-19,-13,13,21,-27,27,33,-13,13,19,-21,-33,29] 5
Kreivi 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-soluinen 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
Biggs-Smithin jaarli 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-soluinen 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]
Ljubljanan kreivi 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-soluinen Tatta 126 [17, 27, -13, -59, -35, 35, -11, 13, -53, 53, -27, 21, 57, 11, -21, -57, 59, -17] 7

Yleistetty LCF-koodi

Monimutkaisempaa versiota LCF-koodista ehdottivat Coxeter, Fruht ja Powers myöhemmässä työssään [6] . Erityisesti he ehdottivat "anti-palidromic" -koodia - jos hakasulkeissa olevien numeroiden toinen puolisko on ensimmäisen osan käänteinen järjestys, jossa merkit on käännetty, niin toinen osa korvataan puolipisteellä ja viivalla. Nauru-graafi täyttää tämän ehdon, joten sen koodi [5, −9, 7, −7, 9, −5] 4 voidaan yleistää muodossa [5, −9, 7; −] 4 [7] .

Muistiinpanot

  1. ↑ 1 2 D. Eppstein , Nauru-graafin monet kasvot Arkistoitu alkuperäisestä 21. heinäkuuta 2011. LiveJournalin verkkosivuilla, 2007.
  2. ↑ Tomaž Pisanski, Brigitte Servatius. Konfiguraatiot graafisesta näkökulmasta. - Springer, 2013. - ISBN 9780817683641 .
  3. ↑ R. Frucht. Trivalenttien Hamiltonin graafien kanoninen esitys // Journal of Graph Theory. - 1976. - Osa 1 , numero. 1 . - S. 45-60 . - doi : 10.1002/jgt.3190010111 .
  4. ↑ Klavdija Kutnar, Dragan Marusic. Hamiltonisuus of vertex-transitive graphs of 4 p  // European Journal of Combinatorics. - T. 29 , no. 2 (helmikuu 2008) . - S. 423-438, kohta 2. .
  5. ↑ esimerkiksi Maple Arkistoitu 2. maaliskuuta 2012 Wayback Machinessa , NetworkX Arkistoitu 2. maaliskuuta 2012 Wayback Machinessa , R Arkistoitu 21. elokuuta 2009 Wayback Machinessa ja sage Arkistoitu 27. maaliskuuta 2017 Wayback Machinessa .
  6. ↑ Coxeter, Frucht, Powers, 1981 , s. 54
  7. ↑ Coxeter, Frucht, Powers, 1981 , s. 12

Linkit