Código LCF

Un código LCF  es una notación en matemáticas combinatorias desarrollada por Lederberg y ampliada por Coxeter y Frucht para representar gráficos cúbicos que son hamiltonianos [2] [3] . Dado que los gráficos son hamiltonianos, los vértices se pueden colocar en un círculo que define dos aristas para cada vértice. El tercer borde ahora se puede describir por el número de posiciones que el final del borde está desde el principio (más en el sentido de las agujas del reloj y menos en el sentido contrario a las agujas del reloj). A menudo, el resultado es una secuencia repetitiva de números, en cuyo caso solo se escribe esta parte repetitiva y el número de repeticiones se muestra con un superíndice (como un grado). Por ejemplo, el conde de Nauru [1] tiene el código LCF [5, −9, 7, −7, 9, −5] 4 . Un mismo grafo puede tener diferentes códigos LCF dependiendo de cómo se ubiquen los vértices en el círculo (el grafo puede tener varias variantes del ciclo hamiltoniano).

Los números entre corchetes se consideran módulo , donde  es el número de vértices del gráfico. Los números módulo 0, 1 y no están permitidos [4] porque no pueden coincidir con ningún tercer borde.

Un código LCF es útil para una descripción concisa de los gráficos cúbicos hamiltonianos, en particular los que se enumeran en la siguiente tabla. Además, algunos paquetes de software de gráficos incluyen utilidades para crear un gráfico a partir de su código LCF [5] .

Ejemplos

Nombre picos código LCF
gráfico de tetraedro cuatro [2] 4
6 [3] 6
gráfico de cubo ocho [3,-3] 4
Conde Wagner ocho [4] 8 o [4,-3,3,4] 2
Cubo de Bidiakis 12 [6,4,-4] 4 o [6,-3,3,6,3,-3] 2 o [-3,6,4,-4,6,3,-4,6,-3, 3,6,4]
Conde de Franklin 12 [5,-5] 6 o [-5,-3,3,5] 3
Conde Fruhta 12 [-5,-2,-4,2.5,-2,2.5,-2,-5,4,2]
Gráfico de tetraedro truncado 12 [2,6,-2] 4
Conde de Heawood catorce [5,-5] 7
Gráfico de Möbius - Cantor dieciséis [5,-5] 8
Conde papá Dieciocho [5,7,-7,7,-7,-5] 3
Conde Desargués veinte [5,-5,9,-9] 5
gráfico de dodecaedro veinte [10.7.4,-4,-7.10,-4.7,-7.4] 2
conde mcgee 24 [12,7,-7] 8
Gráfico de cubo truncado 24 [2,9,-2,2,-9,-2] 4
Gráfico de un octaedro truncado 24 [3,-7,7,-3] 6
Conde de Nauru 24 [5,-9.7,-7.9,-5] 4
Cuenta F26A 26 [-7, 7] 13
Conde de Thatta-Coxeter treinta [-13,-9.7,-7.9.13] 5
conde dick 32 [5,-5,13,-13] 8
conde de gris 54 [-25.7,-7.13,-13.25] 9
Gráfico de dodecaedro truncado 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
conde de harris 70 [-29,-19,-13,13,21,-27,27,33,-13,13,19,-21,-33,29] 5
Conde 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]
balabán de 10 celdas 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]
Conde de Foster 90 [17,-9.37,-37.9,-17] 15
Conde 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]
Balabán de 11 celdas 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]
Conde de Liubliana 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 de 12 celdas 126 [17, 27, -13, -59, -35, 35, -11, 13, -53, 53, -27, 21, 57, 11, -21, -57, 59, -17] 7

Código LCF generalizado

Coxeter, Fruht y Powers propusieron una versión más compleja del código LCF en un trabajo posterior [6] . En particular, propusieron un código "antipalidrómico": si la segunda mitad de los números entre corchetes es la secuencia inversa de la primera parte con los signos invertidos, la segunda parte se reemplaza por un punto y coma y un guión. El gráfico de Nauru satisface esta condición, por lo que su código [5, −9, 7, −7, 9, −5] 4 puede generalizarse como [5, −9, 7; −] 4 [7] .

Notas

  1. ↑ 1 2 D. Eppstein , Las muchas caras del gráfico de Nauru Archivado desde el original el 21 de julio de 2011. en el sitio web de LiveJournal, 2007.
  2. ↑ Tomaž Pisanski, Brigitte Servatius. Configuraciones desde un punto de vista gráfico. - Springer, 2013. - ISBN 9780817683641 .
  3. ↑ R. Frucht. Una representación canónica de grafos hamiltonianos trivalentes // Journal of Graph Theory. - 1976. - Vol. 1 , número. 1 . — S. 45–60 . -doi : 10.1002 / jgt.3190010111 .
  4. ↑ Klavdija Kutnar, Dragan Marusic. Hamiltonicidad de gráficos transitivos de vértice de orden 4 p  // European Journal of Combinatorics. - T. 29 , n. 2 (febrero de 2008) . - S. 423-438, apartado 2. .
  5. ↑ por ejemplo, Maple Archivado el 2 de marzo de 2012 en Wayback Machine , NetworkX Archivado el 2 de marzo de 2012 en Wayback Machine , R Archivado el 21 de agosto de 2009 en Wayback Machine y sage Archivado el 27 de marzo de 2017 en Wayback Machine .
  6. ↑ Coxeter, Frucht, Powers, 1981 , pág. 54
  7. ↑ Coxeter, Frucht, Powers, 1981 , pág. 12

Enlaces