Composantes connexes, ponts et points d'articulation

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

1. Ce que signifie « connexe »

Un graphe est connexe lorsqu'il existe un chemin entre chaque paire de ses sommets. Vous pouvez partir de n'importe où et, en suivant les arêtes, arriver partout. Quand ce n'est pas le cas, le graphe se décompose en morceaux appelés composantes connexes : les plus grands sous-graphes connexes qu'il contient, sans aucune arête entre deux morceaux différents.

La façon la plus claire de voir les composantes passe par la relation « le sommetu peut atteindre v ». Elle est réflexive (chaque sommet s'atteint lui-même par le chemin vide), symétrique (dans un graphe non orienté, un chemin peut se parcourir à l'envers) et transitive (deux chemins peuvent être mis bout à bout). Une relation qui possède ces trois propriétés est une relation d'équivalence, et toute relation d'équivalence partage son ensemble en classes disjointes. Les classes de l'accessibilité sont exactement les composantes. C'est pourquoi chaque sommet appartient à exactement une composante, et pourquoi un sommet isolé, sans aucune arête, forme une composante à lui seul.

Un seul graphe accompagne tout l'article. Il a douze sommets et treize arêtes, et il est construit pour que chaque idée ci-dessous ait un exemple concret et, quand c'est utile, un contre-exemple concret :

V = {A, B, C, D, E, F, G, H, I, J, K, L}
E = {AB, BC, CA, CD, DE, EC, EF, FG, GH, HI, IF, IJ, KL}        13 arêtes

composante 1 = {A, B, C, D, E, F, G, H, I, J}     12 arêtes
composante 2 = {K, L}                               1 arête

Le vocabulaire vient du guide sur les sommets et arêtes, et tout ce qui suit concerne les graphes non orientés jusqu'à la section 11, où l'orientation change la donne.

2. Trouver les composantes

Comme les composantes sont des classes d'accessibilité, n'importe quel parcours de graphe les trouve. Lancez un parcours en largeur ou en profondeur depuis un sommet ; tout ce qu'il atteint forme la composante de ce sommet. Recommencez ensuite depuis un sommet pas encore atteint, et répétez jusqu'à ce qu'il n'en reste aucun. Chaque nouveau départ donne une composante de plus.

from collections import deque

def connected_components(graph):
    """Étiquette chaque sommet d'un graphe non orienté avec l'indice de sa composante."""
    label, components = {}, []
    for start in graph:                      # les sommets isolés forment leur propre composante
        if start in label:
            continue
        label[start] = len(components)
        members, queue = [start], deque([start])
        while queue:
            u = queue.popleft()
            for v in graph[u]:
                if v not in label:
                    label[v] = len(components)
                    members.append(v)
                    queue.append(v)
        components.append(sorted(members))
    return components, label

edges = ['AB', 'BC', 'CA', 'CD', 'DE', 'EC', 'EF', 'FG', 'GH', 'HI', 'IF', 'IJ', 'KL']
graph = {v: [] for v in 'ABCDEFGHIJKL'}
for u, v in edges:
    graph[u].append(v)
    graph[v].append(u)

components, label = connected_components(graph)
print(len(components), components)
# 2 [['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J'], ['K', 'L']]
print(label['H'] == label['A'], label['K'] == label['A'])
# True False

Chaque sommet est étiqueté une fois et chaque arête est examinée deux fois, une fois depuis chaque extrémité, donc le travail complet prend un temps O(V + E). La boucle externe sur tous les sommets est la ligne importante. Un parcours unique répond à « que puis-je atteindre d'ici », pas à « combien y a-t-il de morceaux », et oublier la boucle est une façon courante d'obtenir 1 composante pour un graphe qui en a plusieurs.

Deux variantes méritent d'être connues. Si les arêtes arrivent une par une et que vous ne faites qu'en ajouter, une structure union-find maintient les composantes à jour en un temps amorti quasi constant par arête : chaque arête fusionne les classes de ses deux extrémités, et deux sommets sont dans la même composante exactement quand ils ont la même racine. L'idée remonte à l'algorithme d'équivalence de Galler et Fischer de 1964. Et en traitement d'images, où le « graphe » est une grille de pixels, le même problème s'appelle étiquetage en composantes connexes. Rosenfeld et Pfaltz en ont décrit un balayage séquentiel en 1966. Le fait de compter les voisins en diagonale, ce qu'on appelle la 8-connexité, ou seulement les quatre voisins orthogonaux, ce qu'on appelle la 4-connexité, change les formes qui constituent une seule région et celles qui en forment deux.

