Échelle de Möbius

Échelle de Möbius
Deux vues de l'échelle de Möbius $ML_{8}$ . Cliquer ici pour voir la transition entre les deux vues.

Notation	$ML_{n}$ ^[1]
Nombre de sommets	$2n$
Nombre d'arêtes	$3n$ ( $n$ barreaux et $2n$ montants)
Distribution des degrés	Régulier, sommets de degré $3$
Diamètre	$\lceil {\frac {n}{2}}\rceil$
Maille	$4$
Nombre chromatique	$3$ si $n$ est pair, $2$ s'il est impair.
Propriétés	Régulier Hamiltonien Sommet-transitif
modifier

Dans la théorie des graphes, une branche des mathématiques, l'échelle de Möbius $ML_{n}$ est un graphe cubique formé à partir du graphe cycle à $2n$ sommets en ajoutant des arêtes entre les sommets opposés du cycle.

Les graphes de cette famille sont nommés ainsi car, si l'on excepte $ML_{3}$ ^[2], $ML_{n}$ possède exactement $n$ cycles à 4 sommets^[3] qui, mis ensemble par leurs sommets partagés, forment l'équivalent d'un ruban de Möbius. Les échelles de Möbius ont été nommées et étudiées pour la première fois par Richard Guy et Frank Harary en 1967^[4].

Propriétés modifier

Une vue de

ML_{8}

mettant en évidence sa ressemblance avec un ruban de Möbius

L'échelle de Möbius sur un ruban de Möbius.

Coloration avec 3 couleurs de

ML_{4}

.

Les échelles de Möbius sont des graphes circulants.

Elles ne sont pas des graphes planaires, mais peuvent être rendues planaires en supprimant un seul sommet, ce qui en fait des graphes apex (en). Il est possible de le dessiner sur un plan avec un seul croisement et ce nombre est minimal. Il peut être plongé (en) dans un tore ou un plan projectif sans croisements, il s'agit donc d'exemple de graphe toroïdal. De-Ming Li a exploré des plongements de ces graphes sur des surfaces d'ordre supérieur^[5].

Les échelles de Möbius sont sommet-transitives mais ne sont pas arête-transitives (sauf $ML_{3}$ ) : chaque montant de l'échelle appartient à un seul cycle de 4 sommets, tandis que les barreaux de l'échelle appartiennent chacun à deux de ces cycles.

Le théorème de Brooks et le fait que le graphe soit cubique garantissent que 3 couleurs suffisent à le colorer. De fait, quand $n$ est pair, on a besoin des trois couleurs, et dans le cas contraire deux couleurs suffisent. De plus, les échelles de Möbius sont déterminées de façon unique par leurs polynômes chromatiques^[6].

L'échelle de Möbius $ML_{4}$ possède 392 arbres couvrants. Elle et $ML_{3}$ ont le plus d'arbres couvrants parmi tous les graphes cubiques ayant le même nombre de sommets^[7]^,^[8]. Ce n'est toutefois pas général. En effet, le graphe cubique à 10 sommet ayant le plus d'arbres couvrants est le graphe de Petersen, qui n'est pas une échelle de Möbius.

Les polynômes de Tuttes des échelles de Möbius peuvent être calculés à l'aide d'une simple relation de récurrence^[9].

Mineurs du graphe modifier

Vue en trois dimensions de

ML_{4}

. Un des cycles hamiltoniens est numéroté.

Vue en trois dimensions de

ML_{6}

.

Les échelles de Möbius jouent un rôle important dans l'histoire de mineurs de graphes. Le résultat le plus ancien dans ce domaine est le théorème de 1937 de Klaus Wagner affirmant que les graphes sans mineur peut être formé en utilisant des opérations de somme de clique (en) pour combiner des graphes planaires et l'échelle de Möbius $ML_{4}$ . Pour cette raison, $ML_{4}$ est appelé le graphe de Wagner^[10].

Gubser (1996) définit un graphe presque planaire comme un graphe non planaire dans lequel tout mineur non trivial est planaire. Il montre que les graphes presque planaires 3-connexes sont des échelles de Möbius ou des membres d'un petit nombre d'autres familles et que d'autres graphes presque-planaires peuvent être formés à partir d'une suite d'opérations simples^[11].

