Notação LCF - LCF notation

O gráfico de Nauru tem notação LCF [5, −9, 7, −7, 9, −5] 4 .

Em matemática combinatória , a notação LCF ou código LCF é uma notação desenvolvida por Joshua Lederberg e estendida por HSM Coxeter e Robert Frucht , para a representação de gráficos cúbicos que contêm um ciclo hamiltoniano . O próprio ciclo inclui duas das três adjacências para cada vértice, e a notação LCF especifica a que distância ao longo do ciclo está o terceiro vizinho de cada vértice. Um único gráfico pode ter várias representações diferentes na notação LCF.

Descrição

Em um grafo hamiltoniano, os vértices podem ser organizados em um ciclo , o que representa duas arestas por vértice. A terceira aresta de cada vértice pode então ser descrita por quantas posições no sentido horário (positivo) ou anti-horário (negativo) ela lidera. A forma básica da notação LCF é apenas a sequência desses números de posições, começando de um vértice escolhido arbitrariamente e escrito entre colchetes. Os números entre os colchetes são interpretados como módulo N , onde N é o número de vértices. As entradas do módulo congruente N a 0, 1 ou N  - 1 não aparecem nesta sequência de números, porque corresponderiam a um laço ou a múltiplas adjacências , nenhuma das quais é permitida em grafos simples.

Freqüentemente, o padrão se repete e o número de repetições pode ser indicado por um sobrescrito na notação. Por exemplo, o gráfico de Nauru , mostrado à direita, tem quatro repetições dos mesmos seis deslocamentos e pode ser representado pela notação LCF [5, −9, 7, −7, 9, −5] 4 . Um único gráfico pode ter várias notações LCF diferentes, dependendo das escolhas do ciclo hamiltoniano e do vértice inicial.

Formulários

A notação LCF é útil na publicação de descrições concisas de gráficos cúbicos hamiltonianos, como os exemplos abaixo. Além disso, alguns pacotes de software para manipulação de gráficos incluem utilitários para criar um gráfico a partir de sua notação LCF.

Se um gráfico é representado pela notação LCF, é simples testar se o gráfico é bipartido : isso é verdadeiro se e somente se todos os deslocamentos na notação LCF forem ímpares.

Exemplos

Nome Vértices Notação LCF
Gráfico tetraédrico 4 [2] 4
Gráfico de utilidades 6 [3] 6
Gráfico cúbico 8 [3, −3] 4
Gráfico de Wagner 8 [4] 8 ou [4, −3,3,4] 2
Cubo bidiakis 12 [6,4, −4] 4 ou [6, −3,3,6,3, −3] 2 ou [−3,6,4, −4,6,3, −4,6, −3, 3,6,4]
Gráfico de Franklin 12 [5, −5] 6 ou [−5, −3,3,5] 3
Gráfico de Frucht 12 [−5, −2, −4,2,5, −2,2,5, −2, −5,4,2]
Gráfico tetraédrico truncado 12 [2,6, -2] 4
Gráfico de Heawood 14 [5, −5] 7
Gráfico Möbius-Kantor 16 [5, −5] 8
Gráfico de Pappus 18 [5,7, −7,7, −7, −5] 3
O menor gráfico de simetria zero 18 [5, −5] 9
Gráfico Desargues 20 [5, −5,9, −9] 5
Gráfico dodecaédrico 20 [10,7,4, −4, −7,10, −4,7, −7,4] 2
Gráfico de McGee 24 [12,7, −7] 8
Gráfico cúbico truncado 24 [2,9, −2,2, −9, −2] 4
Gráfico octaédrico truncado 24 [3, −7,7, −3] 6
Gráfico de Nauru 24 [5, −9,7, −7,9, −5] 4
Gráfico F26A 26 [-7, 7] 13
Gráfico Tutte-Coxeter 30 [−13, −9,7, −7,9,13] 5
Gráfico Dyck 32 [5, −5,13, ​​−13] 8
Gráfico cinza 54 [−25,7, −7,13, −13,25] 9
Gráfico dodecaédrico 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
Gráfico de Harries 70 [−29, −19, −13,13,21, −27,27,33, −13,13,19, −21, −33,29] 5
Gráfico Harries-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]
Balaban 10-gaiola 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]
Gráfico Foster 90 [17, −9,37, −37,9, −17] 15
Gráfico 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]
Balaban 11-gaiola 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]
Gráfico 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
Tutte 12-gaiola 126 [17, 27, −13, −59, −35, 35, −11, 13, −53, 53, −27, 21, 57, 11, −21, −57, 59, −17] 7

Notação LCF estendida

Uma versão estendida mais complexa da notação LCF foi fornecida por Coxeter, Frucht e Powers em um trabalho posterior. Em particular, eles introduziram uma notação "antipalíndrômica": se a segunda metade dos números entre colchetes fosse o reverso da primeira metade, mas com todos os sinais alterados, então ela foi substituída por um ponto e vírgula e um travessão. O gráfico de Nauru satisfaz essa condição com [5, −9, 7, −7, 9, −5] 4 e, portanto, pode ser escrito [5, −9, 7; -] 4 na notação estendida.

Referências

links externos