Isthme

Imaginez deux groupes de villes. Dans chaque groupe, plusieurs routes forment une boucle, mais une seule route relie les deux groupes. Si cette liaison disparaît, il devient impossible de passer d'un côté à l'autre : cette arête est un isthme, aussi appelé pont.

Une arête placée sur un cycle n'est pas un isthme, car le reste du cycle offre un autre trajet entre ses extrémités. L'isthme révèle donc un point de fragilité du réseau.

Considérons un graphe non orienté connexe, c'est-à-dire un ensemble de sommets reliés par des arêtes dans lequel tout sommet est accessible depuis tout autre. Une arête est un isthme, ou pont, lorsque sa suppression augmente le nombre de composantes connexes. Dans le cadre connexe de la définition, le graphe restant possède alors exactement deux composantes connexes.

Notons G le graphe et e l'arête étudiée. Le critère fondamental est :

En effet, si e appartient à un cycle, les autres arêtes de ce cycle relient encore ses extrémités après sa suppression. En l'absence de cycle contenant e, aucun trajet de remplacement n'existe. Un graphe connexe dépourvu d'isthme est dit 2-arête-connexe. L'algorithme de Tarjan repère tous les isthmes en temps linéaire par rapport au nombre de sommets et d'arêtes.

Étudions un réseau formé de deux triangles reliés par une seule arête. Le schéma matérialise les deux cycles et la liaison à tester.

Données.
Sommets : A, B, C, D, E et F.
Premier cycle : A–B–C–A.
Second cycle : D–E–F–D.
Unique liaison entre les deux cycles : l'arête C–D.

Étape 1. Supprimons C–D. Les sommets A, B et C restent reliés entre eux, tout comme D, E et F, mais aucun chemin ne relie plus les deux groupes. Le graphe se sépare en deux composantes connexes.

Étape 2. Vérifions le critère des cycles. C–D n'appartient à aucun cycle : partir de C vers D ne laisse aucun autre chemin permettant de revenir à C. L'arête C–D est donc un isthme.

Contrôle. Supprimer A–B ne coupe pas le graphe, car A–C–B reste disponible. Le même raisonnement vaut pour chaque arête des deux triangles. C–D est bien l'unique isthme du réseau.

Dans un réseau de transport, rechercher les isthmes met en évidence les liaisons dont la fermeture séparerait des zones encore connectées en interne. Si plusieurs itinéraires forment un cycle, la liaison étudiée dispose au contraire d'un détour.

Dans un réseau de communication, le même test signale une connexion critique : sa disparition suffit à interrompre les échanges entre deux parties du réseau. Renforcer en priorité une telle liaison réduit cette fragilité structurelle.

Sur un petit graphe, on peut chercher visuellement si chaque arête appartient à un cycle. Sur un graphe volumineux, l'algorithme de Tarjan est préférable à la suppression successive de chaque arête, car il trouve tous les isthmes en un parcours de temps linéaire.

Isthme et sommet d'articulation. Un isthme est une arête dont on teste la suppression ; un sommet d'articulation est un sommet dont on teste le retrait avec ses arêtes incidentes. Dans l'exemple, supprimer l'arête C–D coupe le réseau : le diagnostic porte bien sur un isthme.

Pont et chemin. Le pont est une seule arête critique, tandis qu'un chemin est une suite d'arêtes. Dans l'exemple, C–D est le pont ; A–C–D–F est un chemin qui l'emprunte.

Le cadre connexe compte. La formulation « deux composantes » suppose que le graphe initial est connexe. Dans un graphe déjà déconnecté, un isthme se définit plus généralement comme une arête dont la suppression augmente d'une unité le nombre total de composantes connexes.

Une arête isolée visuellement n'est pas forcément un isthme. Il suffit d'un autre chemin, même long, entre ses extrémités pour qu'elle appartienne à un cycle. Il faut rechercher ce trajet de remplacement avant de conclure.

Dans un arbre, toutes les arêtes sont des isthmes. Un arbre connexe ne contient aucun cycle. Supprimer n'importe laquelle de ses arêtes sépare donc l'arbre en exactement deux composantes.

Les arêtes parallèles demandent une convention claire. Dans un multigraphe, deux arêtes reliant les mêmes sommets se remplacent mutuellement : en supprimer une ne déconnecte pas le graphe. Une implémentation doit distinguer ces arêtes au lieu de les confondre avec une seule liaison.

La fiche graphe connexe précise la propriété de connexion que la suppression d'un isthme fait disparaître.