John Maharry a montré que presque tous les graphes qui n'ont pas un mineur cubique peuvent être déduits d'une suite d'opérations simples à partir d'échelles de Möbius^[12].

Applications modifier

D. Walba et ses collègues ont synthétisé les premiers des structures moléculaires en forme d'échelle de Möbius^[13], et depuis cette structure a été objet d'intérêt en chimie et en stéréochimie^[14], et en particulier en relation avec la forme en échelle des molécules d'ADN. En gardant cette application à l'esprit, Erica Flapan étudie^[15] les symétries mathématiques des plongements (en) des échelles de Möbius dans $\mathbb {R} ^{3}$ .

Les échelles de Möbius ont également été utilisées pour la forme d'anneaux supraconducteurs dans des expériences consistant à étudier la structure spatiale des conducteurs dans les interactions entre électrons^[16]^,^[17].

Enfin, elles ont également été utilisées en informatique, dans le cadre d'approches par optimisation linéaire en nombres entiers de problèmes de set packing et d'ordonnancement. Les échelles de möbius peuvent servir à définir les facettes du polytope qui décrit une relaxation continue du problème ; ces facettes sont appelées contraintes en échelle de Möbius^[18]^,^[19]^,^[20]^,^[21]^,^[22].

Notes et références modifier

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Möbius ladder » (voir la liste des auteurs).

↑ Par exemple Graph Theory – Lecture 2, University of Columbia. De nombreuses autres notations coexistent.
↑ $ML_{3}$ est le graphe biparti complet $K_{3,3}$
↑ (en) John P. McSorley, « Counting structures in the Möbius ladder », Discrete Mathematics, vol. 184, n^os 1 à 3,‎ 1998, p. 137-164 (DOI 10.1016/S0012-365X(97)00086-1, MR 1609294)
↑ (en) Richard Guy et Frank Harary, « On the Möbius ladders », Canadian Mathematical Bulletin, vol. 10,‎ 1967, p. 493-496 (DOI 10.4153/CMB-1967-046-4, MR 0224499)
↑ (en) De-ming Li, « Genus distributions of Möbius ladders », Northeastern Mathematics Journal, vol. 21, n^o 1,‎ 2005, p. 70-80 (MR 2124859)
↑ (en) Anna de Mier et Marc Noy, « On graphs determined by their Tutte polynomials », Graphs and Combinatorics, vol. 20, n^o 1,‎ 2004, p. 105-119 (DOI 10.1007/s00373-003-0534-z, MR 2048553)
↑ (en) Dmitry Jakobson et Igor Rivin, « On some extremal problems in graph theory », arXiv,‎ 1999 (lire en ligne)
↑ (en) L. Valdes, « Extremal properties of spanning trees in cubic graphs », Proceedings of the Twenty-second Southeastern Conference on Combinatorics, Graph Theory, and Computing (Baton Rouge, LA, 1991), Congressus Numerantium, vol. 85,‎ 1991, p. 143-160 (MR 1152127)
↑ (en) N. L. Biggs, R. M. Damerell et D. A. Sands, « Recursive families of graphs », Journal of Combinatorial Theory, b, vol. 12,‎ 1972, p. 123-131 (DOI 10.1016/0095-8956(72)90016-0, MR 0294172).
↑ (de) K. Wagner, « Über eine Eigenschaft der ebenen Komplexe », Mathematische Annalen, vol. 114,‎ 1937, p. 570-590 (DOI 10.1007/BF01594196, MR 1513158)
↑ (en) Gubser, Bradley S., « A characterization of almost-planar graphs », Combinatorics, Probability and Computing, vol. 5, n^o 3,‎ 1996, p. 227-245 (DOI 10.1017/S0963548300002005)
↑ (en) John Maharry, « A characterization of graphs with no cube minor », Journal of Combinatorial Theory, b, vol. 80, n^o 2,‎ 2000, p. 179-201 (DOI 10.1006/jctb.2000.1968)
↑ (en) D. Walba, R. Richards et R. C. Haltiwanger, « Total synthesis of the first molecular Möbius strip », Journal of the American Chemical Society, vol. 104, n^o 11,‎ 1982, p. 3219-3221 (DOI 10.1021/ja00375a051).
↑ (en) Jonathan Simon, « Knots and chemistry », dans New scientific applications of geometry and topology, Providence, RI, AMS, coll. « Proceedings of Symposia in Applied Mathematics » (n^o 45), 1992 (MR 1196717), p. 97-130.
↑ (en) Erica Flapan, « Symmetries of Möbius ladders », Mathematische Annalen, vol. 283, n^o 2,‎ 1989, p. 271-283 (DOI 10.1007/BF01446435).
↑ (en) Frédéric Mila, C. A. Stafford et Sylvain Capponi, « Persistent currents in a Möbius ladder: A test of interchain coherence of interacting electrons », Physical Review B, vol. 57, n^o 3,‎ 1998, p. 1457-1460 (DOI 10.1103/PhysRevB.57.1457, lire en ligne).
↑ (en) Wen-Ji Deng, Ji-Huan Xu et Ping Liu, « Period halving of persistent currents in mesoscopic Möbius ladders », Chinese Physics Letters, vol. 19, n^o 7,‎ 2002, p. 988-991 (DOI 10.1088/0256-307X/19/7/333, arXiv cond-mat/0209421).
↑ (en) G. Bolotashvili, M. Kovalev et E. Girlich, « New facets of the linear ordering polytope », SIAM Journal on Discrete Mathematics, vol. 12, n^o 3,‎ 1999, p. 326-336 (DOI 10.1137/S0895480196300145).
↑ (en) Ralf Borndörfer et Robert Weismantel, « Set packing relaxations of some integer programs », Mathematical Programming, Series A, vol. 88, n^o 3,‎ 2000, p. 425-450 (DOI 10.1007/PL00011381, MR 1782150).
↑ (en) M. Grötschel, M. Jünger et G. Reinelt, « On the acyclic subgraph polytope », Mathematical Programming, vol. 33,‎ 1985, p. 28-42 (DOI 10.1007/BF01582009, MR 0809747).
↑ (en) M. Grötschel, M. Jünger et G. Reinelt, « Facets of the linear ordering polytope », Mathematical Programming, vol. 33,‎ 1985, p. 43-60 (DOI 10.1007/BF01582010, MR 0809747).
↑ (en) Alantha Newman et Santosh Vempala, « Fences are futile: on relaxations for the linear ordering problem », dans Integer Programming and Combinatorial Optimization: 8th International IPCO Conference, Utrecht, The Netherlands, June 13–15, 2001, Proceedings, Berlin, Springer-Verlag, coll. « Lecture Notes in Computer Science » (n^o 2081), 2001 (DOI 10.1007/3-540-45535-3_26, MR 2041937, lire en ligne), p. 333-347.