Il existe même une réponse algébrique. La matrice laplacienne d'un graphe, avec les degrés sur la diagonale et −1 pour chaque arête, a la valeur propre 0 avec une multiplicité exactement égale au nombre de composantes. Pour l'exemple fil rouge, cette multiplicité vaut 2. Le lien entre valeurs propres et structure est développé en théorie spectrale des graphes.

3. Ce que dit le nombre de composantes

Notez n le nombre de sommets, m le nombre d'arêtes et k le nombre de composantes. Une poignée de faits relient les trois, et ils servent de vérifications de cohérence pour tout programme qui compte des composantes.

Un graphe à n sommets et k composantes a au moins n − k arêtes, avec égalité exactement quand c'est une forêt.

La preuve est un argument de comptage. Partez de n sommets isolés, soit n composantes, et ajoutez les arêtes une à une. Chaque arête soit relie deux composantes différentes, ce qui diminue le compte de un, soit tombe à l'intérieur d'une composante et ne change rien. Pour descendre à k composantes, il vous faut au moins n − k arêtes du premier type, et vous en avez exactement autant quand aucune arête n'a été gaspillée à fermer un cycle. Une forêt est précisément un graphe sans cycle, et un arbre est une forêt connexe, ce qui explique pourquoi un arbre à n sommets a n − 1 arêtes, comme le guide sur les arbres en théorie des graphes le prouve de plusieurs autres façons. L'exemple fil rouge vérifie 13 ≥ 12 − 2 = 10, avec trois arêtes en trop, une pour chacun de ses trois cycles.

L'autre sens a aussi un plafond. Un graphe simple à k composantes a au plus C(n − k + 1, 2) arêtes, nombre atteint en plaçant n − k + 1 sommets dans un seul graphe complet et en laissant les k − 1 autres isolés. Un corollaire donne un test de connexité rapide : un graphe simple qui a plus de C(n − 1, 2) arêtes ne peut pas avoir deux composantes, donc il est forcément connexe.

Un dernier fait est un exercice classique avec une preuve de deux lignes : un graphe ou son complémentaire est toujours connexe. Si G n'est pas connexe, prenez deux sommets quelconques. S'ils se trouvent dans des composantes différentes de G, ils sont adjacents dans le complémentaire. S'ils sont dans la même composante, choisissez un sommet dans une autre composante ; il est adjacent aux deux dans le complémentaire. Dans tous les cas, ils sont reliés par un chemin de longueur au plus deux. Ces trois faits ont été vérifiés par force brute sur tous les graphes simples d'au plus six sommets.

4. Les ponts : les arêtes que vous ne pouvez pas perdre

La connexité ne se résume pas à savoir si un graphe tient ensemble : elle mesure aussi avec quelle solidité. Un pont, aussi appelé isthme, est une arête dont la suppression augmente le nombre de composantes. La supprimer coupe sa composante en exactement deux morceaux, jamais plus, car retirer une arête ne peut séparer que ses deux extrémités l'une de l'autre.

Une arête est un pont si et seulement si elle n'appartient à aucun cycle.

Si une arête uv appartient à un cycle, le reste du cycle est un second chemin de u à v, donc retirer l'arête ne déconnecte rien. Inversement, si retirer uv laisse u et v reliés, le chemin restant de v jusqu'à u forme, avec uv, un cycle. Les ponts sont donc exactement les arêtes sans itinéraire de rechange. Deux conséquences suivent immédiatement : dans un arbre, chaque arête est un pont, et une arête entre deux sommets reliés par une seconde arête parallèle n'est jamais un pont.

L'exemple fil rouge a trois ponts : E–F, I–J et K–L. Retirer n'importe lequel d'entre eux fait passer le nombre de composantes de 2 à 3. Toutes les autres arêtes appartiennent à l'un des trois cycles, les deux triangles et le carré.

5. Les points d'articulation : les sommets que vous ne pouvez pas perdre

Un point d'articulation, aussi appelé sommet d'articulation, est un sommet dont la suppression, avec ses arêtes, augmente le nombre de composantes. De façon équivalente, v est un point d'articulation lorsqu'il existe deux autres sommets u et w dans sa composante tels que tout chemin de u à w passe par v.

