En el campo matemático de la teoría de grafos , la notación LCF o código LCF es una notación ideada por Joshua Lederberg y ampliada por HSM Coxeter y Robert Frucht para la representación de grafos cúbicos que contienen un ciclo hamiltoniano . [2] [3] El ciclo en sí incluye dos de las tres adyacencias para cada vértice , y la notación LCF especifica qué tan lejos a lo largo del ciclo se encuentra el tercer vecino de cada vértice. Un solo grafo puede tener múltiples representaciones diferentes en la notación LCF.
En un grafo hamiltoniano, los vértices se pueden organizar en un ciclo , que representa dos aristas por vértice. La tercera arista de cada vértice se puede describir entonces por cuántas posiciones en el sentido de las agujas del reloj (positivo) o en el sentido contrario a las agujas del reloj (negativo) conduce. La forma básica de la notación MCF es simplemente la secuencia de estos números de posiciones, comenzando desde un vértice elegido arbitrariamente y escrito entre corchetes. Los números entre los corchetes se interpretan módulo N , donde N es el número de vértices. Las entradas congruentes módulo N con 0, 1 o N − 1 no aparecen en esta secuencia de números, [4] porque corresponderían a un bucle o a una adyacencia múltiple , ninguna de las cuales está permitida en grafos simples.
A menudo, el patrón se repite y la cantidad de repeticiones se puede indicar mediante un superíndice en la notación. Por ejemplo, el gráfico de Nauru , [1] que se muestra a la derecha, tiene cuatro repeticiones de los mismos seis desplazamientos y se puede representar mediante la notación LCF [5, −9, 7, −7, 9, −5] 4 . Un solo gráfico puede tener varias notaciones LCF diferentes, según las opciones de ciclo hamiltoniano y vértice inicial.
La notación MCF es útil para publicar descripciones concisas de gráficos cúbicos hamiltonianos, como los ejemplos que se muestran a continuación. Además, algunos paquetes de software para manipular gráficos incluyen utilidades para crear un gráfico a partir de su notación MCF. [5]
Si un gráfico se representa mediante la notación LCF, es sencillo comprobar si el gráfico es bipartito : esto es cierto si y solo si todos los desplazamientos en la notación LCF son impares. [6]
Coxeter, Frucht y Powers proporcionaron una versión extendida más compleja de la notación LCF en trabajos posteriores. [8] En particular, introdujeron una notación "antipalindrómica": si la segunda mitad de los números entre corchetes era la inversa de la primera mitad, pero con todos los signos cambiados, entonces se reemplazaba por un punto y coma y un guión. El grafo de Nauru satisface esta condición con [5, −9, 7, −7, 9, −5] 4 , y por lo tanto puede escribirse [5, −9, 7; −] 4 en la notación extendida. [9]