Voir aussi modifier

Articles connexes modifier

Liens externes modifier

(en) Eric W. Weisstein, « Möbius Ladder », sur MathWorld

Portail des mathématiques

[1] Par exemple Graph Theory – Lecture 2, University of Columbia. De nombreuses autres notations coexistent.

[2] $ML_{3}$ est le graphe biparti complet $K_{3,3}$

[3] (en) John P. McSorley, « Counting structures in the Möbius ladder », Discrete Mathematics, vol. 184, n^os 1 à 3,‎ 1998, p. 137-164 (DOI 10.1016/S0012-365X(97)00086-1, MR 1609294)

[4] (en) Richard Guy et Frank Harary, « On the Möbius ladders », Canadian Mathematical Bulletin, vol. 10,‎ 1967, p. 493-496 (DOI 10.4153/CMB-1967-046-4, MR 0224499)

[5] (en) De-ming Li, « Genus distributions of Möbius ladders », Northeastern Mathematics Journal, vol. 21, n^o 1,‎ 2005, p. 70-80 (MR 2124859)

[6] (en) Anna de Mier et Marc Noy, « On graphs determined by their Tutte polynomials », Graphs and Combinatorics, vol. 20, n^o 1,‎ 2004, p. 105-119 (DOI 10.1007/s00373-003-0534-z, MR 2048553)

[7] (en) Dmitry Jakobson et Igor Rivin, « On some extremal problems in graph theory », arXiv,‎ 1999 (lire en ligne)

