Die Idee für diese Arbeit stammt von Prof. Armin Mikler 2007, der nach einem (möglichst deterministischen) Algorithmus suchte, der jede Ecke eines unbekannten Graphen mindestens einmal besucht und danach zur Ausgangsecke zurückkehrt.
Aus dieser Grundidee entstanden die beiden deterministischen Irrfahrten in der Eckenversion und in der Kantenversion. Die Irrfahrt in der Eckenversion wählt von der Startecke aus eine benachbarte Ecke und im Anschluss immer die Ecke, die am seltensten besucht wurde, außer alle Ecken wurden gleich oft besucht, dann wird die nächste Ecke ausgewählt entsprechend einer zuvor festgesetzten Reihenfolge unter den Ecken. Die Irrfahrt endet, wenn die Startecke zum zweiten Mal erreicht wird.
Die Irrfahrt in der Kantenversion wählt von der Startecke aus eine benachbarte Kante und im Anschluss immer die Kante, die am seltensten besucht wurde, außer alle Kanten wurden gleich oft besucht, dann wird die nächste Kante ausgewählt entsprechend einer zuvor festgesetzten Reihenfolge unter den Kanten. Die Irrfahrt endet, wenn die Startecke zum zweiten Mal erreicht wird.
Die beiden Irrfahrten sind im Allgemeinen nicht erfolgreich in ihrer Zielsetzung alle Ecken des Graphen zu erreichen, außer auf Bäumen, wenn die Startecke ein Blatt ist. Es ergeben sich neue Fragestellungen: Wird die Startecke zum zweiten Mal erreicht und ist die Irrfahrt somit endlich? Welchen Weg legt die Irrfahrt maximal zurück? Außerdem ergibt sich die Frage, ob es überhaupt einen Algorithmus geben kann, der durch reines Zählen der Besuche der Ecken bzw. Kanten das Netzwerk vollständig absuchen und danach zur Startecke zurückkehren kann.
Inhaltsverzeichnis
- 1 Einleitung
- 2 Einordnung in die Literatur
- 3 Graphentheoretische Grundlagen
- 4 Die deterministische Irrfahrt ☞ in der Eckenversion
- 4.1 Die deterministische Irrfahrt I auf Bäumen
- 4.2 Die deterministische Irrfahrt auf vollständig bipartiten Graphen Ka,b
- 5 Die deterministische Irrfahrt in der Kantenversion
- 5.1 Die deterministische Irrfahrt I' auf Bäumen
- 5.2 Die deterministische Irrfahrt auf vollständigen Graphen Kn
- 6 Zusammenfassung
Zielsetzung und Themenschwerpunkte
Die Diplomarbeit beschäftigt sich mit der Entwicklung und Analyse von deterministischen Irrfahrten auf Graphen. Ziel ist es, Algorithmen zu entwickeln, die in der Lage sind, alle Ecken eines unbekannten Graphen zu besuchen und danach zur Ausgangsecke zurückzukehren, ohne einen großen Speicherplatz für die Speicherung des gesamten Graphen zu benötigen. Die Arbeit untersucht zwei spezifische Arten von deterministischen Irrfahrten: die Irrfahrt I in der Eckenversion und die Irrfahrt I' in der Kantenversion.
- Die deterministischen Irrfahrten I und I' auf verschiedenen Graphenarten (z.B. Bäume, vollständige bipartite Graphen, vollständige Graphen).
- Die Analyse der Effizienz und der Grenzen der deterministischen Irrfahrten.
- Die Erforschung der Frage, ob es einen Algorithmus gibt, der durch reines Zählen der Besuche von Ecken bzw. Kanten ein Netzwerk vollständig absuchen und zur Ausgangsecke zurückkehren kann.
- Der Vergleich der deterministischen Irrfahrten mit bekannten randomisierten Algorithmen.
Zusammenfassung der Kapitel
- Kapitel 1: Einleitung
Die Einleitung stellt das Thema der Diplomarbeit vor und erläutert die Motivation hinter der Entwicklung von deterministischen Irrfahrten. - Kapitel 2: Einordnung in die Literatur
Dieses Kapitel gibt einen Überblick über die historische Entwicklung des Konzepts der Irrfahrt und beschreibt verschiedene Anwendungen in verschiedenen Disziplinen. - Kapitel 3: Graphentheoretische Grundlagen
Hier werden grundlegende Definitionen und Konzepte aus der Graphentheorie vorgestellt, die für das Verständnis der deterministischen Irrfahrten notwendig sind. - Kapitel 4: Die deterministische Irrfahrt ☞ in der Eckenversion
Dieses Kapitel behandelt die deterministische Irrfahrt I in der Eckenversion. Es werden die Funktionsweise der Irrfahrt sowie ihre Anwendung auf Bäume und vollständig bipartite Graphen erläutert. - Kapitel 5: Die deterministische Irrfahrt in der Kantenversion
Dieses Kapitel befasst sich mit der deterministischen Irrfahrt I' in der Kantenversion. Es werden die Funktionsweise der Irrfahrt sowie ihre Anwendung auf Bäume und vollständige Graphen erläutert.
Schlüsselwörter
Die zentralen Themen der Arbeit sind deterministische Irrfahrten, Graphentheorie, Algorithmen, Bäume, vollständige bipartite Graphen, vollständige Graphen, Eckenversion, Kantenversion, Effizienz, Grenzen, randomisierte Algorithmen.
- Arbeit zitieren
- Katrin von Otte (Autor:in), 2016, Deterministische Irrfahrten auf Graphen, München, GRIN Verlag, https://www.grin.com/document/321316
