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]⁴.

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, n^o 1,‎ 1976, 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, n^o 2,‎ février 2008, 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, 29 décembre 2003
(en) Cubic Hamiltonian Graphs from LCF Notation, une application JavaScript interactive

Portail des mathématiques

[1] (en) Robert Frucht, « A canonical representation of trivalent Hamiltonian graphs », Journal of Graph Theory, vol. 1, n^o 1,‎ 1976, p. 45–60 (DOI 10.1002/jgt.3190010111).

[2] (en) David Eppstein, The many faces of the Nauru graph dans LiveJournal, 2007.

[3] (en) Klavdija Kutnar et Dragan Marušič, « Hamiltonicity of vertex-transitive graphs of order 4p », European Journal of Combinatorics, vol. 29, n^o 2,‎ février 2008, p. 423-438, section 2 (lire en ligne).

[1]

[2]

[3]