[8] (en) L. Valdes, « Extremal properties of spanning trees in cubic graphs », Proceedings of the Twenty-second Southeastern Conference on Combinatorics, Graph Theory, and Computing (Baton Rouge, LA, 1991), Congressus Numerantium, vol. 85,‎ 1991, p. 143-160 (MR 1152127)

[9] (en) N. L. Biggs, R. M. Damerell et D. A. Sands, « Recursive families of graphs », Journal of Combinatorial Theory, b, vol. 12,‎ 1972, p. 123-131 (DOI 10.1016/0095-8956(72)90016-0, MR 0294172).

[10] (de) K. Wagner, « Über eine Eigenschaft der ebenen Komplexe », Mathematische Annalen, vol. 114,‎ 1937, p. 570-590 (DOI 10.1007/BF01594196, MR 1513158)

[11] (en) Gubser, Bradley S., « A characterization of almost-planar graphs », Combinatorics, Probability and Computing, vol. 5, n^o 3,‎ 1996, p. 227-245 (DOI 10.1017/S0963548300002005)

[12] (en) John Maharry, « A characterization of graphs with no cube minor », Journal of Combinatorial Theory, b, vol. 80, n^o 2,‎ 2000, p. 179-201 (DOI 10.1006/jctb.2000.1968)

[13] (en) D. Walba, R. Richards et R. C. Haltiwanger, « Total synthesis of the first molecular Möbius strip », Journal of the American Chemical Society, vol. 104, n^o 11,‎ 1982, p. 3219-3221 (DOI 10.1021/ja00375a051).

[14] (en) Jonathan Simon, « Knots and chemistry », dans New scientific applications of geometry and topology, Providence, RI, AMS, coll. « Proceedings of Symposia in Applied Mathematics » (n^o 45), 1992 (MR 1196717), p. 97-130.

[15] (en) Erica Flapan, « Symmetries of Möbius ladders », Mathematische Annalen, vol. 283, n^o 2,‎ 1989, p. 271-283 (DOI 10.1007/BF01446435).

[16] (en) Frédéric Mila, C. A. Stafford et Sylvain Capponi, « Persistent currents in a Möbius ladder: A test of interchain coherence of interacting electrons », Physical Review B, vol. 57, n^o 3,‎ 1998, p. 1457-1460 (DOI 10.1103/PhysRevB.57.1457, lire en ligne).

[17] (en) Wen-Ji Deng, Ji-Huan Xu et Ping Liu, « Period halving of persistent currents in mesoscopic Möbius ladders », Chinese Physics Letters, vol. 19, n^o 7,‎ 2002, p. 988-991 (DOI 10.1088/0256-307X/19/7/333, arXiv cond-mat/0209421).

[18] (en) G. Bolotashvili, M. Kovalev et E. Girlich, « New facets of the linear ordering polytope », SIAM Journal on Discrete Mathematics, vol. 12, n^o 3,‎ 1999, p. 326-336 (DOI 10.1137/S0895480196300145).

[19] (en) Ralf Borndörfer et Robert Weismantel, « Set packing relaxations of some integer programs », Mathematical Programming, Series A, vol. 88, n^o 3,‎ 2000, p. 425-450 (DOI 10.1007/PL00011381, MR 1782150).

[20] (en) M. Grötschel, M. Jünger et G. Reinelt, « On the acyclic subgraph polytope », Mathematical Programming, vol. 33,‎ 1985, p. 28-42 (DOI 10.1007/BF01582009, MR 0809747).

[21] (en) M. Grötschel, M. Jünger et G. Reinelt, « Facets of the linear ordering polytope », Mathematical Programming, vol. 33,‎ 1985, p. 43-60 (DOI 10.1007/BF01582010, MR 0809747).

[22] (en) Alantha Newman et Santosh Vempala, « Fences are futile: on relaxations for the linear ordering problem », dans Integer Programming and Combinatorial Optimization: 8th International IPCO Conference, Utrecht, The Netherlands, June 13–15, 2001, Proceedings, Berlin, Springer-Verlag, coll. « Lecture Notes in Computer Science » (n^o 2081), 2001 (DOI 10.1007/3-540-45535-3_26, MR 2041937, lire en ligne), p. 333-347.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]