Pivot point (graph theory)

An undirected graph with n = 5 nodes and 3 articulation points (marked in red)

An undirected graph with no points of articulation

In graph theory , an articulation point , articulation point , articulation or intersection node denotes a node of a graph , the removal of which would increase the number of connected subgraphs . If the graph was connected before the node was removed, it will be disconnected afterwards. A pivot point is a special case of a separator .

The term pivot point is also well defined for directed graphs, but is mainly used for undirected graphs. In principle, a connected undirected graph with n nodes cannot have more than n-2 articulation points.

A bridge is an edge analogous to a hinge point; that is, removing the bridge increases the number of connected subgraphs.

Finding points of articulation

A trivial algorithm: ${\displaystyle O(nm)}$

C = leere Menge (nach Beenden des Algorithmus wird sie die Gelenkpunkte enthalten)
a = Anzahl der zusammenhängenden Teilgraphen (gefunden mit Tiefensuche/Breitensuche)
for alle Knoten i in V auf den Kanten zeigen
    b = Anzahl der zusammenhängenden Teilgraphen, wenn i entfernt wird
    if b > a
        i ist ein Gelenkpunkt
        C = C + {i}
    endif
endfor

There is an algorithm that uses depth-first search to achieve a significantly better runtime of . ${\displaystyle O(n+m)}$

Articulation points in trees

A node of a tree G is a pivot point if and only if the degree of the node is greater than 1.

literature

• Nirmala, K .; Ramachandra Rao, A. The number of cut vertices in a regular graph. Cah. Cent. Etud. Rech. Opér. 17: 295-299 (1975).

Web links

• Wolfram Mathworld: "Cut-Vertex" (in English)

Individual evidence

1. ↑ Rao, SB; Ramachandra Rao, A. The number of cut vertices and cut arcs in a strong directed graph. Acta Math. Acad. Sci. Hung. 22, 411-421 (1972)
2. ↑ Presentation of the O ( n + m ) algorithm (in English; PDF; 447 kB)