Notation LCF
En mathématiques, et plus particuliÚrement en théorie des graphes, la notation LCF ou le code LCF (pour Lederberg-Coxeter-Frucht) est une notation imaginée par Joshua Lederberg et étendue par Harold Coxeter et Robert Frucht qui sert à représenter les graphes cubiques qui sont hamiltoniens[1].
Principe
Comme le graphe est hamiltonien, les sommets peuvent ĂȘtre arrangĂ©s en cercle, chaque sommet ayant deux arĂȘtes sur le cercle. La troisiĂšme arĂȘte peut ĂȘtre dĂ©crite par le nombre de positions sur le cercle qu'il faut parcourir pour atteindre l'autre extrĂ©mitĂ© de l'arĂȘte. Si l'on parcourt ces positions dans le sens des aiguilles d'une montre, on considĂšre le nombre comme positif, et si on les parcourt dans le sens inverse des aiguilles d'une montre, on le considĂšre comme nĂ©gatif.
Comme cette suite de nombres se rĂ©pĂšte souvent, on abrĂšge la notation en notant le nombre de rĂ©pĂ©titions du motif de base en exposant. Par exemple, le graphe de Nauru[2] (figure) a pour notation LCF [5, â9, 7, â7, 9, â5]4.
Le mĂȘme graphe peut ĂȘtre reprĂ©sentĂ© par plusieurs notations LCF diffĂ©rentes, selon la façon dont les sommets sont arrangĂ©s.
Les nombres entre crochets sont pris entre 2 et Nâ2, N Ă©tant le nombre de sommets. Les nombres 0, 1 et Nâ1 ne sont pas permis, puisque les arĂȘtes correspondantes mĂšneraient soit au sommet lui-mĂȘme, soit Ă ses voisins sur le cycle[3].
Utilisation
La notation LCF fournit une description concise des graphes cubiques hamiltoniens, utile dans les publications papier.
En outre, des logiciels de manipulation de graphes comprennent des utilitaires pour créer un graphe à partir de sa notation LCF. On peut citer Maple, NetworkX, R et sage.
Notes et références
- (en) Robert Frucht, « A canonical representation of trivalent Hamiltonian graphs », Journal of Graph Theory, vol. 1, no 1,â , p. 45â60 (DOI 10.1002/jgt.3190010111).
- (en) David Eppstein, The many faces of the Nauru graph dans LiveJournal, 2007.
- (en) Klavdija Kutnar et Dragan MaruĆĄiÄ, « Hamiltonicity of vertex-transitive graphs of order 4p », European Journal of Combinatorics, vol. 29, no 2,â , p. 423-438, section 2 (lire en ligne).
Voir aussi
Source
- (en) Cet article est partiellement ou en totalitĂ© issu de lâarticle de WikipĂ©dia en anglais intitulĂ© « LCF Notation » (voir la liste des auteurs).
Liens externes
- (en) Eric W. Weisstein, « LCF Notation », sur MathWorld
- (en) Ed Pegg Jr., « Math Games: Cubic Symmetric Graphs », Mathematical Association of America,
- (en) Cubic Hamiltonian Graphs from LCF Notation, une application JavaScript interactive