Artikulationspunkte Finder

Pseudocode

Eine einzige Tiefensuche und zwei Zahlen je Knoten. Die Entdeckungszeit sagt, wann der Knoten zuerst gesehen wurde; der Low-Link-Wert sagt, welchen frühesten Knoten sein Teilbaum über eine Rückkante erreichen kann.

dfs(u, vorgänger):
    entd[u] = low[u] = ++zeit
    kinder = 0

    für jeden Nachbarn v von u:
        wenn v == vorgänger: weiter
        wenn v bereits besucht:
            low[u] = min(low[u], entd[v])   // Rückkante
        sonst:
            kinder++
            dfs(v, u)
            low[u] = min(low[u], low[v])
            wenn vorgänger != KEINER und low[v] >= entd[u]:
                markiere u als Artikulationspunkt

    wenn vorgänger == KEINER und kinder > 1:
        markiere u als Artikulationspunkt   // Wurzelregel

Die Bedingung low[v] >= entd[u] besagt, dass der im Kind v wurzelnde Teilbaum keine Rückkante besitzt, die über u hinausreicht. Jeder Weg aus diesem Teilbaum heraus führt also durch u, und u zu löschen schneidet ihn ab. Die Wurzel ist ein Sonderfall, weil sie keinen Vorgänger hat, von dem sie getrennt werden könnte: die Wurzel ist genau dann ein Artikulationspunkt, wenn sie zwei oder mehr DFS-Kinder hat, denn diese Teilbäume können einander nur über sie erreichen.

Durchgerechnetes Beispiel, Schritt für Schritt

Führe die Tiefensuche von A aus auf einem Graphen aus, der aus einem Dreieck mit einem zweiknotigen Anhängsel besteht, und nimm die Nachbarn alphabetisch.

Beispielgraph: Ungerichtete Kanten A-B, B-C und C-A bilden ein Dreieck, dazu C-D und D-E als Anhängsel.

1. Abstieg bis E. Entdeckungszeiten und Low-Link-Werte werden beim Abstieg vergeben: A erhält 1, B erhält 2, C erhält 3, D erhält 4 und E erhält 5. E ist ein Blatt, dessen einziger Nachbar sein Vorgänger D ist, also bleibt low[E] bei 5.
2. Zurück zu D. low[D] = min(4, low[E] = 5) = 4. Prüfe das Kind: low[E] = 5 >= entd[D] = 4, also reicht nichts unterhalb von E über D hinaus. D ist ein Artikulationspunkt, und tatsächlich isoliert das Entfernen von D den Knoten E.
3. Zurück zu C. C besitzt zusätzlich die Rückkante C-A, die low[C] = min(3, entd[A] = 1) = 1 setzt. Bezieht man das Kind ein, ergibt sich low[C] = min(1, low[D] = 4) = 1. Prüfe das Kind D: low[D] = 4 >= entd[C] = 3, also ist C ein Artikulationspunkt. Das Entfernen von C trennt das Anhängsel D-E vom Dreieck.
4. Zurück zu B. low[B] = min(2, low[C] = 1) = 1. Prüfe das Kind C: low[C] = 1 >= entd[B] = 2 ist falsch, denn C erreicht A auch ohne den Umweg über B. B ist somit kein Artikulationspunkt, was zutrifft: das Dreieck hält A und C auch ohne B verbunden.
5. Abschluss an der Wurzel. A ist die DFS-Wurzel. Sie hat genau ein DFS-Kind, nämlich B, da C über B und nicht direkt erreicht wurde. Ein einziges Kind bedeutet, dass die Wurzelregel nicht greift, A ist also kein Artikulationspunkt.

Die Artikulationspunkte sind C und D. Das Dreieck A-B-C liefert unter A und B keinen, weil jeder Knoten eines Zyklus eine Ausweichroute besitzt, während im Anhängsel C-D-E jeder innere Knoten kritisch ist. Dieser Gegensatz ist die eigentliche Intuition: Artikulationspunkte leben auf Ketten, nicht innerhalb von Zyklen.

Komplexität und woher sie kommt

Zeit: O(V + E) · Speicher: O(V)

Das ist eine einzige Tiefensuche mit konstantem Zusatzaufwand je Kante, sie kostet also genauso viel wie der Durchlauf selbst. Jeder Knoten wird einmal besucht und jede Kante zweimal betrachtet, einmal von jedem Endpunkt. Der zusätzliche Zustand besteht aus zwei ganzen Zahlen je Knoten, Entdeckungszeit und Low-Link, plus dem Rekursionsstapel, alles O(V). Die naive Alternative, jeden Knoten der Reihe nach zu entfernen und den Zusammenhang zu prüfen, kostet O(V mal (V + E)); die Low-Link-Methode verwandelt also eine quadratische Prüfung in einer einzigen Passe in eine lineare. Bei einem Graphen mit 10.000 Knoten und 30.000 Kanten liegt der Unterschied bei etwa vier Größenordnungen.

