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


Une réflexion au sujet de « C comme chaîne et chemin »

  1. Ping : A comme accessibilité | groupe fmr (flux, matrices, réseaux)

Laisser un commentaire

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