Échelle de Möbius

De testwiki
Aller à la navigation Aller à la recherche

Modèle:Infobox Graphe Dans la théorie des graphes, une branche des mathématiques, l'échelle de Möbius MLn 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 ML3[1], MLn possède exactement n cycles à 4 sommets[2] 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[3].

Propriétés

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

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 Modèle:Lien. Il est possible de le dessiner sur un plan avec un seul croisement et ce nombre est minimal. Il peut être plongé 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[4].

Les échelles de Möbius sont sommet-transitives mais ne sont pas arête-transitives (sauf ML3) : 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[5].

L'échelle de Möbius ML4 possède 392 arbres couvrants. Elle et ML3 ont le plus d'arbres couvrants parmi tous les graphes cubiques ayant le même nombre de sommets[6]Modèle:,[7]. 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[8].

Mineurs du graphe

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

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 Modèle:Lien pour combiner des graphes planaires et l'échelle de Möbius ML4. Pour cette raison, ML4 est appelé le graphe de Wagner[9].

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[10].

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[11].

Applications

D. Walba et ses collègues ont synthétisé les premiers des structures moléculaires en forme d'échelle de Möbius[12], et depuis cette structure a été objet d'intérêt en chimie et en stéréochimie[13], et en particulier en relation avec la forme en échelle des molécules d'ADN. En gardant cette application à l'esprit, Erica Flapan étudie[14] les symétries mathématiques des plongements des échelles de Möbius dans ℝ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[15]Modèle:,[16].

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[17]Modèle:,[18]Modèle:,[19]Modèle:,[20]Modèle:,[21].

Notes et références

Modèle:Traduction/Référence Modèle:Références

Voir aussi

Articles connexes

Liens externes

Modèle:Portail

  1. ↑ ML3 est le graphe biparti complet K3,3
  2. ↑ Modèle:Article
  3. ↑ Modèle:Article
  4. ↑ Modèle:Article
  5. ↑ Modèle:Article
  6. ↑ Modèle:Article
  7. ↑ Modèle:Article
  8. ↑ Modèle:Article.
  9. ↑ Modèle:Article
  10. ↑ Modèle:Article
  11. ↑ Modèle:Article
  12. ↑ Modèle:Article.
  13. ↑ Modèle:Chapitre.
  14. ↑ Modèle:Article.
  15. ↑ Modèle:Article.
  16. ↑ Modèle:Article.
  17. ↑ Modèle:Article.
  18. ↑ Modèle:Article.
  19. ↑ Modèle:Article.
  20. ↑ Modèle:Article.
  21. ↑ Modèle:Chapitre.
Récupérée de "https://fr.wiki.beta.math.wmflabs.org/w/index.php?title=Échelle_de_Möbius&oldid=13666"