Ressources numériques en sciences humaines et sociales OpenEdition Nos plateformes OpenEdition Books OpenEdition Journals Hypothèses Calenda Bibliothèques OpenEdition Freemium Suivez-nous

C comme chaîne et chemin

Ces billets visent à définir le plus clairement et le plus précisément possible des termes clés en analyse de réseau. Ils s’adressent à un public débutant et évitent autant que possible toute formalisation mathématique (pour cette dernière, voir les synthèses fmr sur Hal-Shs).

Dans un graphe, une chaîne (walk) reliant  deux sommets x et y est définie par une suite finie de liens consécutifs reliant x à y, ces liens n’étant pas nécessairement orientés dans le même sens. Un chemin est une chaîne dont tous les liens sont orientés dans le même sens.

Une chaîne ou un chemin sont dits simples quand ils ne passent pas deux fois par le même lien et tous les liens sont donc distincts – en anglais, on parle de trail. Une chaîne ou un chemin sont dits élémentaires quand ils ne passent pas deux fois par le même sommet et tous les sommets sont donc distincts – path en anglais. Une chaîne ayant le même point de départ et d’origine est appelé un cycle (voir C comme cycle). Un chemin ayant le même point de départ et d’origine est appelé un circuit.

La longueur d’une chaîne ou d’un chemin (path lenght)  se mesure en nombre de liens nécessaires pour relier deux sommets. Si cette chaîne ou ce chemin est la plus courte possible entre deux sommets (shortest path), sa longueur est nommée distance géodésique (geodesic distance, voir D comme distance). Dans le graphe non  orienté ci-dessous, il existe de multiples chaînes permettant de relier les sommets x et y : on peut citer par exemple les suites de liens {1,6} {2,3,6} {2,4,7,12}. La chaîne la plus courte {1,6} est de longueur 2 : la distance géodésique entre x et y est donc égale à 2.

Chaînes dans un graphe

Un chemin permettant d’inclure une fois et une seule tous les sommets d’un graphe est appelé un chemin hamiltonien (Hamiltonian path). Quand un chemin permet d’inclure une fois et une seule tous les liens d’un graphe, il est appelé un chemin eulérien (Eulerian path).

Les notions de chaîne et de chemin sont notamment utilisées pour mesurer la centralité des sommets, le diamètre du graphe, sa connexité et sa robustesse.

Billets liés : C comme cycle, D comme distance

Retour au glossaire


OpenEdition vous propose de citer ce billet de la manière suivante :
Laurent Beauguitte (20 avril 2013). C comme chaîne et chemin. groupe fmr (flux, matrices, réseaux). Consulté le 16 février 2025 à l’adresse https://doi.org/10.58079/p824


Vous aimerez aussi...

1 réponse

  1. 24/06/2013

    […] d’accessibilité dans un graphe est fortement liée aux notions de plus court chemin (voir C comme chaîne et chemin) et de centralité, notamment à l’indice de Shimbel et ses dérivés (voir C comme […]

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *

Ce site utilise Akismet pour réduire les indésirables. En savoir plus sur comment les données de vos commentaires sont utilisées.