AlgèbreNotion · Glossaire
Boucle
Dans la théorie des graphes, une boucle est une arête dont les deux extrémités coïncident, c'est-à-dire une arête reliant un sommet à lui-même. Un graphe sans boucles et sans arêtes multiples est dit simple. En algèbre, une boucle est une structure algébrique (Q, .) munie d'une loi de composition dans laquelle les équations a · x = b et y · a = b ont une unique solution, et qui possède un élément neutre. Les boucles généralisent les groupes en abandonnant l'associativité.
Sommaire
Ce que vous allez apprendre
- Reconnaître une boucle à partir des extrémités d'une arête.
- Déterminer pourquoi un graphe contenant une boucle n'est pas simple.
- Identifier les axiomes d'une boucle algébrique et le rôle de l'associativité.
En clair
Dessinez un point, puis une arête qui part de ce point et y revient : cette arête forme une boucle. Ses deux extrémités touchent le même sommet, même si le trait s'écarte pour rendre le retour visible.
En algèbre, le mot change de sens. Imaginez une table d'opération semblable à une table de multiplication. Dès que l'on fixe un opérande et le résultat visé, l'autre opérande est déterminé de façon unique. Un élément neutre laisse aussi chaque élément inchangé.
Définition
En théorie des graphes, une boucle est une arête incidente deux fois au même sommet : ses deux extrémités coïncident. Cette propriété dépend des extrémités de l'arête, non de la forme courbe ou droite choisie pour la dessiner. Selon la définition retenue ici, un graphe simple ne possède ni boucle ni arêtes multiples.
En algèbre, on considère un ensemble Q muni d'une loi de composition, notée par un point. Pour tous les éléments a et b de Q, l'inconnue x placée à droite de a et l'inconnue y placée à gauche de a existent chacune de manière unique :
La structure possède aussi un élément neutre e, qui laisse tout élément q de Q inchangé des deux côtés :
L'associativité n'est pas exigée : les résultats de (a · b) · c et de a · (b · c) peuvent donc différer. Tout groupe satisfait les conditions d'une boucle, tandis qu'une boucle ne devient un groupe que si sa loi est associative. Les deux sens du mot appartiennent à des cadres distincts.
Un exemple, pas à pas
Considérons un graphe dont les sommets sont A, B et C. Il possède trois arêtes : e1 relie A à A, e2 relie A à B et e3 relie B à C. La figure rend ces trois données visibles sans changer leurs extrémités.
1. On examine les deux extrémités de e1 : elles valent A et A. Elles coïncident, donc e1 est une boucle.
2. Les extrémités de e2 sont A et B, puis celles de e3 sont B et C. Elles sont différentes dans les deux cas : ces arêtes ne sont pas des boucles.
3. Aucune paire de sommets n'est reliée par plusieurs arêtes, mais la présence de e1 suffit à conclure que ce graphe n'est pas simple.
Le contrôle se refait en notant les extrémités : (A, A), (A, B) et (B, C). Une seule paire répète le même sommet ; le graphe possède donc exactement une boucle.
En pratique
Pour repérer une boucle dans un graphe, lisez les extrémités de chaque arête. Si elles portent le même sommet, l'arête est une boucle ; la courbure du dessin n'est qu'un choix graphique.
Pour décider si le graphe est simple au sens de cette fiche, cherchez d'abord une boucle, puis deux arêtes distinctes ayant les mêmes extrémités. L'un ou l'autre constat écarte l'appellation « graphe simple ».
Pour tester une structure algébrique candidate, vérifiez l'unicité des deux divisions, à gauche et à droite, puis l'existence d'un même élément neutre des deux côtés. Testez séparément l'associativité : elle n'est pas fournie par la définition d'une boucle.
À ne pas confondre
Boucle et cycle. Une boucle se reconnaît sur une seule arête dont les extrémités coïncident. Un cycle décrit un parcours fermé. Selon les conventions, une boucle peut être admise ou non comme cycle de longueur 1 ; il faut donc vérifier la définition de « cycle » utilisée.
Boucle et arêtes multiples. Une boucle utilise deux fois le même sommet comme extrémité. Des arêtes multiples sont plusieurs arêtes distinctes partageant les mêmes extrémités. Deux arêtes reliant A à B sont multiples, même si aucune n'est une boucle.
Boucle de graphe et boucle algébrique. La première est une arête ; la seconde est un ensemble muni d'une opération. La présence de sommets indique le sens graphique, tandis que des équations à résoudre dans Q indiquent le sens algébrique.
Limites et pièges
Graphe annoncé simple. Dans le cadre de cette fiche, une boucle observée contredit immédiatement cette qualification. Il faut soit retirer la boucle du modèle, soit travailler avec un graphe qui n'est pas simple.
Degré d'un sommet. Dans un graphe non orienté, lorsqu'on compte les incidences, une boucle touche deux fois son sommet et contribue donc pour 2 à son degré. Compter seulement le trait visible ferait perdre une incidence.
Parenthèses en algèbre. Sans associativité, une expression à trois facteurs est ambiguë si elle n'est pas parenthésée. Il faut conserver explicitement (a · b) · c ou a · (b · c), sans passer de l'une à l'autre.
Solutions uniques, mais pas groupe automatique. Pouvoir résoudre de façon unique a · x = b et y · a = b, avec un neutre, ne prouve pas l'associativité. Cette propriété doit être vérifiée séparément avant de conclure que la boucle est un groupe.
Pour aller plus loin
Le glossaire Sous-graphe prolonge le versant graphique en montrant comment sélectionner des sommets et des arêtes au sein d'un graphe.
La fiche Loi de composition interne précise le cadre algébrique dans lequel l'opération d'une boucle combine deux éléments d'un même ensemble.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres