Loading AI tools
De Wikipédia, l'encyclopédie libre
Cet article concerne le point d'articulation en mathématiques. Pour le point d'articulation en phonétique, voir Point d'articulation.
En mathématiques, et en particulier en théorie des graphes, un point d'articulation est un sommet d'un graphe non orienté qui, si on le retire du graphe, augmente le nombre de composantes connexes. Si le graphe était connexe avant de retirer ce sommet, il devient donc non connexe.
Un graphe est dit biconnexe s'il ne contient pas de points d'articulation. Un graphe qui contient des points d'articulation peut être décomposé en composantes biconnexes en démultipliant les points d'articulation. Cela revient à dire que deux arêtes quelconques d'une composante biconnexe appartiennent à un cycle[1].
Dans un arbre, tous les sommets de degré strictement supérieur à 1 sont des points d'articulation.
La notion équivalente aux points d'articulation pour les arêtes est celle d'isthme.
Soit G un graphe à n sommets et m arêtes. Un algorithme trivial de complexité d'ordre O(nm) est le suivant :
Cet algorithme est naïf, il en existe de bien meilleurs. John Hopcroft et Robert Tarjan en ont décrit un en 1973 de complexité d'ordre O(n+m) et qui utilise l'algorithme de parcours en profondeur[2]. Le problème a aussi été étudié du point de vue des algorithmes online[3].
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