Contrairement à un pont, un point d'articulation peut couper sa composante en plusieurs morceaux à la fois. Retirez le centre d'une étoile à cinq feuilles et il reste cinq composantes. Dans l'exemple fil rouge, retirer C laisse trois composantes : {A, B}, tout ce qui va de D à J, et {K, L}, qui était déjà séparée.

Ponts et points d'articulation sont liés, et ce lien est un piège qui mérite d'être énoncé avec soin :

• Une extrémité d'un pont est un point d'articulation, sauf si elle est de degré 1. Retirez E et le pont disparaît avec lui, ce qui sépare le côté de F du côté de D. Voilà pourquoi E, F et I sont des points d'articulation.
• Un pont n'a pas forcément de point d'articulation à ses extrémités. K–L est un pont, mais ses deux extrémités sont de degré 1, et retirer une feuille ne déconnecte jamais rien.
• Un point d'articulation ne touche pas forcément de pont. C relie deux triangles, une figure souvent appelée nœud papillon. Chaque arête en C appartient à un triangle, donc aucune n'est un pont, et pourtant retirer C coupe A et B du reste.

L'exemple fil rouge a donc quatre points d'articulation, C, E, F et I, et les deux idées sont réellement différentes : les pannes de sommets et les pannes de liens révèlent des points faibles différents dans un même réseau.

6. Un seul parcours en profondeur trouve les deux

L'algorithme évident supprime chaque arête, ou chaque sommet, tour à tour et recompte les composantes. Cela coûte un parcours complet par candidat, soit O(E(V + E)) pour les ponts. En 1972 et 1973, Tarjan, puis Hopcroft et Tarjan, ont montré qu'un seul parcours en profondeur suffit, en O(V + E) au total. La méthode repose sur deux nombres par sommet.

• disc[v] est l'instant où le parcours atteint v pour la première fois : 0 pour le premier sommet, 1 pour le suivant, et ainsi de suite.
• low[v] est le plus petit instant de découverte que l'on peut atteindre depuis le sous-arbre de v en descendant par des arêtes d'arbre puis en empruntant au plus une arête arrière.

Dans un parcours en profondeur non orienté, toute arête hors de l'arbre est une arête arrière : elle relie un sommet à l'un de ses ancêtres. Une arête arrière est une issue de secours, un moyen de sortir d'un sous-arbre sans utiliser l'arête d'arbre située au-dessus. Les deux tests demandent si une telle issue existe. Pour une arête d'arbre allant du parent u vers l'enfant v :

pont            u–v est un pont                  si  low[v] > disc[u]    rien sous v n'atteint u ou plus haut
articulation    u est un point d'articulation    si  low[v] ≥ disc[u]    rien sous v n'atteint plus haut que u
racine          la racine est un point d'articulation  si elle a 2 enfants ou plus dans l'arbre DFS

La racine a besoin de sa propre règle car rien ne se trouve au-dessus d'elle : elle sépare le graphe exactement quand le parcours a dû la quitter deux fois, ce qui signifie que ses sous-arbres n'ont aucune arête entre eux. Voici la méthode complète, écrite de façon itérative pour qu'un long chemin ne puisse pas faire déborder la pile d'appels de Python :

def bridges_and_cut_vertices(vertices, edges):
    """Méthode low-link de Tarjan, itérative. Les arêtes sont des paires (u, v) ; les arêtes parallèles sont autorisées."""
    adj = {v: [] for v in vertices}
    for i, (u, v) in enumerate(edges):       # retenir les identifiants d'arêtes, pas seulement les voisins
        adj[u].append((v, i))
        adj[v].append((u, i))
    disc, low, bridges, cuts, clock = {}, {}, [], set(), 0
    for root in vertices:
        if root in disc:
            continue
        disc[root] = low[root] = clock; clock += 1
        children = 0
        stack = [(root, -1, iter(adj[root]))]  # (sommet, id de l'arête d'arrivée, voisins)
        while stack:
            u, in_edge, it = stack[-1]
            for v, i in it:
                if i == in_edge:             # ignorer cette seule arête, pas toutes les arêtes vers le parent
                    continue
                if v in disc:                # arête arrière : une issue qui remonte l'arbre
                    low[u] = min(low[u], disc[v])
                else:                        # arête d'arbre : descendre
                    disc[v] = low[v] = clock; clock += 1
                    stack.append((v, i, iter(adj[v])))
                    break
            else:                            # u est terminé : remonter le résultat au parent p
                stack.pop()
                if stack:
                    p = stack[-1][0]
                    low[p] = min(low[p], low[u])
                    if low[u] > disc[p]:
                        bridges.append(edges[in_edge])
                    if low[u] >= disc[p] and p != root:
                        cuts.add(p)
                    if p == root:
                        children += 1
        if children >= 2:                    # la racine n'est un point d'articulation qu'avec 2+ enfants DFS
            cuts.add(root)
    return bridges, sorted(cuts), disc, low

