Notação LCF - LCF notation
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
- Weisstein, Eric W. "LCF Notation" . MathWorld .
- Ed Pegg Jr. (29 de dezembro de 2003), Math Games: Cubic Symmetric Graphs , Mathematical Association of America
- "Gráficos Hamiltonianos Cúbicos da Notação LCF" - aplicativo interativo JavaScript, desenvolvido com a biblioteca D3js