Wann Artikulationspunkte passt und wann nicht

Artikulationspunkte, Brücken und Zweifachzusammenhangskomponenten entspringen alle derselben Tiefensuche. Welche du brauchst, hängt davon ab, ob das Anfällige ein Knoten oder eine Kante ist.

Häufige Fehler

• Die Nichtwurzelregel auf die Wurzel anwenden. Die Wurzel hat keinen Vorgänger, der Test low[v] >= entd[u] ist dort also sinnlos und markiert sie meist fälschlich. Die Wurzel braucht ihre eigene Regel: sie ist genau dann ein Artikulationspunkt, wenn sie zwei oder mehr DFS-Kinder besitzt.
• Bei einer Rückkante low[v] statt entd[v] verwenden. Triffst du auf einen bereits besuchten Knoten v, aktualisiere mit entd[v], nicht mit low[v]. Die Verwendung von low[v] kann einen Wert aus einem anderen Teilbaum weitertragen und zu kleine Low-Link-Werte erzeugen, wodurch echte Artikulationspunkte verborgen bleiben.
• Den Kindtest mit dem Brückentest verwechseln. Artikulationspunkte nutzen low[v] >= entd[u]; Brücken nutzen low[v] > entd[u], also strikt größer. Der Unterschied eines einzigen Zeichens ist der Unterschied zwischen "alles muss durch diesen Knoten" und "alles muss über diese Kante".
• Den Vorgänger über die Identität statt über die Kante überspringen. Nur die Vorgängerkennung zu vergleichen scheitert bei Multigraphen. Verbinden zwei parallele Kanten u und v, so ist die zweite eine echte Ausweichroute und darf nicht übersprungen werden. Merke dir die Kante, über die du angekommen bist, nicht bloß den Knoten.
• Unzusammenhängende Komponenten vergessen. Eine einzelne DFS deckt nur eine Komponente ab. Iteriere über alle Knoten und starte von jedem unbesuchten eine neue DFS, wobei die Wurzelregel für jede neue Wurzel zurückgesetzt wird.

Häufig gestellte Fragen

Was ist ein Artikulationspunkt in einem Graphen?

Ein Artikulationspunkt, auch Schnittknoten genannt, ist ein Knoten, dessen Entfernen die Zahl der Zusammenhangskomponenten erhöht. Praktisch gesprochen ist er ein einzelner Ausfallpunkt: jeder Weg zwischen einem bestimmten Knotenpaar führt durch ihn, sodass sein Löschen den Graphen zerteilt.

Wie findet man Artikulationspunkte?

Führe eine einzige Tiefensuche aus und notiere für jeden Knoten seine Entdeckungszeit und seinen Low-Link-Wert, also die früheste aus seinem Teilbaum über höchstens eine Rückkante erreichbare Entdeckungszeit. Ein Knoten u, der nicht die Wurzel ist, ist genau dann ein Artikulationspunkt, wenn ein DFS-Kind v die Bedingung low[v] >= entd[u] erfüllt. Die Wurzel ist es, wenn sie zwei oder mehr DFS-Kinder hat. Das Ganze läuft in O(V + E).

Was ist der Unterschied zwischen einem Artikulationspunkt und einer Brücke?

Ein Artikulationspunkt ist ein Knoten, dessen Entfernen den Graphen trennt; eine Brücke ist eine Kante, die das bewirkt. Beide entspringen derselben DFS und unterscheiden sich in einem Vergleich: low[v] >= entd[u] für Artikulationspunkte und das strikte low[v] > entd[u] für Brücken. Ein Graph kann Brücken ohne Artikulationspunkte haben und umgekehrt.

Warum ist die Wurzel der DFS ein Sonderfall?

Weil der allgemeine Test fragt, ob ein Kindteilbaum etwas oberhalb des aktuellen Knotens erreichen kann, und oberhalb der Wurzel gibt es nichts. Die Wurzel ist nur dann kritisch, wenn sie zwei oder mehr sonst getrennte Teilbäume verbindet, was genau der Bedingung von zwei oder mehr DFS-Kindern entspricht.

Wofür werden Artikulationspunkte verwendet?

Sie kennzeichnen kritische Router in Kommunikationsnetzen, wichtige Knotenpunkte in Straßensystemen, Server, deren Ausfall eine verteilte Infrastruktur zerteilen würde, und einflussreiche Vermittler in sozialen Netzwerken. Die Zuverlässigkeitstechnik nutzt sie, um zu entscheiden, wo sich Redundanz lohnt.