edges = ['AB', 'BC', 'CA', 'CD', 'DE', 'EC', 'EF', 'FG', 'GH', 'HI', 'IF', 'IJ', 'KL']
bridges, cuts, disc, low = bridges_and_cut_vertices('ABCDEFGHIJKL', edges)
print(bridges)
# ['IJ', 'EF', 'KL']
print(cuts)
# ['C', 'E', 'F', 'I']

print(bridges_and_cut_vertices('xy', ['xy', 'xy'])[0])   # une arête doublée n'est pas un pont
# []

Sur l'exemple fil rouge, le parcours depuis A se trouve descendre tout droit le long d'un chemin, A, B, C, …, J, et les trois arêtes hors de l'arbre C–A, E–C et I–F deviennent des arêtes arrière. La figure montre les nombres obtenus.

Confronter la table aux règles donne toutes les réponses. low[F] = 5 est plus grand que disc[E] = 4, donc rien sous F ne remonte jusqu'à E, et E–F est un pont ; I–J est un pont pour la même raison, avec 9 > 8. low[D] = 2 est égal à disc[C] = 2 : le sous-arbre sous C peut remonter jusqu'à C lui-même mais pas plus haut, donc C est un point d'articulation bien qu'aucun pont ne le touche. Quant à A, la racine, il n'a qu'un seul enfant, donc il n'en est pas un.

7. Deux bugs qui passent les tests simples

Le code low-link est court, et deux de ses erreurs classiques produisent des réponses correctes sur la plupart des petits exemples. Les deux ont été vérifiées par force brute : la version ci-dessus concorde avec « supprimer et recompter » sur 5 000 multigraphes aléatoires.

Ignorer le sommet parent au lieu de l'arête parente. Quand le parcours examine les voisins de v, il ne doit pas traiter l'arête d'arbre par laquelle il est arrivé comme une arête arrière, sinon chaque sommet pourrait s'échapper par son propre parent. Beaucoup d'implémentations ignorent « le voisin égal à mon parent ». C'est correct dans un graphe simple, mais avec deux arêtes parallèles entre x et y, cette règle les ignore toutes les deux, et l'arête doublée est signalée comme un pont alors que supprimer une copie ne déconnecte rien. Ignorer cette seule arête par son identité, comme le fait le code avec in_edge, reste correct pour les multigraphes également.

Utiliser low[w] au lieu de disc[w] sur une arête arrière. La mise à jour le long d'une arête arrière vers w doit utiliser disc[w]. Écrire low[w] permet à l'issue de secours de continuer au-delà de w par des arêtes qui appartiennent à un autre bloc. Pour les ponts, c'est sans conséquence : sur 20 000 graphes aléatoires, la variante ne s'est jamais trompée sur un pont. Pour les points d'articulation, ce n'est pas le cas : le même test l'a prise en défaut sur 35 des graphes, et le plus petit échec trouvé par cette recherche est la paire de triangles qui partagent C. Avec low[w], l'arête arrière E–C importe low[C] = 0, donc low[D] devient 0, le test en C échoue, et le point d'articulation disparaît de la sortie.

8. Les blocs et l'arbre des blocs et des points d'articulation

Les points d'articulation découpent un graphe connexe en morceaux naturels. Un bloc est un sous-graphe connexe maximal sans point d'articulation propre : soit un morceau 2-connexe, qui reste connexe après la suppression de n'importe quel sommet, soit un pont seul, soit un sommet isolé. Chaque arête appartient à exactement un bloc, et deux blocs partagent au plus un sommet, qui est alors un point d'articulation. Les blocs s'appellent aussi composantes biconnexes, et l'algorithme de Hopcroft et Tarjan de 1973 les trouve dans le même parcours unique, en gérant une pile d'arêtes et en dépilant un bloc chaque fois que le test de point d'articulation se déclenche.

