Robert Sedgewick: Algorithmen

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


29. Elementare Algorithmen für Graphen



Sehr viele Probleme lassen sich in natürlicher Weise unter Benutzung von Objekten und Verbindungen zwischen ihnen formulieren. Wenn zum Beispiel eine Karte der Fluglinien des östlichen Teils der USA gegeben ist, könnten uns Fragen interessieren wie: »Was ist der schnellste Weg von Providence nach Princeton?« Oder es könnte sein, daß Geld für uns wichtiger ist als Zeit und wir nach dem billigsten Weg suchen, um von Providence nach Princeton zu gelangen. Um solche Fragen zu beantworten, benötigen wir lediglich Informationen über Verbindungen (Fluglinien) zwischen Objekten (Städten).

Elektrische Schaltungen sind ein weiteres offensichtliches Beispiel, wo Verbindungen zwischen Objekten eine zentrale Rolle spielen. Schaltelemente, wie etwa Transistoren, Widerstände und Kondensatoren, sind in komplizierter Weise miteinander verdrahtet. Solche Schaltungen können mit Hilfe eines Computers dargestellt und verarbeitet werden, um sowohl einfache Fragen von der Art »Ist alles miteinander verbunden?« als auch komplizierte Fragen wie »Wenn diese Schaltung hergestellt ist, wird sie funktionieren?« zu beantworten. Hierbei hängt die Antwort auf die erste Frage nur von den Eigenschaften der Verbindungen (Drähte) ab, während die Antwort auf die zweite genaue Informationen sowohl über die Drähte als auch die Objekte, die durch sie verbunden sind, erfordert.

Ein drittes Beispiel ist das Scheduling, wobei die Objekte auszuführende Aufgaben sind, zum Beispiel in einem Fertigungsprozeß, und die Verbindungen angeben, welche Aufgaben vor anderen ausgeführt werden sollten. Hierbei könnte uns die Antwort auf Fragen wie »Wann sollte jede Aufgabe ausgeführt werden?« interessieren.

Ein Graph ist ein mathematisches Objekt, das solche Situationen exakt modelliert. Im vorliegenden Kapitel wollen wir einige grundlegende Eigenschaften von Graphen betrachten, und in den nachfolgenden Kapiteln untersuchen wir eine Vielzahl von Algorithmen zur Beantwortung von Fragen der oben gestellten Art.

Tatsächlich haben wir es in weiter zurückliegenden Kapiteln bereits mit Graphen zu tun gehabt. Verkettete Datenstrukturen sind dem Wesen nach Darstellungen von Graphen, und einige der Algorithmen, die wir für die Verarbeitung von Graphen betrachten werden, sind Algorithmen ähnlich, die wir bereits für die Verarbeitung von Bäumen und anderen Strukturen kennengelernt haben. Zum Beispiel wurden die endlichen Automaten in den Kapiteln 19 und 20 mit Hilfe von Graphen dargestellt.

Die Graphentheorie ist ein wichtiger Zweig der kombinatorischen Mathematik, der seit Jahrhunderten Gegenstand intensiver Forschung ist. Viele wichtige und nützliche Eigenschaften von Graphen wurden bewiesen, doch viele komplizierte Probleme sind noch zu lösen. Hier können wir nur die Oberfläche dessen streifen, was über Graphen bekannt ist, in einem Ausmaß, der für das Verständnis der grundlegenden Algorithmen ausreichend ist.

Wie bei vielen anderen der von uns untersuchten Problemkreise wurde auch bei Graphen erst in jüngster Zeit damit begonnen, sie von einem algorithmischen Standpunkt aus zu betrachten. Auch wenn einige der grundlegenden Algorithmen sehr alt sind, sind viele interessante Algorithmen erst im Laufe der letzten zehn Jahre entdeckt worden. Selbst triviale Algorithmen für Graphen führen zu interessanten Programmen, und die nichttrivialen Algorithmen, die wir kennenlernen werden, gehören zu den elegantesten und interessantesten (wenn auch schwer verständlichen) bekannten Algorithmen.


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