Hispanopedia Wiki
Articulo de referencia

Notación LCF

El gráfico de Nauru [ 1 ] tiene la notación LCF [5, −9, 7, −7, 9, −5] 4 . 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...

Hispanopedia WikiContenido en espanolLectura gratuita
El gráfico de Nauru [ 1 ] tiene la notación LCF [5, −9, 7, −7, 9, −5] 4 .

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 extendida 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 a lo largo del ciclo se encuentra el tercer vecino de cada vértice. Un solo grafo puede tener múltiples representaciones diferentes en notación LCF.

Descripción

En un grafo hamiltoniano, los vértices se pueden organizar en un ciclo , que representa dos aristas por vértice. La tercera arista desde cada vértice se puede describir por la cantidad de posiciones que conduce en sentido horario (positivo) o antihorario (negativo). La forma básica de la notación LCF 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 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 el número de repeticiones se puede indicar con un superíndice en la notación. Por ejemplo, el grafo de Nauru [ 1 ] , que se muestra a la derecha, tiene cuatro repeticiones de los mismos seis desplazamientos y se puede representar con la notación LCF [5, -9 , 7, -7 , 9, -5 ] ⁴ . Un mismo grafo puede tener varias notaciones LCF diferentes, dependiendo de la elección del ciclo hamiltoniano y del vértice inicial.     

Aplicaciones

La notación LCF es útil para publicar descripciones concisas de grafos cúbicos hamiltonianos, como los ejemplos que se muestran a continuación. Además, algunos paquetes de software para manipular grafos incluyen utilidades para crear un grafo a partir de su notación LCF. [ 5 ]

Si un grafo se representa mediante la notación LCF, es sencillo comprobar si el grafo es bipartito : esto es cierto si y solo si todos los desplazamientos en la notación LCF son impares. [ 6 ]

Ejemplos

Notación LCF extendida

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 guion. El grafo Nauru satisface esta condición con [5, − 9, 7, − 7, 9, − 5] 4 , y por lo tanto se puede escribir [5, − 9, 7; − ] 4 en la notación extendida. [ 9 ]        

Referencias

  1. 1 2 Eppstein, D. , Las muchas caras del gráfico de Nauru , 2007.
  2. ↑ Pisanski, Tomaž ; Servatius, Brigitte (2013), "2.3.2 Gráficos cúbicos y notación LCF" , Configurations from a Graphical Viewpoint , Springer, p.  32, ISBN 9780817683641.
  3. ↑ Frucht, R. (1976), "Una representación canónica de grafos hamiltonianos trivalentes", Journal of Graph Theory , 1 (1): 45– 60, doi : 10.1002/jgt.3190010111 , MR 0463029 .
  4. ↑ Kutnar, Klavdija ; Marušič, Dragan (2008), "Hamiltonicidad de gráficos transitivos de vértices de orden 4 p ", European Journal of Combinatorics , 29 (2): 423– 438, arXiv : math/0606585 , doi : 10.1016/j.ejc.2007.02.002 , MR 2388379 Véase la Sección 2.
  5. ↑ p. ej. Maple , NetworkX Archivado el 2 de marzo de 2012 en Wayback Machine , igraph y sage .
  6. ↑ Coxeter, Harold Scott MacDonald ; Frucht, Roberto ; Powers, David L. (1981), Grafos simétricos cero , Academic Press, Inc. [Harcourt Brace Jovanovich, Editores], Nueva York-Londres, pág. 13, ISBN  0-12-194580-4, MR 0658666 .
  7. ^ Coxeter, Frucht y Powers (1981) , figura 1.1, pág. 5.
  8. ^ Coxeter, Frucht y Powers (1981) , pág. 54.
  9. ^ Coxeter, Frucht y Powers (1981) , pág. 12.
  • Weisstein, Eric W. "Notación LCF" . MathWorld .
  • Ed Pegg Jr. (29 de diciembre de 2003), Juegos matemáticos: grafos cúbicos simétricos , Asociación Matemática de América, archivado del original el 7 de mayo de 2013 , recuperado el 25 de septiembre de 2010.
  • "Gráficos hamiltonianos cúbicos a partir de la notación LCF" – Aplicación interactiva en JavaScript, creada con la biblioteca D3js.