|
Folien
Übungen
Programme
Bilder
 Zurück
|
Multimedia-Ergänzungen zum Buch: Algorithmen und Datenstrukturen, Kapitel 8: Graphenalgorithmen
|
|
|
Wie komme
ich am schnellsten von Freiburg nach Königsberg, dem heutigen Kaliningrad
? Wie komme ich am billigsten von Freiburg nach Königsberg? Wie
transportiere ich ein Gut am billigsten von mehreren Anbietern zu
mehreren Nachfragern? Wie ordne ich die Arbeitskräfte meiner Firma am
besten denjenigen Tätigkeiten zu, für die sie geeignet sind? Wann kann
ich frühestens mit meinem Hausbau fertig sein, wenn die einzelnen
Arbeiten in der richtigen Reihenfolge ausgeführt werden? Wie besuche ich
alle meine Kunden mit einer kürzestmöglichen Rundreise? Welche
Wassermenge kann die Kanalisation in Freiburg höchstens verkraften? Wie
muß ein Rundweg durch Königsberg aussehen, auf dem ich jede Brücke über
den Pregel genau einmal überquere und am Schluß zum Ausgangspunkt zurückkomme?
Diese und viele andere Probleme lassen sich als Probleme in Graphen formulieren
und mit Hilfe von Graphenalgorithmen lösen.
In einem Graphen wird dabei die wesentliche Struktur des Problems, befreit
von unbedeutenden Nebenaspekten, repräsentiert.
Abbildung1
zeigt einen (verzerrten) Ausschnitt aus dem Stadtplan von
Königsberg, Abbildung2
zeigt den dazugehörigen Graphen. Das Wesentliche am Königsberger Brückenproblem
ist die Verbindungsstruktur der einzelnen Stadtteile gemäß den sieben Brücken.
Jeder Stadtteil ist im Graphen durch einen Punkt, genannt Knoten,wiedergegeben;
eine Verbindung ist eine Linie von einem Knoten zu einem anderen Knoten, genannt
Kante. In unserem Beispiel entspricht eine Verbindung gerade einer Brücke.
Bereits 1736 löste Euler das Königsberger Brückenproblem. Er stellte
fest, dass der gewünschte Rundweg nicht möglich ist.
Im Laufe dieses Kapitels werden wir Beispiele für andere Graphenprobleme und
entsprechende Lösungsalgorithmen kennenlernen. Insbesondere kann man sich
vorstellen, dass Verbindungen --- anders als beim Königsberger Brückenproblem
--- mit einer Richtung ausgezeichnet sind und in Gegenrichtung nicht
benutzt werden dürfen, wie etwa Einbahnstraßen in einer Stadt. Ähnliches
gilt bei der Kanalisation oder beim Hausbau.Betrachten wir zunächst
solche Graphen.
Ein gerichteter Graph G=(V,E) (englisch: digraph) besteht
aus einer Menge V Knoten (englisch: vertices) und einer
Menge E von Pfeilen (englisch:edges, arcs).
Wir nennen v den Anfangs- und v' den Endknoten
des Pfeils (v,v'); v und v' heißen auch adjazent;
v (und ebenso v') heißt mit e inzident; ebenso nennen wir
e inzident mit v und v'. Wir werden Knoten eines
Graphen stets als Punkte, Pfeile als Verbindungslinien mit einer auf den Endknoten gerichteten Pfeilspitze
darstellen. Wir beschränken uns auf endliche Mengen von Knoten und
Pfeilen, also auf endliche Graphen; weil E eine Menge ist,
kann in diesen Graphen jeder Pfeil höchstens einmal auftreten.
|
|
Bei Fragen zu
dem Inhalt des Buches senden Sie bitte eine Email an ad-buch@informatik.uni-freiburg.de.
|
|