Isthme (théorie des graphes)

En théorie des graphes, un isthme ou un pont est une arête d'un graphe dont l'élimination induit un graphe avec plus de composantes connexes que le graphe initial. De façon équivalente, une arête est un isthme si et seulement si elle n'est pas contenue dans un cycle.

Un graphe avec six isthmes (marqués en rouge).

Arbres et forêts

Un graphe avec $n$ sommets peut contenir au plus $n-1$ isthmes, puisque l'ajout d'une arête supplémentaire formerait un cycle.

Article connexe

• Point d'articulation