L'exemple fil rouge a six blocs : les triangles {A, B, C} et {C, D, E}, le carré {F, G, H, I}, et les trois ponts {E, F}, {I, J} et {K, L}.

La structure appelée arbre des blocs et des points d'articulation, introduite par Harary et Prins en 1966, a un nœud par bloc et un nœud par point d'articulation, avec une arête chaque fois que le point d'articulation se trouve dans le bloc. Pour un graphe connexe, c'est toujours un arbre. Pour la composante 1, elle a 5 nœuds de blocs et 4 nœuds de points d'articulation, soit 9 nœuds reliés par 8 arêtes. Cet arbre est le squelette grossier du graphe : il répond à « quelles pannes séparent quelles parties » sans regarder à l'intérieur d'aucun bloc.

Les ponts donnent une décomposition parallèle. Supprimez tous les ponts, et ce qui reste se répartit en composantes 2-arête-connexes, des morceaux qui survivent à la perte de n'importe quelle arête. L'exemple en a cinq : {A, B, C, D, E}, {F, G, H, I}, et les sommets isolés {J}, {K} et {L}. Notez que la première forme une seule composante 2-arête-connexe mais deux blocs. Le nœud papillon survit à toute panne d'une seule arête, mais pas à la panne de C.

Deux théorèmes classiques expliquent ce qu'apporte vraiment l'absence de point d'articulation. Whitney a montré en 1932 qu'un graphe d'au moins trois sommets est 2-connexe exactement quand deux sommets quelconques sont reliés par deux chemins sans sommet intérieur commun, ce qui revient à dire que deux sommets quelconques appartiennent à un cycle commun. Et Robbins a prouvé en 1939 que l'on peut orienter les arêtes d'un graphe connexe de sorte que chaque sommet atteigne tous les autres exactement quand le graphe n'a aucun pont, le théorème au cœur du guide sur les graphes orientés et non orientés.

9. Mesurer à quel point un graphe est connexe

Les ponts et les points d'articulation sont le premier barreau d'une échelle. La connexité par sommets κ(G) est le plus petit nombre de sommets dont la suppression déconnecte le graphe, ou ne laisse qu'un seul sommet. La connexité par arêtes λ(G) est le plus petit nombre d'arêtes dont la suppression le déconnecte. Un graphe connexe d'au moins trois sommets a un point d'articulation exactement quand κ = 1, et un graphe connexe d'au moins deux sommets a un pont exactement quand λ = 1. L'inégalité de Whitney de 1932 relie les deux au degré minimum δ(G) :

κ(G)  ≤  λ(G)  ≤  δ(G)

deux triangles partageant C  κ = 1   λ = 2   δ = 2      un point d'articulation, mais aucun pont
composante 1 de l'exemple    κ = 1   λ = 1   δ = 1      J ne tient qu'à une seule arête
tout cycle                   κ = 2   λ = 2   δ = 2

L'inégalité de droite est facile : supprimer les arêtes d'un sommet de degré minimum l'isole. Celle de gauche dit que les pannes de sommets sont toujours au moins aussi dangereuses que les pannes d'arêtes, et le nœud papillon montre que l'écart peut être réel.

Le théorème de Menger de 1927 transforme ces minimums en maximums. Le plus petit nombre d'arêtes dont la suppression sépare deux sommets u et v est égal au plus grand nombre de chemins de u à v sans arête commune. La version pour les sommets est le même énoncé avec des chemins intérieurement disjoints, et elle exige que u et v ne soient pas adjacents, puisqu'aucun ensemble d'autres sommets ne sépare deux voisins. Le théorème de Menger est un cas particulier du théorème flot max-coupe min, qui est aussi la méthode utilisée en pratique pour calculer la connexité.

10. Là où cela compte

Les composantes, les ponts et les points d'articulation forment le vocabulaire de l'analyse des pannes. Dès qu'un système peut être modélisé par des éléments et des liens, ces notions désignent ses points faibles.

Les composantes expliquent aussi l'un des résultats les plus célèbres sur les graphes aléatoires. Erdős et Rényi ont montré en 1960 que si vous ajoutez des arêtes aléatoires à n sommets isolés, les composantes restent petites jusqu'à ce que le degré moyen dépasse 1, puis, assez soudainement, une seule composante géante contenant une fraction constante de tous les sommets apparaît. Cette transition de phase, décrite dans l'histoire de la théorie des graphes, explique pourquoi les grands réseaux réels ont presque toujours une composante dominante, entourée de quelques petites composantes éparses.

