Em matemática , e mais particularmente na teoria dos grafos , a notação LCF ou o código LCF (para L ederberg- C oxeter- F rucht) é uma notação imaginada por Joshua Lederberg e estendida por Harold Coxeter e Robert Frucht que é usada para representar gráficos cúbicos que são hamiltonianos .
Como o gráfico é hamiltoniano, os vértices podem ser dispostos em um círculo, cada vértice tendo duas arestas no círculo. A terceira borda pode ser descrita pelo número de posições no círculo que devem ser percorridas para alcançar a outra extremidade da borda. Se alguém percorrer essas posições no sentido horário, o número é considerado positivo, e se for percorrido no sentido anti-horário, é considerado negativo.
Como essa sequência de números é freqüentemente repetida, a notação é abreviada observando o número de repetições do padrão básico em sobrescrito. Por exemplo, o gráfico de Nauru (figura) tem a notação LCF [5, −9, 7, −7, 9, −5] 4 .
O mesmo gráfico pode ser representado por várias notações LCF diferentes, dependendo de como os vértices estão organizados.
Os números entre parênteses são considerados entre 2 e N −2, sendo N o número de vértices. Os números 0, 1 e N −1 não são permitidos, pois as arestas correspondentes levariam ao próprio vértice ou a seus vizinhos no ciclo.
A notação LCF fornece uma descrição concisa dos gráficos cúbicos hamiltonianos, úteis em publicações impressas.
Além disso, o software de manipulação de gráfico inclui utilitários para criar um gráfico a partir de sua notação LCF. Podemos citar Maple , NetworkX , R e sage .