Brücken & Gelenkpunkte

(EN: bridges & articulation points)

Flutfüllung

Tiefensuche (DFS) kann nicht nur auf Bäume angewendet werden. Die Flutfüllung (flood-fill) ist eine Tiefensuche auf einem beliebigen Graphen. Das Problem bei der Tiefensuche auf einem beliebigen Graphen ist, dass man auf einen Zyklus stossen kann (hier blau markiert) und so immer denselben Pfad unendlich oft aufruft.

%3 a a b b a->b c c b->c c->a d d c->d e e c->e

Die Lösung zu diesem Problem ist, dass man jeden Knoten nur einmal besucht. Dazu muss man einfach bei jedem besuchten Knoten abspeichern, ob man ihn besucht hat. Falls ja wird dieser Knoten nicht mehr aufgerufen.

void floodFill(vector<vector<int> > & graph, vector<bool> & visited, int node) {
    visited[node] = true;
    for(int it : graph[node])
        if(visited[it] == false)
            floodFill(graph, visited, it);
}

Die resultierende Traversierung hat nun keine Zyklen und ist ein Baum, ein sogenannter Spannbaum (spanning tree). Deswegen bezeichnet man diese Flutfüllung ebenfalls als eine Tiefensuche (DFS). Ein möglicher Spannbaum ist unten eingetragen:

%3 a a b b a--b c c b--c c--a d d c--d e e c--e

Beim DFS wird aber in Wirklichkeit jeder Knoten mehrmals aufgerufen, denn jedes mal, wenn man ein Kind besucht hat, kehrt man zurück zum Vater. Den resultierenden Pfad der Traversierung nennt man auch den Suchpfad (search path).

%3 a a b b a->b 1 b->a 8 c c b->c 2 c->a c->b 7 d d c->d 3 e e c->e 5 d->c 4 e->c 6
void dfs(vector<vector<int> > & graph, vector<bool> & visited, int node) {
    visited[node] = true;
    //code here gets executed on the first visit
    for(int it : graph[node]) {
        if(visited[it] == false) dfs(graph,visited,it);
        //code here gets executed after each child node is visited
    }
    //code here gets executed on the last visit. It will now return to the parent node.
}

Diese Tiefensuche kann verwendet werden um zusammenhängende Komponente (connected components) zu bestimmen. Hier wird anstelle eines boolean ein int verwendet, welcher die jeweilige Komponente markiert. Falls ein Knoten noch nicht besucht worden ist hat er den Wert -1. Der Algorithmus läuft in \(O(V+E)\) auf einer Addjazenzliste.

void dfs(vector<vector<int> > & graph, vector<int > & components, int node, int component) {
    visited[node] = component;
    for(int it : graph[node])
        if(component[it] == -1) dfs(graph,visited,it,component);
}

vector<int> findComponents(vector<vector<int> > & graph) {
    vector<int> components(graph.size(), -1);
    int componentCount = 0;
    for(int i = 0; i < graph.size(); ++i) {
        //start dfs at each node
        if(components[i] == -1) {
            dfs(graph, components, i, componentCount);
            componentCount++;
        }
    }
}

Brücken & Gelenkpunkte

Brücken (bridges) und Gelenkpunkte (articulation points oder cut vertices) sind sogenannte Knotentrenner (vertex seperators).

Wenn man also einer dieser Knotentrenner entfernt, wird der Graph nicht mehr zusammenhängend sein und die Anzahl zusammenhängende Komponente erhöht sich. Eine Brücke ist dabei eine Kante, welche einen Graphen zusammenhält, während ein Gelenkpunkt ein Knoten ist. Wenn man einen Gelenkpunkt entfernt, entfernt man auch automatisch die Kanten, welche mit dem Gelenkpunkt in Verbindung stehen.

Eigenschaften Brücke & Gelenkpunkt

Brücken & Gelenkpunkte werden hier in Gelb markiert sein.

Knoten, welche nur mit einer Kante verbunden sind (Grad 1 besitzen), heissen Blätter. Brücken sind Kanten die es nur zwischen Blättern und Gelenkknoten geben kann! Wäre einer der verbundenen Knoten kein Gelenkpunkt, wäre die Kante teil eines Zyklus. Blätter sind keine Gelenkpunkte, da wenn man sie entfernt die Komponentenanzahl nicht erhöht wird.

Hier ein paar Beispiele von Brücken:

%3 a a b b a--b %3 a a d d a--d b b a--b e e d--e f f f--d g g f--g c c b--c c--a e--f

Das ist aber keine hinreichende Bedingung, z.B. ist in diesem Graphen \((b,d)\) keine Brücke, obwohl b und d Artikulationsknoten sind.

%3 a a b b a--b c c b--c d d c--d d--b e e d--e

Die gleiche Beziehung besteht auch nicht von Gelenkpunkten zu Brücken. Ein Gelenkpunkt muss nicht zwingend mit einer Brücke verbunden sein. Siehe das Beispiel unten. Würde man a entfernen, hätte man 3 zusammenhängende Komponente (markiert rot, grün, blau). Trotzdem gibt es keine Brücke.