Quand le graphe change sans cesse, la connexité devient un problème de structure de données. Les insertions seules sont faciles avec union-find. Les suppressions sont bien plus difficiles, car retirer une arête peut ou non couper une composante, et le savoir semble exiger un parcours. Holm, de Lichtenberg et Thorup ont montré en 2001 que la connexité, la 2-arête-connexité et la biconnexité peuvent toutes être maintenues sous insertions et suppressions en temps amorti polylogarithmique par mise à jour.

11. Graphes orientés : connexité faible et forte

Dans un graphe orienté, la relation « le sommetu peut atteindre v » n'est plus symétrique, ce n'est donc plus une relation d'équivalence, et « la composante de v » demande un choix. Il existe deux choix classiques.

• Les composantes faiblement connexes ignorent l'orientation : ce sont les composantes du graphe non orienté sous-jacent, et tout ce que dit cet article s'y applique sans changement.
• Les composantes fortement connexes exigent l'accessibilité dans les deux sens. La relation « le sommetu atteint v et v atteint u » est de nouveau une relation d'équivalence, et ses classes sont les composantes fortement connexes, trouvées en temps linéaire par l'algorithme de Tarjan ou celui de Kosaraju, comme le guide sur les composantes fortement connexes l'explique.

Lancer le code des composantes non orientées sur une liste d'adjacence orientée ne donne aucune des deux réponses. Il ne suit les arcs que dans leur sens, donc les « composantes » qu'il renvoie dépendent de l'endroit où chaque parcours a commencé. Symétrisez d'abord les listes pour obtenir les composantes faibles, ou utilisez un algorithme de composantes fortes.

12. Erreurs fréquentes

13. Glossaire

15. Références

Les définitions, théorèmes et attributions ci-dessus proviennent de ces sources, classées par ordre chronologique.

1. Menger, K. (1927). "Zur allgemeinen Kurventheorie." Fundamenta Mathematicae 10, 96 à 115. Chemins disjoints et ensembles séparateurs.
2. Whitney, H. (1932). "Congruent Graphs and the Connectivity of Graphs." American Journal of Mathematics 54(1), 150 à 168.
3. Whitney, H. (1932). "Non-separable and Planar Graphs." Transactions of the American Mathematical Society 34(2), 339 à 362. Avec l'article ci-dessus, l'inégalité entre connexité par sommets, connexité par arêtes et degré minimum, et la caractérisation des graphes 2-connexes par des chemins disjoints.
4. Robbins, H. E. (1939). "A Theorem on Graphs, with an Application to a Problem of Traffic Control." American Mathematical Monthly 46(5), 281 à 283.
5. Erdős, P. et Rényi, A. (1960). "On the Evolution of Random Graphs." Publications of the Mathematical Institute of the Hungarian Academy of Sciences 5, 17 à 61. La composante géante.
6. Galler, B. A. et Fischer, M. J. (1964). "An Improved Equivalence Algorithm." Communications of the ACM 7(5), 301 à 303. L'idée d'union-find pour fusionner des classes.
7. Harary, F. et Prins, G. (1966). "The Block-Cutpoint-Tree of a Graph." Publicationes Mathematicae Debrecen 13, 103 à 107.
8. Rosenfeld, A. et Pfaltz, J. L. (1966). "Sequential Operations in Digital Picture Processing." Journal of the ACM 13(4), 471 à 494. Étiquetage en composantes connexes des images.
9. Tarjan, R. E. (1972). "Depth-First Search and Linear Graph Algorithms." SIAM Journal on Computing 1(2), 146 à 160.
10. Hopcroft, J. E. et Tarjan, R. E. (1973). "Algorithm 447: Efficient Algorithms for Graph Manipulation." Communications of the ACM 16(6), 372 à 378. Composantes biconnexes et points d'articulation en temps linéaire.
11. Tarjan, R. E. (1974). "A Note on Finding the Bridges of a Graph." Information Processing Letters 2(6), 160 à 161.
12. Holm, J., de Lichtenberg, K. et Thorup, M. (2001). "Poly-logarithmic Deterministic Fully-Dynamic Algorithms for Connectivity, Minimum Spanning Tree, 2-Edge, and Biconnectivity." Journal of the ACM 48(4), 723 à 760.
13. Diestel, R. (2017). Graph Theory, 5e édition. Graduate Texts in Mathematics 173. Berlin : Springer.