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. 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, 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.
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.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. 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.Ad es. Maple, NetworkX , R , e sage.
Esempi Nome Vertici Notazione LCFGrafo tetraedrico 4 4Grafo dei servizi pubblici 6 6Grafo cubico 8 [3,-3]4Grafo di Wagner 8 8 or [4,-3,3,4]2Cubo 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]3Grafo di Frucht 12 [-5,-2,-4,2,5,-2,2,5,-2,-5,4,2]Grafo tetraedrico troncato 12 [2,6,-2]4Grafo di Heawood 14 [5,-5]7Grafo di Möbius-Kantor 16 [5,-5]8Grafo di Pappus 18 [5,7,-7,7,-7,-5]3Grafo di Desargues 20 [5,-5,9,-9]5Grafo dodecaedrico 20 [10,7,4,-4,-7,10,-4,7,-7,4]2Grafo di McGee 24 [12,7,-7]8Grafo cubico 24 [2,9,-2,2,-9,-2]4Grafo ottaedrico troncato 24 [3,-7,7,-3]6Grafo di Nauru 24 [5,-9,7,-7,9,-5]4Grafo F26A 26 [-7, 7]13Grafo di Tutte-Coxeter 30 [-13,-9,7,-7,9,13]5Grafo di Dyck 32 [5,-5,13,-13]8Grafo di Gray 54 [-25,7,-7,13,-13,25]9Grafo 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]2Grafo di Harries 70 [-29,-19,-13,13,21,-27,27,33,-13,13,19,-21,-33,29]5Grafo 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]15Grafo 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]2Gabbia 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 Una versione estesa, più complessa, della notazione LCF fu fornita da Coxeter, Frucht e Powers in un lavoro successivo. 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..
Note
Collegamenti esterni
Cubic Hamiltonian Graphs from LCF Notation - Applicazione interattiva JavaScript, costruita con la libreria D3js
Categoria:Teoria dei grafi