%3 a a b b a--b d d a--d f f a--f c c b--c c--a e e d--e e--a g g f--g g--a

Falls es zwei Kanten gibt, die die gleichen Knoten verbinden (Duplikat), muss man nur eine davon beachten. Die Gelenkpunkte sind unabhängig von der Anzahl identischer Kanten, Brücken hingegen nicht.

Gelenkpunkte naiv finden

Eine einfache Methode Gelenkpunkte zu finden, ist einfach jeden Knoten einmal zu entfernen und auf diesen Graphen eine zusammenhängende Komponentensuche zu starten (Siehe Sektion Flutfüllung). Wenn die Anzahl Komponente zugenommen hat, handelt es sich bei dem Graphen um einen Gelenkpunkt. Dieser Algorithmus läuft in \(O(V*(V+E))\) auf einer Adjazenzliste.

Gelenkpunkte in linearer Laufzeit finden

Mithilfe der Tiefensuche kann man Gelenkpunkte auch in linearer Laufzeit finden. Während der Tiefensuche werden die Knoten in 3 Kategorien eingeteilt. 1. Weisse Knoten: Der Knoten wurde noch nicht besucht. 2. Graue Knoten: Der Knoten wurde besucht, aber noch nicht alle Kinder des Knotens sind schwarz. Der Knoten wird im Verlauf des Suchpfades des DFS mindestens noch einmal aufgerufen. 3. Schwarze Knoten: Der Knoten und all dessen Kinder des Spannbaums wurden besucht. Der Knoten wird nicht mehr im Verlauf des Suchpfades aufgerufen.

Stelle dir folgende DFS Suche direkt nach dem 4-ten Schritt vor (Blaue Kanten sind abgehakt, gestrichelt blaue Kanten werden noch besucht).

%3 a a b b a->b 1 b->a 8 c c b->c 2 c->a c->b 7 d d c->d 3 e e c->e 5 d->c 4 e->c 6

Zusätzlich gibt es 4 Typen von Kanten des Suchbaumes: 1. Baumkanten (tree edges): Baumkanten sind Kanten, welche kurz bevor sie vom DFS besucht werden einen grauen Knoten mit einem weissen Knoten verbinden. Beispiel beim obigen Graphen c->e. 2. Rückwärtskanten (back edges): Das sind entweder Kanten, welche in die entgegengesetzte Richtung von Baumkanten zeigen (Eine davon wird zum Schluss besucht und wird den Knoten schwarz markieren), oder es sind Kanten welche auf Ahnenknoten zeigen, also zB. einen Grossvaterknoten, Urgrossvaterknoten, etc. Ein Beispiel beim obigen Graphen wäre c->a

Die anderen beiden Kantentypen sind nicht notwendig um den Gelenkknotenalgorithmus zu verstehen, sie sind aber vollständigkeitshalber trotzdem aufgelistet. Das sind die Kanten, die während der DFS Traversierung ausgelassen werden (nur kurz überprüft werden).

  1. Vorwärtskanten (forward edges): Diese Kanten verbinden einen grauen Knoten mit einem schwarzen Knoten, kurz bevor sie überprüft werden. Der graue Knoten ist dabei ein Ahne vom schwarzen Knoten. Beispiel bei diesem Graphen a->c nach Schritt 8.
  2. Kreuzkanten (cross edges): Eine Kreuzkante kann nur bei gerichteten Graphen geschehen und beschäftigt uns für das Gelenkknotenproblem für gerichtete Graphen (strong articulation points). Diese Kanten verbinden einen grauen Knoten mit einem schwarzen Knoten bevor sie überprüft werden. Der graue Knoten ist dabei kein Ahne vom schwarzen Knoten.

Ein etwas übersichtlicheres Beispiel einer DFS Traversierung bei einem gerichtetem Graphen (die Kantennummerierung ist die Traversierungsreihenfolge): image0

Eine einfache Methode festzustellen, ob eine Kante eine Baumkante, eine Vorwärtskante oder eine (Rückwarts-/Kreuzkante) ist, ist in dem man die Traversierungsreihenfolge abspeichert. Der Startknoten erhält die Nummerierung 0 und jeder Knoten, der nun zum ersten Mal besucht wird bei der Tiefensuche, erhält die nächst-höhere Nummerierung. Die DFS Implementierung würde etwa so aussehen:

int numCount = 0;
void dfs(vector<vector<int> > & graph, vector<int> & numbering, int node, int parent) {
    numbering[node] = numCount;
    numCount++;
    for(auto it : graph[node]) {
        if(numbering[it] == -1) dfs(graph,visited,it,node); //tree edge
        else if(numbering[it] == numbering[node]) {
            //this is a loop, this can be ignored
        }
        else if(it == parent) {
            //edge to parent.
        }
        else if(numbering[it] > numbering[node]) {
            //forward edge.
        }
        else { //numbering[node] < numbering[it]
            //backward edge (or cross-edge if directed).
        }
    }
}
  1. Es handelt sich um eine Baumkante, wenn die Nachbarskante noch nicht besucht worden ist.

  2. Es handelt sich um eine Forwärtskante, wenn die Nachbarskante besucht worden ist und eine höhere Nummerierung hat.

  3. Wenn numbering[node] < numbering[it] handelt es sich entweder um eine Kreuzkante oder um eine Rückwärtskante. Wenn der Nachbarsknoten = Vaterknoten ist, darf die Kante ignoriert werden. Sie ist entweder die Kante von der man gekommen ist oder ein Duplikat davon. Duplikate kann man für die Gelenkknotenaufgabe ignorieren!

    Jeder Knoten i ist genau dann ein Gelenkknoten, wenn er: 1. Mindestens zwei Nachbarsknoten besitzt (inklusive der Vaterknoten des DFS), sonst wäre er ein Blattknoten (leaf node). 2. Einer der nicht besuchten Nachbarsknoten ist auf die Existenz des Knotens i angewiesen ist. Es darf also keinen Pfad vom Nachbarsknoten zur Wurzel geben ohne i zu überqueren.

    Die Wurzel / Startknoten / root node (in unserem Falle a) ist eine Ausnahme. Siehe in der grünen Box weiter unten.

Um die zweite Eigenschaft herauszufinden, muss man folgendes in \(O(E+V)\) fertig bringen: Für jeden Knoten X muss abgespeichert werden, welches der Knoten mit der tiefsten Nummerierung ist, welchen man von einem nicht nummerierten Nachkommen im DFS her erreichen kann. Oder in anderen Worten: Für jeden Knoten muss der Knoten mit der tiefsten Nummerierung abgespeichert werden, welcher ohne Backtracking des DFS erreichbar ist! Hat man diesen tiefsten Wert kann man die Eigenschaft 2 unformulieren: Wenn die eigene Nummerierung <= eine tiefste Nummerierung des Knotens ist, ist Eigenschaft 2 erfüllt!

Schau dir dafür dieses Beispiel an:

%3 a a b b a->b 1 b->a 10 d d b->d 4 c c b->c 2 d->b 9 e e d->e 5 e->d 8 f f e->f 6 f->d f->e 7 c->b 3

Gleich nach dem 6-ten Schritt wird hier eine Rückwärtskante entdeckt (f->d). Es könnte sich aber auch um eine Kreuzkante handeln (z.B. f->c). In beiden Fällen wäre es ein Knoten mit tieferer Nummerierung, als man selber. Diese Information muss einfach abgespeichert werden.

Nachdem wir nun das Backtracking zurück zu e durchgeführt haben, testen wir auch hier nocheinmal, ob die Kinder einen Wert mit tieferer Nummerierung haben. f hat eine solche tiefere Nummerierung, weswegen e unmöglich ein Gelenkknoten sein kann. e übernimmt den Wert von f. Nun kommt es zu d. d schaut auch seine Kinder an, doch seine Kinder haben keinen Wert, welcher tiefer ist als sein eigener (Wert von e = Wert von d). Beide Bedingungen für d sind erfüllt, d ist ein Gelenkknoten. Dasselbe gilt für b. c wurde schon vorher abgehackt (bei ihm fehlt schon die erste Bedingung) und schlussendlich bleibt noch die Wurzel a.

Die Wurzel muss nur eine einzige Bedingung erfüllen: Sie muss zwei oder mehr Baumkanten besitzen.

a->c wäre in diesem Beispiel übrigens keine Baumkante mehr, da c durch a->b->c schon grau markiert wäre. So hätte a nur 1 Baumkante & 1 Vorwärtskante und würde die Bedingung nicht erfüllen.

C++ Implementierung (getestet an UVA 315):

vector<int> type; //0 default, 1 articulation point
vector<int> low, number; //-1 unvisited
vector<vector<int> > graph;

int counter = 0, rootNode;
void dfs(int node, int parent) {
    number[node] = low[node] = counter++;
    int rootNeighbors = 0; //only important if node = rootNode
    for(int neighbor : graph[node]) {
        if(number[neighbor] == -1) { //unvisited
            if(node == rootNode) rootNeighbors++;
            dfs(neighbor, node);
            if(low[neighbor] >= number[node]) type[node] = 1;
            //if(low[neighbor] > number[node]) the edge to the neighbor must be a bridge!
            low[node] = MIN(low[node], low[neighbor]);
        }
        else if(neighbor != parent) { //this must be a back edge
            low[node] = MIN(low[node], number[neighbor]);
        }
    }
    if(node == rootNode && rootNeighbors > 1) type[rootNode] = 1;
    else if(node == rootNode) type[rootNode] = 0;
}

Brücken berechnen Brücken kann man mit dem genau gleichen Algorithmus finden, nur muss man wenn man eine Kante im DFS betrachtet überprüfen ob low[neighbor] > number[node]