Ein Artikulationspunkt (englisch articulation point, auch Gelenkpunkt oder cut vertex) ist ein Knoten eines ungerichteten Graphen, dessen Entfernung die Zahl der Zusammenhangskomponenten erhöht. Entfernt man einen Artikulationspunkt samt seiner Kanten, zerfällt das Netzwerk in mehrere Teile — er ist ein Single Point of Failure.
Beispiel
Betrachte einen ungerichteten Graphen mit den Knoten A–B–C–D in einer Kette. Knoten B ist ein Artikulationspunkt: Ohne B sind A und die Gruppe C–D voneinander getrennt. Knoten A ist keiner: Sein Verlust entfernt nur ein Ende der Kette, der Rest bleibt verbunden. Dieselbe Logik gilt für Netzwerk-Hubs, Straßenknoten und Umspannwerke.
Eigenschaften
- Ein Graph ohne Artikulationspunkte heißt 2-fach zusammenhängend (biconnected). Seine maximalen 2-fach zusammenhängenden Teilgraphen heißen Blöcke (biconnected components).
- Zwei verschiedene Blöcke teilen sich höchstens einen Knoten — und genau dieser gemeinsame Knoten ist ein Artikulationspunkt.
- Eine Brücke ist eine Kante, die in keinem Block mit mehr als zwei Knoten liegt. Brücken und Artikulationspunkte sind damit Geschwister: die eine spaltet über eine Kante, der andere über einen Knoten.
Berechnung: Tarjan mit Lowlink
Wie bei den Brücken liefert eine Tiefensuche mit Lowlink-Werten alle Artikulationspunkte in O(V + E) (Tarjan 1972). Es gibt zwei Kriterien:
- Wurzel: Die Wurzel des DFS-Baums ist ein Artikulationspunkt, wenn sie mindestens zwei Kinder im DFS-Baum hat.
- Anderer Knoten v: v ist ein Artikulationspunkt, wenn es ein DFS-Kind to gibt mit low[to] ≥ tin[v] — von to aus führt kein Umweg zu einem echten Vorfahren von v.
Der einzige Unterschied zu den Brücken ist das „≥“ statt „>“: Schon eine Rückwärtskante direkt zu v selbst schützt die Kante, aber nicht den Knoten v.
Anwendungen
- Netzwerktechnik: Der Ausfall eines Routers spaltet das Firmennetz — der Router ist ein Artikulationspunkt; Redundanz macht ihn unkritisch.
- Infrastruktur: Eine einzige Straßenbrücke oder eine einzelne Stromleitung zu einem Stadtteil macht den Anschlusspunkt kritisch.
- Soziale Netzwerke: Personen, deren Entfernung die Community spaltet, sind strukturelle Vermittler (Broker).
Abgrenzung: Starke Zusammenhangskomponenten betrachten gerichtete Graphen und gegenseitige Erreichbarkeit; Artikulationspunkte zerlegen ungerichtete Netze nach kritischen Knoten.
Verwandte Grundlagen: Kante, Brücke (Graph).