Échelle de Möbius

Un article de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche

Échelle de Möbius
image illustrative de l’article Échelle de Möbius
Deux vues de l'échelle de Möbius . Cliquer ici pour voir la transition entre les deux vues.

Notation [1]
Nombre de sommets
Nombre d'arêtes ( barreaux et montants)
Distribution des degrés Régulier, sommets de degré
Diamètre
Maille
Nombre chromatique si est pair, s'il est impair.
Propriétés Régulier
Hamiltonien
Sommet-transitif

Dans la théorie des graphes, une branche des mathématiques, l'échelle de Möbius est un graphe cubique formé à partir du graphe cycle à 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 [2], possède exactement 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 | modifier le code]

Une vue de 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 .

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 (en) (sauf ) : 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 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 possède 392 arbres couvrants. Elle et 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 | modifier le code]

Vue en trois dimensions de . Un des cycles hamiltoniens est numéroté.
Vue en trois dimensions de .

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 est 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 . Pour cette raison, 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 | modifier le code]

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 .

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 | modifier le code]

(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).

  1. Par exemple Graph Theory – Lecture 2, University of Columbia. De nombreuses autres notations coexistent.
  2. est le graphe biparti complet
  3. (en) John P. McSorley, « Counting structures in the Möbius ladder », Discrete Mathematics, vol. 184, nos 1 à 3,‎ , p. 137-164 (DOI 10.1016/S0012-365X(97)00086-1, Math Reviews 1609294)
  4. (en) Richard Guy et Frank Harary, « On the Möbius ladders », Canadian Mathematical Bulletin, vol. 10,‎ , p. 493-496 (DOI 10.4153/CMB-1967-046-4, Math Reviews 0224499)
  5. (en) De-ming Li, « Genus distributions of Möbius ladders », Northeastern Mathematics Journal, vol. 21, no 1,‎ , p. 70-80 (Math Reviews 2124859)
  6. (en) Anna de Mier et Marc Noy, « On graphs determined by their Tutte polynomials », Graphs and Combinatorics, vol. 20, no 1,‎ , p. 105-119 (DOI 10.1007/s00373-003-0534-z, Math Reviews 2048553)
  7. (en) Dmitry Jakobson et Igor Rivin, « On some extremal problems in graph theory », arXiv,‎ (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), série Congressus Numerantium, vol. 85,‎ , p. 143-160 (Math Reviews 1152127)
  9. (en) N. L. Biggs, R. M. Damerell et D. A. Sands, « Recursive families of graphs », Journal of Combinatorial Theory, série B, vol. 12,‎ , p. 123-131 (DOI 10.1016/0095-8956(72)90016-0, Math Reviews 0294172).
  10. (de) K. Wagner, « Über eine Eigenschaft der ebenen Komplexe », Mathematische Annalen, vol. 114,‎ , p. 570-590 (DOI 10.1007/BF01594196, Math Reviews 1513158)
  11. (en) Gubser, Bradley S., « A characterization of almost-planar graphs », Combinatorics, Probability and Computing, vol. 5, no 3,‎ , p. 227-245 (DOI 10.1017/S0963548300002005)
  12. (en) John Maharry, « A characterization of graphs with no cube minor », Journal of Combinatorial Theory, série B, vol. 80, no 2,‎ , 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, no 11,‎ , 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 » (no 45), (Math Reviews 1196717), p. 97-130.
  15. (en) Erica Flapan, « Symmetries of Möbius ladders », Mathematische Annalen, vol. 283, no 2,‎ , 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, no 3,‎ , 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, no 7,‎ , 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, no 3,‎ , 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, no 3,‎ , p. 425-450 (DOI 10.1007/PL00011381, Math Reviews 1782150).
  20. (en) M. Grötschel, M. Jünger et G. Reinelt, « On the acyclic subgraph polytope », Mathematical Programming, vol. 33,‎ , p. 28-42 (DOI 10.1007/BF01582009, Math Reviews 0809747).
  21. (en) M. Grötschel, M. Jünger et G. Reinelt, « Facets of the linear ordering polytope », Mathematical Programming, vol. 33,‎ , p. 43-60 (DOI 10.1007/BF01582010, Math Reviews 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 » (no 2081), (DOI 10.1007/3-540-45535-3_26, Math Reviews 2041937, lire en ligne), p. 333-347.

Voir aussi[modifier | modifier le code]

Articles connexes[modifier | modifier le code]

Liens externes[modifier | modifier le code]