Notazione LCF

notazione ideata da Joshua Lederberg ed estesa da Coxeter e Frucht

In matematica combinatoria, la notazione LCF o codice LCF è una notazione ideata da Joshua Lederberg ed estesa da Coxeter e Frucht, per la rappresentazione dei grafi cubici che sono hamiltoniani.[2][3] Poiché i grafi sono hamiltoniani, i vertici possono essere disposti in cerchio, che corrisponde a due spigoli per vertice. Il terzo spigolo di ciascun vertice può essere descritto allora dal numero di posizioni che esso conduce in senso orario (positivo) o antiorario (negativo). Spesso il modello si ripete, il che è da un apice nella notazione. Per esempio, il grafo di Nauru,[1] mostrato a destra, ha la notazione LCF [5, −9, 7, −7, 9, −5]4. I grafi possono avere diverse notazioni LCF, a seconda di come precisamente sono disposti i vertici.

Il grafo di Nauru[1] ha la notazione LCF [5, −9, 7, −7, 9, −5]4.

I numeri tra parentesi quadre sono interpretate come modulo N, dove N è il numero dei vertici. Gli inserimenti uguali (modulo N) a 0, 1, e N−1 non sono permessi.[4] poiché non corrispondono a terzi spigoli validi.

La notazione LCF è utile per pubblicare descrizioni concise dei grafi cubici hamiltoniani, come gli esempi sottostanti. Inoltre, alcuni pacchetti di programmi per manipolare grafi includono utilità per creare un grafo partendo dalla sua notazione LCF.[5]

Nome Vertici Notazione LCF
Grafo tetraedrico 4 [2]4
Grafo dei servizi pubblici 6 [3]6
Grafo cubico 8 [3,-3]4
Grafo di Wagner 8 [4]8 or [4,-3,3,4]2
Cubo di Bidiakis 12 [6,4,-4]4 or [6,-3,3,6,3,-3]2 or [-3,6,4,-4,6,3,-4,6,-3,3,6,4]
Grafo di Franklin 12 [5,-5]6 or [-5,-3,3,5]3
Grafo di Frucht 12 [-5,-2,-4,2,5,-2,2,5,-2,-5,4,2]
Grafo tetraedrico troncato 12 [2,6,-2]4
Grafo di Heawood 14 [5,-5]7
Grafo di Möbius-Kantor 16 [5,-5]8
Grafo di Pappus 18 [5,7,-7,7,-7,-5]3
Grafo di Desargues 20 [5,-5,9,-9]5
Grafo dodecaedrico 20 [10,7,4,-4,-7,10,-4,7,-7,4]2
Grafo di McGee 24 [12,7,-7]8
Grafo cubico 24 [2,9,-2,2,-9,-2]4
Grafo ottaedrico troncato 24 [3,-7,7,-3]6
Grafo di Nauru 24 [5,-9,7,-7,9,-5]4
Grafo F26A 26 [-7, 7]13
Grafo di Tutte-Coxeter 30 [-13,-9,7,-7,9,13]5
Grafo di Dyck 32 [5,-5,13,-13]8
Grafo di Gray 54 [-25,7,-7,13,-13,25]9
Grafo dodecaedrico troncato 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
Grafo di Harries 70 [-29,-19,-13,13,21,-27,27,33,-13,13,19,-21,-33,29]5
Grafo di Harrie-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]
Gabbia 10 di 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]
Grafo di Foster 90 [17,-9,37,-37,9,-17]15
Grafo di 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]
Gabbia 11 di 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]
Grafo di 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
Gabbia 12 di Tutte 126 [17, 27, -13, -59, -35, 35, -11, 13, -53, 53, -27, 21, 57, 11, -21, -57, 59, -17]7

Notazione LCF estesa

modifica

Una versione estesa, più complessa, della notazione LCF fu fornita da Coxeter, Frucht e Powers in un lavoro successivo.[6] In particolare, essi introdussero una notazione "anti-palindromica": se la seconda metà dei numeri tra parentesi quadre era l'inverso della prima metà, ma con tutti i segni cambiati, allora era sostituita da un punto e virgola e da un trattino. Il grafo di Nauru soddisfa questa condizione con [5, −9, 7, −7, 9, −5]4, e perciò può essere scritto [5, −9, 7; −]4 nella notazione estesa.[7]

  1. ^ a b Eppstein, D., The many faces of the Nauru graph Archiviato il 21 luglio 2011 in Internet Archive. on LiveJournal, 2007.
  2. ^ Tomaž Pisanski e Brigitte Servatius, 2.3.2 Cubic graphs and LCF notation, in Configurations from a Graphical Viewpoint, Springer, 2013, p. 32, ISBN 978-0-8176-8364-1.
  3. ^ R. Frucht, A canonical representation of trivalent Hamiltonian graphs, in Journal of Graph Theory, vol. 1, n. 1, 1976, pp. 45–60, DOI:10.1002/jgt.3190010111.
  4. ^ Klavdija Kutnar e Dragan Marušič, "Hamiltonicity of vertex-transitive graphs of order 4p," European Journal of Combinatorics, volume 29, numero 2 (febbraio 2008), pp. 423-438, sezione 2.
  5. ^ Ad es. Maple, NetworkX Archiviato il 2 marzo 2012 in Internet Archive., R Archiviato il 21 agosto 2009 in Internet Archive., e sage.
  6. ^ H. S. M. Coxeter, R. Frucht e D. L. Powers, Zero-symmetric graphs: trivalent graphical regular representations of groups, Academic Press, 1981, p. 54, ISBN 0-12-194580-4, MR 0658666.
  7. ^ Coxeter, Fruch e Powers (1981), p. 12.

Collegamenti esterni

modifica
  Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica