Détecteur de Points d'Articulation

Pseudocode

Un seul parcours en profondeur et deux nombres par sommet. La date de découverte indique quand le sommet a été vu pour la première fois; le low-link indique le sommet le plus ancien que son sous-arbre peut atteindre par une arête arrière.

dfs(u, parent):
    dec[u] = low[u] = ++temps
    enfants = 0

    pour chaque voisin v de u:
        si v == parent: continuer
        si v deja visite:
            low[u] = min(low[u], dec[v])   // arete arriere
        sinon:
            enfants++
            dfs(v, u)
            low[u] = min(low[u], low[v])
            si parent != AUCUN et low[v] >= dec[u]:
                marquer u comme point d articulation

    si parent == AUCUN et enfants > 1:
        marquer u comme point d articulation   // regle racine

La condition low[v] >= dec[u] signifie que le sous-arbre enraciné au fils v ne possède aucune arête arrière remontant au-dessus de u. Toute sortie de ce sous-arbre passe donc par u, et supprimer u l'isole. La racine est un cas à part car elle n'a pas de parent dont elle pourrait être coupée: la racine est un point d'articulation exactement lorsqu'elle a deux fils ou plus dans le DFS, puisque ces sous-arbres ne peuvent s'atteindre entre eux qu'à travers elle.

Exemple détaillé, étape par étape

Exécute le DFS depuis A sur un graphe formé d'un triangle prolongé par une queue de deux sommets, en prenant les voisins par ordre alphabétique.

Graphe d'exemple: Arêtes non orientées A-B, B-C et C-A formant un triangle, plus C-D et D-E en prolongement.

1. Descendre jusqu à E. Les dates de découverte et les low-link sont attribués à la descente: A reçoit 1, B reçoit 2, C reçoit 3, D reçoit 4 et E reçoit 5. E est une feuille dont l'unique voisin est son parent D, donc low[E] reste à 5.
2. Revenir à D. low[D] = min(4, low[E] = 5) = 4. Teste le fils: low[E] = 5 >= dec[D] = 4, donc rien sous E ne remonte au-dessus de D. D est un point d'articulation, et de fait retirer D isole E.
3. Revenir à C. C possède en outre l'arête arrière C-A, qui fixe low[C] = min(3, dec[A] = 1) = 1. En intégrant le fils, low[C] = min(1, low[D] = 4) = 1. Teste le fils D: low[D] = 4 >= dec[C] = 3, donc C est un point d'articulation. Retirer C sépare la queue D-E du triangle.
4. Revenir à B. low[B] = min(2, low[C] = 1) = 1. Teste le fils C: low[C] = 1 >= dec[B] = 2 est faux, car C peut remonter jusqu'à A sans passer par B. B n'est donc pas un point d'articulation, ce qui est exact: le triangle maintient A et C connectés sans lui.
5. Terminer à la racine. A est la racine du DFS. Elle a exactement un fils DFS, B, puisque C a été atteint via B et non directement. Un seul fils signifie que la règle de la racine ne se déclenche pas, A n'est donc pas un point d'articulation.

Les points d'articulation sont C et D. Le triangle A-B-C n'en fournit aucun parmi A et B car tout sommet d'un cycle dispose d'une route alternative, tandis que dans la queue C-D-E chaque sommet interne est critique. Ce contraste est l'intuition centrale: les points d'articulation vivent sur les chaînes, pas à l'intérieur des cycles.

Complexité et son origine

Temps: O(V + E) · Espace: O(V)

Il s'agit d'un unique parcours en profondeur avec un travail supplémentaire constant par arête, le coût est donc celui du parcours lui-même. Chaque sommet est visité une fois et chaque arête examinée deux fois, une depuis chaque extrémité. L'état supplémentaire tient en deux entiers par sommet, la date de découverte et le low-link, plus la pile de récursion, le tout en O(V). L'approche naïve, retirer chaque sommet à tour de rôle et tester la connexité, coûte O(V fois (V + E)); la méthode du low-link transforme donc une vérification quadratique en une vérification linéaire en une seule passe. Sur un graphe de 10 000 sommets et 30 000 arêtes, l'écart atteint environ quatre ordres de grandeur.

Quand utiliser Points d'Articulation, et quand l'éviter

Points d'articulation, ponts et composantes biconnexes découlent tous du même DFS. Le choix dépend de la nature de l'élément fragile: sommet ou arête.

Pièges fréquents

• Appliquer la règle des non-racines à la racine. La racine n'a pas de parent, le test low[v] >= dec[u] y est donc dénué de sens et la marquera généralement à tort. La racine exige sa propre règle: elle est point d'articulation exactement lorsqu'elle possède deux fils DFS ou plus.
• Utiliser low[v] au lieu de dec[v] sur une arête arrière. Lorsque tu rencontres un sommet v déjà visité, mets à jour avec dec[v], pas avec low[v]. Utiliser low[v] peut propager une valeur venue d'un autre sous-arbre et produire des low-link trop faibles, masquant de véritables points d'articulation.
• Confondre le test du fils avec celui des ponts. Les points d'articulation utilisent low[v] >= dec[u]; les ponts utilisent low[v] > dec[u], strictement supérieur. Ce seul caractère de différence sépare « tout doit passer par ce sommet » de « tout doit passer par cette arête ».
• Sauter le parent par identité plutôt que par arête. Comparer uniquement l'identifiant du parent échoue sur les multigraphes. Si deux arêtes parallèles relient u et v, la seconde constitue une véritable route alternative et ne doit pas être sautée. Mémorise l'arête empruntée à l'arrivée, pas seulement le sommet.
• Oublier les composantes déconnectées. Un seul DFS ne couvre qu'une composante. Parcours tous les sommets et lance un nouveau DFS depuis chacun de ceux non visités, en réinitialisant la règle de la racine pour chaque nouvelle racine.

Questions fréquentes

Qu'est-ce qu'un point d'articulation dans un graphe?

Un point d'articulation, aussi appelé sommet de coupe, est un sommet dont le retrait augmente le nombre de composantes connexes. Concrètement, c'est un point unique de défaillance: toute route entre une certaine paire de sommets passe par lui, si bien que le supprimer scinde le graphe.

Comment trouve-t-on les points d'articulation?

Exécute un unique DFS en enregistrant pour chaque sommet sa date de découverte et son low-link, c'est-à-dire la plus petite date de découverte atteignable depuis son sous-arbre via au plus une arête arrière. Un sommet u qui n'est pas la racine est un point d'articulation si un fils DFS v vérifie low[v] >= dec[u]. La racine en est un si elle possède deux fils DFS ou plus. L'ensemble tient en O(V + E).

Quelle est la différence entre un point d'articulation et un pont?

Un point d'articulation est un sommet dont le retrait déconnecte le graphe; un pont est une arête qui produit le même effet. Les deux découlent du même DFS et diffèrent par une comparaison: low[v] >= dec[u] pour les points d'articulation et le strict low[v] > dec[u] pour les ponts. Un graphe peut posséder des ponts sans point d'articulation, et l'inverse.

Pourquoi la racine du DFS est-elle un cas particulier?

Parce que le test général demande si un sous-arbre fils peut atteindre quelque chose au-dessus du sommet courant, et qu'au-dessus de la racine il n'y a rien. La racine n'est critique que lorsqu'elle relie deux sous-arbres ou plus autrement séparés, ce qui correspond exactement à la condition d'avoir deux fils DFS ou plus.

À quoi servent les points d'articulation?

Ils repèrent les routeurs critiques des réseaux de communication, les carrefours clés des systèmes routiers, les serveurs dont la panne partitionnerait une infrastructure distribuée et les intermédiaires influents des réseaux sociaux. L'ingénierie de la fiabilité s'en sert pour décider où la redondance vaut son coût.