Robert Sedgewick: Algorithmen

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


29. Elementare Algorithmen für Graphen



Ausblick

In den nachfolgenden Kapiteln betrachten wir eine große Zahl von Algorithmen für Graphen, die weitgehend darauf abzielen, Eigenschaften des Zusammenhangs sowohl gerichteter als auch ungerichteter Graphen zu bestimmen. Hierbei handelt es sich um grundlegende Algorithmen für die Verarbeitung von Graphen, doch stellen sie nur eine Einführung in das Gebiet der Graphen-Algorithmen dar. Es sind viele interessante und nützliche Algorithmen entwickelt worden, die über den Rahmen dieses Buches hinausgehen würden, und es sind viele interessante Probleme untersucht worden, für die noch keine guten Algorithmen gefunden wurden.

Einige sehr effiziente Algorithmen wurden entwickelt, die viel zu kompliziert sind, als daß sie hier vorgestellt werden könnten. Zum Beispiel ist es möglich, auf effiziente Weise zu bestimmen, ob ein Graph in der Ebene gezeichnet werden kann, ohne daß sich irgendwelche Linien schneiden, oder ob dies nicht möglich ist. Dieses Problem wird das Problem der Planarität (Ebenheit) genannt, und es war kein effizienter Algorithmus für seine Lösung bekannt, bis R. E. Tarjan 1974 einen genialen (jedoch sehr schwierigen) Algorithmus zur Lösung des Problems in linearer Zeit entwickelte, bei dem Tiefensuche benutzt wird.

Einige mit Graphen zusammenhängende Probleme, die in natürlicher Weise entstehen und sich leicht formulieren lassen, scheinen sehr kompliziert zu sein, und es sind keine guten Algorithmen für ihre Lösung bekannt. Beispielsweise ist kein effizienter Algorithmus bekannt, mit dem der mit minimalen Kosten verbundene Weg bestimmt werden kann, bei dem jeder Knoten in einem gewichteten Graph besucht wird. Dieses Problem, das das Problem des Handelsreisenden (traveling salesman problem) genannt wird, gehört zu einer großen Klasse von komplizierten Problemen, die wir in Kapitel 45 ausführlicher erörtern werden. Die meisten Spezialisten sind der Meinung, daß für diese Probleme keine effizienten Algorithmen existieren.

Für andere Graphen betreffende Probleme können effiziente Algorithmen vorhanden sein, obwohl noch keine entdeckt worden sind. Ein Beispiel hierfür ist das Problem der Isomorphie von Graphen: Zu bestimmen ist, ob zwei Graphen durch Umbenennung von Knoten zu identischen Graphen gemacht werden können. Für viele spezielle Typen von Graphen sind effiziente Algorithmen für dieses Problem bekannt, doch das allgemeine Problem ist noch ungelöst.

Kurz gesagt, es existiert ein breites Spektrum von Problemen und Algorithmen, die Graphen betreffen. Wir können sicher nicht erwarten, daß wir jedes auftretende Problem lösen können, und selbst mit manchen Problemen, die einfach zu sein scheinen, kämpfen die Experten noch immer vergeblich. Doch viele relativ einfache Probleme treten sehr häufig auf, und die Algorithmen für Graphen, die wir untersuchen wollen, sind für eine Vielzahl von Anwendungen von großem Nutzen.


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