Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


30. Zusammenhang



Zweifacher Zusammenhang

Es ist manchmal von Nutzen, mehr als einen Weg zwischen Punkten in einem Graph vorzusehen, so daß bei möglichen Ausfällen an den Verbindungsstellen (Knoten) ein Ausweg vorhanden ist. So können wir sogar dann von Providence nach Princeton fliegen, wenn New York zugeschneit ist, indem wir stattdessen über Philadelphia fliegen. Die wichtigsten Verbindungen in einem integrierten Schaltkreis sind oft zweifach zusammenhängend, so daß der Rest der Schaltung noch funktionieren kann, wenn eine Komponente ausfällt. Eine andere Anwendung (nicht sehr realistisch, doch eine natürliche Veranschaulichung der Idee) wäre, sich eine Situation im Krieg vorzustellen, wo wir es so einrichten können, daß ein Feind mindestens zwei Stationen bombardieren muß, um unsere Eisenbahnlinien zu unterbrechen.

Ein Gelenkpunkt in einem zusammenhängenden Graph ist ein Knoten, der, wenn er gelöscht würde, den Graph in zwei oder mehr Teile zerbrechen lassen würde. Ein Graph ohne Gelenkpunkte wird zweifach zusammenhängend genannt. In einem zweifach zusammenhängenden Graph ist jedes Paar von Knoten durch zwei verschiedene Pfade verbunden. Ein Graph, der nicht zweifach zusammenhängend ist, läßt sich in zweifach zusammenhängende Komponenten zerlegen, Mengen von Knoten, die sich untereinander über zwei unterschiedliche Pfade erreichen lassen.

Abbildung 30.2 zeigt einen Graph, der zusammenhängend, aber nicht zweifach zusammenhängend ist. (Dieser Graph läßt sich aus dem Graph aus dem vorangegangenen Kapitel erzeugen, indem die Kanten GC, GH, JG und LG hinzugefügt werden. In unseren Beispielen wollen wir annehmen, daß diese vier Kanten am Ende der Eingabe in der angegebenen Reihenfolge hinzugefügt werden, so daß (zum Beispiel) die Adjazenzlisten denen in Abbildung 29.4 ähnlich sind, mit acht neuen Einträgen in den Listen, die die vier neuen Kanten widerspiegeln.) Die Gelenkpunkte dieses Graphen sind die Knoten A (da er B mit dem restlichen Graph verbindet), H (da er I mit dem restlichen Graph verbindet), J (da er K mit dem restlichen Graph verbindet) und G (da der Graph in drei Teile zerfallen würde, wenn G gelöscht würde). Es gibt sechs zweifach zusammenhängende Komponenten: {A C G D E F}, {G J L M} und die einzelnen Knoten B, H, I und K.

Abbildung 30.2
Abbildung 30.2 Ein nicht zweifach zusammenhängender Graph.

Die Bestimmung der Gelenkpunkte erweist sich als eine einfache Erweiterung der Tiefensuche. Um uns davon zu überzeugen, betrachten wir den Tiefensuchbaum für diesen Graph, der in Abbildung 30.3 dargestellt ist. Das Löschen des Knotens E führt nicht zu einer Trennung des Graphen, da sowohl G als auch D gestrichelte Linien besitzen, die auf eine Stelle oberhalb von E zeigen, womit sie andere Pfade von diesen Knoten zu F (dem Vorgänger von E im Baum) angeben. Andererseits führt das Löschen von G zu einem Zerfall des Graphen, da es keine solchen alternativen Pfade von L oder H zu E (dem Vorgänger von G) gibt.

Abbildung 30.3
Abbildung 30.3 Tiefensuche für zweifachen Zusammenhang.

Ein Knoten x ist kein Gelenkpunkt, falls es für jeden Nachfolger y einen weiter unten im Baum befindlichen Knoten gibt, der (über eine gestrichelte Verbindung) mit einem oberhalb von x im Baum befindlichen Knoten verbunden ist, womit eine andere Verbindung von x nach y vorhanden ist. Dieser Test ist nicht unmittelbar auf die Wurzel des Tiefensuchbaumes anwendbar, da es hier keine »weiter oben im Baum befindlichen« Knoten gibt. Die Wurzel ist ein Gelenkpunkt, wenn sie zwei oder mehr Nachfolger besitzt, da der einzige Pfad, der Nachfolger der Wurzel verbindet, über die Wurzel führt. Diese Tests lassen sich leicht in die Tiefensuche einbauen, indem die Prozedur des Besuchens von Knoten in eine Funktion verwandelt wird, die den höchsten Punkt im Baum (kleinster Wert von val) zurückgibt, der während der Suche angetroffen wird:

    function visit(k: integer): integer;
      var t: link;
          m,min: integer;
      begin
      id:=id+1; val[k]:=id; min:=id;
      t:=adj[k];
      while t<>z do
        begin
        if val[t^.v]=0 then
          begin
          m:=visit(t^.v);
          if m<min then min:=m;
          if m>=val[k] then write(name(k));
          end
        else if val[t^.v]<min then min:=val[t^.v];
        t:=t^.next
        end
      visit:=min;
      end;

Diese Prozedur bestimmt rekursiv den höchsten Punkt im Baum, der (über eine gestrichelte Linie) von irgendeinem Nachfolger des Knotens k erreicht werden kann, und verwendet diese Information, um zu bestimmen, ob k ein Gelenkpunkt ist. Normalerweise erfordert diese Berechnung einfach einen Test, ob sich der von einem Nachfolger aus erreichbare minimale Wert weiter oben im Baum befindet. Wir benötigen jedoch einen zusätzlichen Test, um zu bestimmen, ob k die Wurzel eines Tiefensuchbaumes ist (oder, was dazu äquivalent ist, ob dies für die zusammenhängende Komponente, die k enthält, der erste Aufruf von visit ist), da wir das gleiche rekursive Programm für beide Fälle verwenden. Dieser Test wird außerhalb des rekursiven visit ordnungsgemäß ausgeführt und erscheint daher in dem obigen Programm nicht.

Eigenschaft 30.1 Die zweifach zusammenhängenden Komponenten eines Graphen können in linearer Zeit gefunden werden.

Obwohl das obige Programm einfach die Gelenkpunkte ausdruckt, läßt es sich leicht dahingehend erweitern (wie wir es für zusammenhängende Komponenten getan haben) daß es eine zusätzliche Verarbeitung der Gelenkpunkte und zweifach zusammenhängenden Komponenten vornimmt. Da es sich um eine Tiefensuchprozedur handelt, ist die Laufzeit proportional zu V + E. (Ein ähnliches Programm, das auf einer Adjazenzmatrix beruht, würde in O(V2) Schritten ablaufen.) w.z.b.w.

Neben den oben erwähnten Anwendungen, wo der zweifache Zusammenhang benutzt wurde, um die Zuverlässigkeit zu erhöhen, kann er von Nutzen sein, wenn umfangreiche Graphen in überschaubare Teile zerlegt werden sollen. Es ist offensichtlich, daß ein sehr umfangreicher Graph in vielen Anwendungsfällen verarbeitet werden kann, indem eine zusammenhängende Komponente nach der anderen verarbeitet wird; es ist etwas weniger offensichtlich, doch gelegentlich ebenso nützlich, daß ein Graph manchmal verarbeitet werden kann, indem eine zweifach zusammenhängende Komponente nach der anderen verarbeitet wird.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]