LCF kód

LCF kód  je zápis v kombinatorické matematice vyvinutý Lederbergem a rozšířený Coxeterem a Fruchtem , aby reprezentoval kubické grafy , které jsou hamiltonovské [2] [3] . Protože jsou grafy hamiltonovské, mohou být vrcholy umístěny na kružnici , která definuje dvě hrany pro každý vrchol. Třetí hranu lze nyní popsat počtem pozic, na kterých je konec hrany od začátku (plus ve směru hodinových ručiček a mínus proti směru hodinových ručiček). Výsledkem je často opakující se posloupnost čísel, v takovém případě se vypíše pouze tato opakující se část a počet opakování se zobrazí s horním indexem (jako stupeň). Například hrabě z Nauru [1] má kód LCF [5, −9, 7, −7, 9, −5] 4 . Stejný graf může mít různé LCF kódy podle toho, jak jsou vrcholy umístěny na kružnici (graf může mít několik variant Hamiltonovského cyklu).

Čísla v hranatých závorkách jsou považována za modulo , kde  je počet vrcholů grafu. Čísla modulo 0, 1 a nejsou povolena [4] , protože nemohou odpovídat žádné třetí hraně.

LCF kód je užitečný pro stručný popis hamiltonovských kubických grafů, zejména těch, které jsou uvedeny v tabulce níže. Některé softwarové balíčky pro grafy navíc obsahují nástroje pro vytváření grafu z jeho LCF kódu [5] .

Příklady

název Vrcholy LCF kód
čtyřstěnný graf čtyři [2] 4
6 [3] 6
krychlový graf osm [3,-3] 4
hrabě Wagner osm [4] 8 nebo [4,-3,3,4] 2
Kostka Bidiakis 12 [6,4,-4] 4 nebo [6,-3,3,6,3,-3] 2 nebo [-3,6,4,-4,6,3,-4,6,-3, 3,6,4]
hrabě z Franklin 12 [5,-5] 6 nebo [-5,-3,3,5] 3
hrabě Fruhta 12 [-5,-2,-4,2.5,-2,2.5,-2,-5,4,2]
Graf zkráceného čtyřstěnu 12 [2,6,-2] 4
hrabě z Heawood čtrnáct [5,-5] 7
Möbiův graf - Cantor 16 [5,-5] 8
hrabě Pappa osmnáct [5,7,-7,7,-7,-5] 3
hrabě Desargues dvacet [5,-5,9,-9] 5
dvanáctistěnný graf dvacet [10.7.4,-4,-7.10,-4.7,-7.4] 2
Hrabě McGee 24 [12,7,-7] 8
Graf zkrácené krychle 24 [2,9,-2,2,-9,-2] 4
Graf zkráceného osmistěnu 24 [3,-7,7,-3] 6
hrabě z Nauru 24 [5,-9,7,-7,9,-5] 4
Hrabě F26A 26 [-7, 7] 13
Hrabě z Thatta-Coxeter třicet [-13,-9,7,-7,9,13] 5
Hrabě Dick 32 [5,-5,13,-13] 8
hrabě z Gray 54 [-25,7,-7,13,-13,25] 9
Graf zkráceného dvanáctistěnu 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
hrabě z Harris 70 [-29,-19,-13,13,21,-27,27,33,-13,13,19,-21,-33,29] 5
hrabě 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článkový 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]
hrabě z Foster 90 [17,-9,37,-37,9,-17] 15
hrabě z 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článkový 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]
hrabě z Lublaně 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článková Tatta 126 [17, 27, -13, -59, -35, 35, -11, 13, -53, 53, -27, 21, 57, 11, -21, -57, 59, -17] 7

Zobecněný kód LCF

Složitější verzi LCF kódu navrhli Coxeter, Fruht a Powers v pozdější práci [6] . Konkrétně navrhli „antipalidromický“ kód – pokud je druhá polovina čísel uvnitř hranatých závorek obráceným sledem první části s obrácenými znaky, pak je druhá část nahrazena středníkem a pomlčkou. Nauruův graf tuto podmínku splňuje, takže jeho kód [5, −9, 7, −7, 9, −5] 4 lze zobecnit jako [5, −9, 7; −] 4 [7] .

Poznámky

  1. ↑ 1 2 D. Eppstein , Mnoho tváří grafu Nauru Archivováno z originálu 21. července 2011. na webu LiveJournal, 2007.
  2. ↑ Tomaž Pisanski, Brigitte Servatius. Konfigurace z grafického hlediska. - Springer, 2013. - ISBN 9780817683641 .
  3. ↑ R. Frucht. Kanonická reprezentace trivalentních hamiltonovských grafů // Journal of Graph Theory. - 1976. - svazek 1 , vydání. 1 . — S. 45–60 . - doi : 10.1002/jgt.3190010111 .
  4. ↑ Klavdija Kutnar, Dragan Marušić. Hamiltonicita vertex-tranzitivních grafů řádu 4 p  // European Journal of Combinatorics. - T. 29 , č.p. 2 (únor 2008) . - S. 423-438, oddíl 2. .
  5. ↑ například Maple Archived 2 March 2012 at Wayback Machine , NetworkX Archived 2 March 2012 at Wayback Machine , R Archived 21 August 2009 at Wayback Machine a sage Archived 27 March 2017 at Wayback Machine .
  6. ↑ Coxeter, Frucht, Powers, 1981 , str. 54
  7. ↑ Coxeter, Frucht, Powers, 1981 , str. 12

Odkazy