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 sommets peut contenir au plus isthmes, puisque l'ajout d'une arĂȘte supplĂ©mentaire formerait un cycle.
Article connexe
Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplĂ©mentaires peuvent sâappliquer aux fichiers multimĂ©dias.