Isthme (théorie des graphes)

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Pour les articles homonymes, voir Isthme.
Un graphe avec six isthmes (marqués en rouge).

Un isthme ou un pont est, en théorie des graphes, 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 contenu dans un cycle.


Arbres et forêts[modifier | modifier le code]

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[modifier | modifier le code]