Point d'articulation (théorie des graphes)

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.

Cet article concerne le point d'articulation en mathématiques. Pour le point d'articulation en phonétique, voir Point d'articulation.

Les composantes biconnexes d'un graphe. Chaque composante est dans une couleur différente. Les points d'articulation portent plusieurs couleurs.

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.

Recherche de points d'articulation

Soit G un graphe à n sommets et m arêtes. Un algorithme trivial de complexité d'ordre O(nm) est le suivant :

a = nombre de composantes connexes de G (déterminé à l'aide de l'algorithme de parcours en profondeur ou de l'algorithme de parcours en largeur)
pour chaque sommet v de V ayant des arêtes incidentes
retirer v de V
b = nombre de composantes connexes de G une fois v éliminé
si b > a
v est un point d'articulation de G
remettre en place v

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].

Notes et références
  1. Luc Maranget, « Parcours en profondeur, biconnexité »(Archive.org • Wikiwix • Archive.is • Google • Que faire ?)
  2. DOI:10.1145/362248.362272
  3. Jeffery Westbrook et Robert Endre Tarjan, « Maintaining Bridge-Connected and Biconnected Components On-Line », Algorithmica, vol. 7, nos 5-6,‎ , p. 433-464

Article connexe
  • Portail des mathématiques
  • Portail de l'informatique théorique
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.