Robert Sedgewick: Algorithmen

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


29. Elementare Algorithmen für Graphen



Glossar

Mit Graphen ist eine umfangreiche Nomenklatur verknüpft. Die meisten Begriffe haben sehr einfache Definitionen, und es ist zweckmäßig, sie an dieser Stelle zusammenzufassen, selbst dann, wenn wir einige von ihnen erst später benutzen werden.

Ein Graph ist eine Menge von Knoten (oder Ecken) und Kanten. Knoten sind einfache Objekte, die Namen und andere Eigenschaften haben können; eine Kante ist eine Verbindung zwischen zwei Knoten. Man kann einen Graph zeichnen, indem man die Knoten durch Punkte markiert und diese durch Linien verbindet, die die Kanten darstellen. Dabei darf man jedoch nicht vergessen, daß der Graph unabhängig von der Darstellung definiert ist. Zum Beispiel stellen die beiden Zeichnungen in Abbildung 29.1 denselben Graph dar. Wir definieren diesen Graph, indem wir sagen, daß er aus der Menge von Knoten A B C D E F G H I J K L M und der Menge von Kanten AG AB AC LM JM JL JK ED FD HI FE AF GE zwischen diesen Knoten besteht.

Für gewisse Anwendungen, wie etwa das obige Beispiel mit den Fluglinien, ist es möglicherweise nicht sinnvoll, die Knoten wie in Abbildung 29.1 anders anzuordnen. Doch für andere Anwendungen, wie die obengenannte Anwendung bei elektrischen Schaltungen, ist es am besten, sich nur auf die Kanten und Knoten zu konzentrieren, unabhängig von irgendeiner speziellen geometrischen Anordnung. Und für wieder andere Anwendungen wie etwa die endlichen Automaten in den Kapiteln 19 und 20 ist niemals eine spezielle geometrische Anordnung von Knoten erforderlich. Der Zusammenhang zwischen Algorithmen für Graphen und geometrischen Problemen wird in Kapitel 31 noch eingehender erörtert. Einstweilen konzentrieren wir uns auf »reine« Algorithmen für Graphen, die einfache Mengen von Kanten und Knoten verarbeiten.

Abbildung 29.1
Abbildung 29.1 Zwei Darstellungen des gleichen Graphen.

Ein Pfad oder Weg von Knoten x zu Knoten y in einem Graph ist eine Liste von Knoten, in der aufeinanderfolgende Knoten durch Kanten im Graph miteinander verbunden sind. Zum Beispiel ist in Abbildung 29.1 BAFEG ein Pfad von B nach G. Ein Graph ist zusammenhängend, wenn von jedem Knoten zu jedem anderen Knoten im Graph ein Pfad existiert. Man kann sich dies so vorstellen, daß, wenn die Knoten physische Objekte und die Kanten Verbindungsfäden dazwischen wären, ein zusammenhängender Graph in einem Stück zusammenbleiben würde, wenn man ihn an irgendeinem Knoten hochheben würde. Ein Graph, der nicht zusammenhängend ist, setzt sich aus zusammenhängenden Komponenten zusammen; beispielsweise besitzt der Graph in Abbildung 29.1 drei zusammenhängende Komponenten. Ein einfacher Pfad ist ein Pfad, auf dem sich kein Knoten wiederholt. (Zum Beispiel ist BAFEGAC kein einfacher Pfad.) Ein Zyklus ist ein einfacher Pfad, mit der Ausnahme, daß der erste und der letzte Knoten identisch sind (ein Pfad von einem Punkt zurück zu sich selbst); der Pfad AFEGA ist ein Zyklus.

Ein Graph ohne Zyklen wird Baum genannt (siehe Kapitel 4). Eine Gruppe nicht zusammenhängender Bäume wird Wald genannt. Ein Spannbaum eines Graphen ist ein Teilgraph, der alle Knoten enthält, doch nur so viele von den Kanten, daß er einen Baum bildet. Zum Beispiel bilden die Kanten AB AC AF FD DE EG einen Spannbaum für die große Komponente des Graphen in Abbildung 29.1, und Abbildung 29.2 zeigt einen größeren Graph und einen seiner Spannbäume.

Abbildung 29.2
Abbildung 29.2 Ein umfangreicher Graph und ein Spannbaum für diesen Graph.

Beachten Sie, daß die Hinzufügung einer Kante zu diesem Baum zu einem Zyklus führt (da zwischen den beiden Knoten, die diese Kante verbindet, bereits ein Pfad vorhanden ist). Weiterhin hat, wie wir in Kapitel 4 gesehen haben, ein Baum mit V Knoten genau V - 1 Kanten. Falls ein Graph mit V Knoten weniger als V - 1 Kanten hat, kann er nicht zusammenhängend sein. Falls er mehr als V - 1 Kanten hat, muß er einen Zyklus enthalten. (Doch falls er genau V - 1 Kanten hat, muß es sich nicht unbedingt um einen Baum handeln.)

Wir wollen die Anzahl der Knoten in einem gegebenen Graph mit V und die Anzahl der Kanten mit E bezeichnen. Wie man leicht sieht, kann E jeden beliebigen Wert zwischen 0 und V(V - 1)/2 haben. Graphen, in denen alle Kanten vorhanden sind, werden vollständige Graphen genannt; Graphen mit relativ wenigen Kanten (zum Beispiel weniger als V log V) werden licht genannt; Graphen, bei denen relativ wenige der möglichen Kanten fehlen, werden dicht genannt.

Die grundlegende Abhängigkeit der Graphentopologie von zwei Parametern bewirkt, daß die vergleichende Untersuchung von Algorithmen für Graphen etwas komplizierter ist als viele andere Algorithmen, die wir betrachtet haben, da mehr Möglichkeiten entstehen. Zum Beispiel könnte es sein, daß ein Algorithmus ungefähr V2 Schritte benötigt, während ein anderer Algorithmus für das gleiche Problem (E + V) log E Schritte benötigt. Der zweite Algorithmus wäre für lichte Graphen besser geeignet, für dichte Graphen wäre dagegen der erste vorzuziehen.

Graphen der bisher definierten Art werden ungerichtete Graphen genannt; dies ist der einfachste Graphentypus. Wir werden auch kompliziertere Graphentypen betrachten, bei denen mit den Knoten und Kanten mehr Information verknüpft ist. In gewichteten Graphen werden jeder Kante ganze Zahlen (Gewichte) zugewiesen, um zum Beispiel Entfernungen oder Kosten darzustellen. In gerichteten Graphen sind Kanten »Einbahnstraßen«: Eine Kante kann von x nach y führen, aber nicht von y nach x. Gerichtete gewichtete Graphen werden manchmal Netzwerke genannt. Wie wir feststellen werden, führt die in gewichteten und gerichteten Graphen enthaltene zusätzliche Information dazu, daß ihre Handhabung etwas schwieriger ist als die von einfachen ungerichteten Graphen.


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