C comme connexité / C comme connectivité

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).

Un graphe est dit connexe lorsque pour toute paire de sommets, il existe une suite de liens permettant de relier ces deux sommets. Lorsque le graphe est orienté, on distingue entre la connexité faible (il existe une chaîne entre toute paire de sommets) et la connexité forte (il existe un chemin entre toute paire de sommets).

Un graphe non connexe se compose de plusieurs composantes connexes non reliées entre elles. Sur la figure ci-dessous, on a de gauche à droite un graphe connexe, un graphe fortement connexe et un graphe formé de deux composantes connexes, l’une de 3 sommets, l’autre de 1 sommet – on parlera plutôt d’isolé (isolate) dans ce dernier cas.

La connexité ne doit pas être confondue avec la connectivité, mesure souvent utilisée en géographie, qui s’intéresse à la densité des connexions au sein d’un réseau et surtout à l’existence d’itinéraires alternatifs entre deux mêmes sommets. Ainsi, en cas d’accident, de travaux, etc., le trafic pourra être plus facilement détourné dans un réseau fortement connecté. Si les sociologues s’intéressent souvent à la non redondance des relations entre personnes (voir les travaux sur les liens faibles ou les trous structuraux), les géographes des transports recherchent au contraire la redondance des relations entre lieux : plus elle est élevée et moins les réseaux seront vulnérables.

Billets liés : C comme chaîne et chemin, C comme cycle

Retour au glossaire

Laurent Beauguitte

More Posts

Follow Me: