Graphenalgorithmen

Ein ungerichteter Graph heißt zusammen­hängend, wenn es von jedem Knoten zu jedem anderen Knoten mindestens einen Weg gibt. In ähnlicher Weise lässt sich der zweifache Zusammenhang charakterisieren. Ein ungerichteter Graph heißt zweifach zusammen­hängend, wenn es von jedem Knoten zu jedem anderen Knoten mindestens zwei disjunkte Wege gibt, also Wege, die außer Anfangs- und Endknoten keine Knoten gemeinsam haben.

Ist ein ungerichteter Graph nicht zusammen­hängend, so besteht er aus mehreren Zusammenhangs­komponenten, also Teilgraphen, die jeweils für sich zusammen­hängend sind und die zusammen­genommen den ganzen Graphen ergeben. Ist der Graph nicht zweifach zusammen­hängend, so besteht er ganz entsprechend aus mehreren Zweifach-Zusammenhangs­komponenten oder Blöcken.

Wie die (einfachen) Zusammenhangs­komponenten lassen sich auch die Zweifach-Zusammenhangs­komponenten mit Hilfe der Tiefensuche berechnen.

Tiefensuche

Gegeben ist ein nichtleerer zusammen­hängender ungerichteter Graph. Mit Hilfe der Tiefensuche (depth-first search) lässt sich der Graph systematisch durchlaufen. In dieser Version der Tiefensuche werden die Knoten entsprechend der Reihenfolge nummeriert, in der sie durchlaufen werden.

Zu Beginn werden alle Knoten des Graphen G mit der Zahl 0 markiert und es wird ein Startknoten v gewählt. Die globale Zählvariable i wird mit 0 initialisiert.

Funktion depthFirstSearch(v)

Methode:

1. setze i = i+1
2. markiere den Knoten v mit der Nummer i
3. für alle Nachbarknoten w von v wiederhole
1. wenn w mit 0 markiert ist dann
1. depthFirstSearch(w)

Die Markierung i, die ein Knoten v im Verlauf des Verfahrens erhält, wird als der Tiefen­such­index (depth-first index) dfi(v) bezeichnet.

Bild 1: Tiefensuche in einem Graphen

Bild 1a zeigt als Beispiel einen Graphen mit Knotenmenge { a, ..., f }. Zu Beginn sind alle Knoten mit 0 markiert. Als Startknoten wird der Knoten a gewählt; dieser wird mit dem Tiefen­such­index i = 1 markiert. Mit dem Nachbarn b wird fortgefahren; dieser erhält die Markierung i = 2. Werden nun die Nachbarn von b betrachtet, so hat a bereits eine Markierung  > 0, also wird mit dem nächsten Nachbarn c fortgefahren; dieser erhält die Markierung i = 3. Bild 1b zeigt diese Situation. Die Kanten, die zu den jeweils neu markierten Knoten führen, sind fett gezeichnet.

Im weiteren Verlauf des Verfahrens wird festgestellt, dass Knoten c keine Nachbarn hat, die mit 0 markiert sind. Der entsprechende Aufruf von depthFirstSearch ist daher hier abge­schlossen und es wird mit dem nächsten Nachbarn des Knotens b fortgefahren, also mit Knoten d.

Vom Knoten e schließlich ist wiederum kein Knoten mehr erreichbar, der mit 0 markiert ist. Hier enden nun alle rekursiven Aufrufe von depthFirstSearch mit Ausnahme des ersten, denn am Knoten a wird festgestellt, dass der Nachbar f noch mit 0 markiert ist. Nachdem dieser mit dem Tiefen­such­index i = 6 markiert ist, endet das Verfahren. Bild 1c zeigt die Situation am Ende. Alle Knoten sind mit einem Tiefen­such­index  > 0 markiert.

Tiefensuchbaum

Die Kanten eines ungerichteten Graphen sind nichts anderes als jeweils zwei gerichtete Kanten, die in entgegen­gesetzte Richtungen zeigen. Unter dieser Sichtweise bilden die Knoten des Graphen zusammen mit den Kanten, die im Verlauf der Tiefensuche zu den jeweils neu markierten Knoten führen, einen gerichteten Baum mit dem Startknoten als Wurzel. Dieser Baum wird als Tiefen­such­baum D des Graphen bezeichnet. Die Kanten des Graphen, die zu diesem Tiefen­such­baum gehören, heißen daher in diesem Zusammenhang Baumkanten. Die Baumkanten sind immer vom Knoten mit dem kleineren zum Knoten mit dem größeren Tiefen­such­index gerichtet. Die entsprechenden entgegen­gesetzt gerichteten Kanten nennen wir reverse Baumkanten. Die ver­bleibenden Kanten des Graphen heißen Vorwärts- bzw. Rückwärts­kanten, je nach dem, ob sie in Richtung vom kleineren zum größeren Tiefen­such­index führen oder umgekehrt. Ein Teilbaum des Tiefen­such­baums, der an einem Knoten v beginnt, wird mit D(v) bezeichnet.

Bild 2 zeigt einen Ausschnitt aus Bild 1c mit einer Baumkante, einer reversen Baumkante, einer Vorwärts- und einer Rückwärts­kante.

Es ist also nicht möglich, dass eine Vorwärts­kante quer im Tiefen­such­baum verläuft, wie in Bild 3 angedeutet; eine solche Kante gibt es bei einem Tiefen­such­baum nicht.

Die Folgerung ist, dass jede Rückwärts­kante zu einem Vorgänger im Tiefen­such­baum führt.

Zweifach zusammenhängende Komponenten (Blöcke)

Ein Graph, der nur aus einem Knoten besteht, ist zweifach zusammen­hängend, denn er hat keine anderen Knoten. Ein Graph mit zwei Knoten u und v, die durch eine Kante verbunden sind, ist ebenfalls zweifach zusammen­hängend. Denn es gibt die beiden Wege (u, v) und (u, v). Diese sind zwar gleich, aber dennoch disjunkt, denn sie enthalten außer Anfangs- und Endknoten keine gemeinsamen Knoten.

Wird aus einem zusammen­hängenden ungerichteten Graphen ein Knoten v entfernt (mitsamt seiner Kanten), so gibt es zwei Möglich­keiten: Entweder bleibt der Graph zusammen­hängend, oder er zerfällt in mehrere Zusammenhangs­komponenten. Ein solcher Knoten v, der den Graphen zerfallen lässt, wenn er entfernt wird, heißt Zerfällungs­knoten (cut point).¹)

Bild 4 zeigt einen zusammen­hängenden ungerichteten Graphen. Der Knoten c in der Mitte ist ein Zerfällungs­knoten.

Die Blöcke und Zerfällungs­knoten eines Graphen lassen sich mithilfe der Tiefensuche bestimmen.

Wir nennen einen Knoten v einen Anführer eines Blocks (block leader), wenn v im Tiefen­such­baum einen direkten Nachfolger w hat, von dessen Teilbaum D(w) keine Rückwärts­kante zu einem Vorgänger u von v führt. Die Knoten von D(w) können dann von anderen Knoten aus nur über den Knoten v erreicht werden. Wenn D(w) keine Anführer von weiteren Blöcken enthält, bildet v zusammen mit den Knoten von D(w) einen Block.

Ein Knoten c ist ein Zerfällungs­knoten, wenn er Anführer eines Blocks ist und außerdem noch zu einem anderen Block gehört. Stets ist der Startknoten Anführer eines Blocks. Er ist Zerfällungs­knoten, wenn er außerdem noch Anführer eines anderen Blocks ist. In einem zweifach zusammen­hängenden Graphen ist nur der Startknoten Anführer eines Blocks.

Implementierung

Der folgende Algorithmus bestimmt die Blöcke und Zerfällungs­knoten eines zusammen­hängenden, ungerichteten Graphen mithilfe der Tiefensuche [AHU 74].

Jedem Knoten v wird zusätzlich zum Tiefen­such­index dfi(v) ein Wert min(v) zugeordnet. Dieser Wert wird mit dfi(v) initialisiert. Er wird in zwei Fällen aktualisiert:

1. wenn eine Rückwärts­kante (v, w) gefunden wird; dann wird min(v) auf dfi(w) gesetzt, falls min(v) dadurch kleiner wird (Aufruf von updateMin am Ende des Else-Teils); ²)
2. wenn eine reverse Baumkante (w, v) durchlaufen wird; dann wird min(v) auf min(w) gesetzt, falls min(v) dadurch kleiner wird (Aufruf von updateMin am Ende des If-Teils).

Somit ist min(v) der minimale Tiefen­such­index aller Vorgänger von v, mit denen v oder ein Nachfolger von v durch eine Rückwärts­kante verbundenen sind.

Ein Knoten v wird als Anführer eines Blocks identifiziert, wenn er einen direkten Nachfolger w hat, für den min(w) größer oder gleich dfi(v) ist. Dies bedeutet nämlich, dass weder von w noch von einem Nachfolger von w eine Rückwärts­kante zu einem Vorgänger von v führt.

Die folgende Funktion findBlocks hat dieselbe rekursive Struktur wie depthFirstSearch. Jedem Knoten v ist zusätzlich zum Tiefen­such­index dfi(v) der Wert min(v), der Vorgänger pre(v) im Tiefen­such­baum, sowie eine Liste der Nummern der Blöcke, denen v angehört, zugeordnet. Mit assignBlockNumber(v, bln) wird dem Knoten v die Blocknummer bln zugeordnet.

Mit einem NeighbourIterator werden die Nachbarn eines jeweiligen Knotens der Reihe nach durchlaufen.

Ferner wird ein globaler Stack stk verwendet, in dem die durch­laufenen Knoten des Tiefen­such­baums gespeichert werden. Wird ein Anführer eines Blocks gefunden, so befinden sich die Knoten des betreffenden Blocks als oberste im Stack; sie werden vom Stack entfernt und als zu dem Block gehörig gekenn­zeichnet.

Als Zerfällungs­knoten werden am Ende diejenigen Knoten identifiziert, die mehreren Blöcken angehören.

Der angegebene Algorithmus funktioniert nicht mit einem Graphen, der nur aus einem isolierten Knoten besteht. Da der Knoten keinen Nachbarn hat, wird diesem Knoten kein Block zugeordnet. Es ist eine zusätzliche Abfrage erforderlich, ob der Graph nur aus einem Knoten besteht.

Mit einer ähnlichen Vorgehens­weise wie bei der Berechnung der Zusammenhangs­komponenten lassen sich auch für beliebige, möglicher­weise nicht zusammen­hängende Graphen die Zerfällungs­knoten und Blöcke ihrer Zusammenhangs­komponenten bestimmen. Dies geschieht, indem die Tiefensuche gegebenen­falls mehrmals durchgeführt wird, beginnend jeweils bei einem Knoten, der noch mit dem Tiefen­such­index 0 markiert ist.