Entrelacs et graphes
![Si ce bandeau n'est plus pertinent, retirez-le. Cliquez ici pour en savoir plus.](http://upload.wikimedia.org/wikipedia/commons/thumb/3/38/Info_Simple.svg/12px-Info_Simple.svg.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/a/a1/2017-fr.wp-orange-source.svg/45px-2017-fr.wp-orange-source.svg.png)
Cet article ne cite pas suffisamment ses sources ().
Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références ».
En pratique : Quelles sources sont attendues ? Comment ajouter mes sources ?
![Si ce bandeau n'est plus pertinent, retirez-le. Cliquez ici pour en savoir plus.](http://upload.wikimedia.org/wikipedia/commons/thumb/3/38/Info_Simple.svg/12px-Info_Simple.svg.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/b/b2/Circle-icons-recycle.svg/45px-Circle-icons-recycle.svg.png)
Cet article concernant les mathématiques doit être recyclé ().
Une réorganisation et une clarification du contenu paraissent nécessaires. Améliorez-le, discutez des points à améliorer ou précisez les sections à recycler en utilisant {{section à recycler}}.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/7/7c/Trefle.jpg/220px-Trefle.jpg)
La théorie des nœuds et la théorie des graphes ont des rapports entre elles. Un entrelacs d'apparence compliquée peut être codé par un graphe planaire.
Diagramme d'un nœud ou d'un entrelacs
![](http://upload.wikimedia.org/wikipedia/commons/thumb/2/28/KnotsBagTable.svg/350px-KnotsBagTable.svg.png)
Un nœud ou entrelacs dans l'espace peut être projeté sur le plan euclidien ; on obtient un diagramme de ce nœud ou entrelacs si 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 doivent être distinctes. Enfin on doit indiquer quel brin est dessus et lequel est dessous en interrompant le tracé ou par un codage. 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
![](http://upload.wikimedia.org/wikipedia/commons/thumb/1/1d/KnotCheckerboard.svg/150px-KnotCheckerboard.svg.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/b/ba/KnotSignedGraph.svg/150px-KnotSignedGraph.svg.png)
![](http://upload.wikimedia.org/wikipedia/commons/4/4d/KnotSignedEdge%2B.png)
![](http://upload.wikimedia.org/wikipedia/commons/7/76/KnotSignedEdge-.png)
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 diagramme 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 [1].
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.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/8/82/KnotGraphTable.svg/350px-KnotGraphTable.svg.png)
Passage inverse, du graphe à l'entrelacs
L'animation ci-dessous montre comment procéder pour passer du graphe à l'entrelacs.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/7/71/KnotStepByStep.gif/300px-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.](http://upload.wikimedia.org/wikipedia/commons/c/c9/Frise.jpg)
Mouvements de Reidemeister
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.
- Type I : suppression/ajout d'une boucle ou d'une arête libre
- Type II : suppression/ajout d'une arête double de signes contraires
- Type III (et son image miroir)
Comme 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.
Voir aussi
- Code de Gauss d'un entrelacs.
- Enlacement de deux courbes.
Notes et références
- Alexeï Sossinsky, Nœuds, Paris, Seuil, , p. 59 à 70
- (en) Peter Cromwell, Knots And Links, Cambridge University Press, , p. 51 à 56
- (en) Bela Bollobas, Modern Graph Theory, Springer, , p. 368 à 370
- ↑ (en) Colin C. Adams, The Knot Book, American Mathematical Society, 1994, 2001, 2004 (lire en ligne), p. 51 - 55
Liens externes
Sur les autres projets Wikimedia :
- Knot theory, sur Wikimedia Commons
- Category:Knots in art and decoration, sur Wikimedia Commons
- (fr + en + de) Tutoriel sur les entrelacs
- (en) « Biquasiles and Dual Graph Diagrams »
- Page mathcurve sur le sujet
- Des beaux entrelacs sur Images des maths
- [vidéo] VideoDiMath, Dessiner de beaux entrelacs (Christian Mercat) sur YouTube, (consulté le )
Portail de la géométrie