C comme cycle

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 non orienté, un cycle est une chaîne partant d’un sommet i et parvenant à ce même sommet. Si le graphe est orienté, on parle plutôt de circuit. Un cycle (ou un circuit) est dit élémentaire s’il ne passe pas deux fois par le même sommet. On peut considérer une boucle – lien d’un sommet vers lui-même – comme un cycle de longueur 1. S’il n’existe aucun cycle dans un graphe, nous sommes soit en présence d’un graphe vide (absence de liens entre les sommets), soit en présence d’un arbre (ou d’une forêt).

La théorie des graphes a permis de mettre en évidence des cycles spécifiques et notamment les deux suivants :

  • le cycle hamiltonien qui passe une fois et une seule par tous les sommets ;
  • le cycle eulérien qui passe exactement une fois par chaque arête.

Sur la figure ci-dessous, on a de gauche à droite une forêt (aucun cycle), un cycle hamiltonien (en rouge) et enfin un cycle eulérien (en rouge).

cycle

Les cycles ont des applications nombreuses, notamment en logistique. En géographie des transports, l’indice alpha proposé par Kansky (1963 – voir ce billet récent) est le ratio entre le nombre de cycles présents et le nombre de cycles possibles : variant entre 0 (arbre) et 1 (graphe complet), il donne une première information concernant la connectivité globale du réseau étudié.

Billets liés : A comme arbre, C comme chaîne et chemin, C comme connexité / C comme connectivité

Laisser un commentaire

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