Ein Articulation Point oder Cut Vertex ist ein Knoten in einem ungerichteten Graphen, dessen Entfernung die Anzahl der Connected Components erhöht.
Unterschied zu Bridges
Code
Articulation Point = kritischer Knoten
Bridge = kritische KanteDiscovery und Low-Link
Die lineare DFS-Lösung verwendet:
Code
disc[u]
low[u]disc[u] ist der Zeitpunkt der ersten Entdeckung.
low[u] beschreibt den frühesten erreichbaren Vorfahren aus dem DFS-Teilbaum.
Bedingung für Nicht-Wurzel-Knoten
Für ein DFS-Kind v von u gilt:
Code
low[v] >= disc[u]Dann ist u ein Articulation Point.
Wurzel-Regel
Die DFS-Wurzel ist genau dann kritisch, wenn sie mehr als ein DFS-Kind besitzt.
Anwendungen
- Router und Switches
- Single Points of Failure
- Verkehrsnetze
- Infrastruktur
- Netzwerkresilienz
- Biconnected Components
Komplexität
Code
O(V + E)Fazit
Articulation Points zeigen strukturell kritische Knoten eines ungerichteten Graphen. Tarjans DFS findet alle solchen Knoten in linearer Zeit.