Entrelacs et graphes

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Le triangle est associé au nœud de trèfle.

La théorie des nœuds et la théorie des graphes ont des rapports entre elles. Un entrelacs a l'air très compliqué mais peut être codé par la structure simple de graphe planaire : des points (nommés sommets) reliés par des traits (nommés arêtes).

Diagramme de nœud[modifier | modifier le code]

Diagrammes des nœuds premiers jusqu'à 7 croisements.

Un nœud ou entrelacs dans l'espace R3 peut être projeté sur le plan euclidien R2.

Cette projection est génériquement régulière, c'est-à-dire injective presque partout, à l'exception d'un nombre fini de points de croisements simples, où la projection envoie seulement 2 points de l'entrelacs sur le même point. De plus, les directions des brins à ces deux points ne sont pas colinéaires si bien que les brins projetés pointent dans deux directions différentes du plan. Dans ces conditions, on indique quel brin est dessus et quel brin est dessous en interrompant le tracé. Un tel diagramme caractérise la classe d'isotopie de l'entrelacs.

En termes de théorie des graphes, un diagramme de nœud ou d'entrelacs est simplement un graphe planaire dont tous les sommets sont de degré 4, ces sommets étant labellisés par l'information des dessus-dessous.

Graphe associé à un nœud ou un entrelacs[modifier | modifier le code]

KnotCheckerboard.svg
L'entrelacs précédent, avec son graphe planaire à arêtes étiquetées associé.
Arête étiquetée +
Arête étiquetée -

Une construction associée à un diagramme d'entrelacs facilite la manipulation de celui-ci. En effet, la projection précédente décompose le plan en plusieurs composantes connexes : le graphe lui-même, de dimension 1, et une zone non bornée et des composantes homéomorphes à des disques, de dimension 2. On peut alors attacher une couleur grise ou blanche à chacune de ces zones de la manière suivante : colorez en gris la zone non bornée et, pour chaque croisement, colorez en gris la zone opposée au croisement. Le théorème de Jordan permet d'affirmer que ce processus est bien défini.

Définissez ensuite un graphe planaire dont les sommets sont au "centre" de chaque zone blanche, et dont les arêtes passent par chaque croisement, entre les deux brins de l'entrelacs. L'information du dessus-dessous est codée par un signe + ou - étiquetant chaque arête. L'arête est étiquetée + si le brin venant de la gauche passe au-dessus, et étiquetée - sinon. On peut représenter ce signe par la convention d'un trait plein pour un signe + et d'un trait en pointillé pour le signe -. Il y a un choix global des signes, un changement de ce choix correspond à la réflexion dans un miroir. Lorsque le nœud ou l'entrelacs est alterné (alternance des passages dessus-dessous), toutes les arêtes ont le même signe.

Le diagramme de nœud est alors le graphe médial du graphe que nous venons de définir.

Table des nœuds premiers jusqu'à sept croisements, représentés par des diagrammes alternés. En vert, le graphe associé dont le diagramme de nœud est le graphe médial.

Passage inverse, du graphe à l'entrelacs[modifier | modifier le code]

L'animation ci-dessous montre comment procéder pour passer du graphe à l'entrelacs.

KnotStepByStep.gif

Cette correspondance entre diagrammes d'entrelacs et graphes plantaires permet de dessiner de beaux entrelacs, pour les coder d'une manière plus aisée à manipuler, ou pour les déformer, les comparer ou les mémoriser.

Du graphe à l'entrelacs.

Mouvements de Reidemeister[modifier | modifier le code]

Les mouvements de Reidemeister sont des modifications locales du diagramme d'entrelacs qui préservent la classe d'isotopie et permettent de passer de n'importe quel diagramme à n'importe quel autre. Ces mouvements se transcrivent sur le graphe associé comme indiqué dans les figures ci-dessous : et, de même que pour les diagrammes, deux graphes planaires à arêtes signées sont associés au même entrelacs si et seulement si on peut passer de l'un à l'autre par une série de mouvements de Reidemeister.

Notes et références[modifier | modifier le code]

  • Alexei Sossinsky, Nœuds, Paris, Seuil, , p. 59 à 70
  • (en) Peter Cromwell, Knots And Links, Cambridge University Press, , p. 51 à 56
  • (en) Colin C. Adams, The Knot Book, Springer, , p. 368 à 370
  • (en) Bela Bollobas, Modern Graph Theory, American Mathematical Society, 1994, 2001, p. 51 à 55

Liens externes[modifier | modifier le code]

Sur les autres projets Wikimedia :