Chaîne (graphe)
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.
|
Dans un graphe non orienté, une chaîne reliant 
à 
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.
[modifier] Vocabulaire
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 un chemin dont les deux extrémités sont identiques.
La longueur d'une chaîne est le nombre d'arêtes du chemin, ou bien, dans le cas d'un graphe pondéré, la somme des poids des arêtes. Dans ce dernier cas, on veillera à distinguer une plus courte chaîne (i.e. de poids minimal) d'une chaîne la moins longue (i.e. ayant un nombre minimum d'arêtes).
