Dualität von Suchstrategien auf planaren Graphen

Abstract

Ein wichtiger Teil der Graphentheorie ist die Untersuchung von Strategien einen Graphen zu durchlaufen. Wir werden uns in dieser Arbeit vor allem mit zwei der bekanntesten Durchlaufstrategien durch Graphen beschäftigen, der Breiten- und der Tiefensuche.Kapitel 2 enthält eine Einführung in einige wichtige Grundbegriffe der Graphentheorie. Diese Einführung beschränkt sich im wesentlichen auf die benötigten Definitionen, für einen tieferen Einblick in die Graphtheorie sei auf die angegebene Literatur verwiesen.In Kapitel 3 werden Graphsuche allgemein und die schon erwähnten Tiefen- und Breitensuche definiert. Einige Anwendungsbeispiele sollen aufzeigen, daß Suchstrategien in vielen Lösungsalgorithmen eine zentrale Rolle übernehmen. Der zweite Teil des Kapitels führt den Begriff der dualen Suche ein und gibt einen ersten Ausblick auf die weiteren Forschungen.Die Kapitel 4 und 5 umfassen die zentralen Aussagen der Arbeit. Zu Beginn des 4. Kapitels werden wir die Struktur eines planaren Graphen betrachten. Danach werden Dualitätseigenschaften von Tiefen- und Breitensuche aufgezeigt. Zwei Suchen sind dual, wenn die Suche auf dem Dualgraphen die Dualkanten in der gleichen Reihenfolge aufnimmt, wie die andere Suche die Kanten des Originalgraphen. Es wird eine modifizierte Breitensuche vorgestellt, welche dual zur Tiefensuche arbeitet. Ebenso führen wir eine modifizierte Tiefensuche ein, die dual ist zur Breitensuche.Das 5. Kapitel beschäftigt sich mit der Dualität des Tiefensuchbaums. Wir werden zeigen, daß die Dualkanten der Nichtbaumkanten im Dualgraphen wiederum einen Tiefensuchbaum bilden. Außerdem läßt sich die Kantenaufnahmereihenfolge der Tiefensuche, die diesen Tiefensuchbaum im Dualgraphen erzeugt aus dem Tiefensuchbaum im Originalgraphen rekonstruieren.Die Ergebnisse der Arbeit werden in Kapitel 6 noch einmal kurz zusammengefaßt.