Deterministische Irrfahrten auf Graphen

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.