Chaîne (théorie des graphes)
Pour les articles homonymes, voir Chaîne.
Cet article est une ébauche concernant les mathématiques.
Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.
Consultez la liste des tâches à accomplir en page de discussion.
Dans un graphe non orienté, une chaîne reliant à , notée [1], est définie par une suite finie d'arêtes consécutives, reliant à .
La notion correspondante dans les graphes orientés est celle de chemin.
Vocabulaire
[modifier | modifier le code]Une chaîne élémentaire est une chaîne ne passant pas deux fois par un même sommet, c'est-à-dire dont tous les sommets sont distincts.
Une chaîne simple est une chaîne ne passant pas deux fois par une même arête, c'est-à-dire dont toutes les arêtes sont distinctes.
Un cycle est une chaîne simple dont les deux extrémités sont identiques.
Dans le cas des graphes non pondérés, longueur et poids d'une chaîne sont deux notions identiques car on attribue à toutes les arêtes le même poids, 1. Cependant dans le cas d'un graphe pondéré, les poids des arêtes peuvent différer, on veillera donc à distinguer une chaîne de poids minimal d'une chaîne la moins longue, par exemple.
La longueur d'une chaine est définie par le nombre d'arêtes qui la composent.
Références
[modifier | modifier le code]- Lucas Létocart, « Algorithmique de graphes » [PDF]
