Pivot point (graph theory)
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:
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 .
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
- ↑ 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)
- ↑ Presentation of the O ( n + m ) algorithm (in English; PDF; 447 kB)