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 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 auf Bäumen

5.2 Die deterministische Irrfahrt auf vollständigen Graphen Kn

6 Zusammenfassung

Zielsetzung & Themen

Die vorliegende Arbeit befasst sich mit der Entwicklung und Analyse von deterministischen Irrfahrten auf Graphen, die darauf abzielen, alle Ecken eines unbekannten Netzwerks mit minimalem Speicherbedarf zu besuchen und zur Startecke zurückzukehren. Die zentrale Forschungsfrage ist, ob ein solcher deterministischer Algorithmus existiert, der lediglich durch das Zählen der Besuche von Ecken oder Kanten ein Netzwerk vollständig absuchen kann.

• Konzeption der Eckenversion der deterministischen Irrfahrt
• Konzeption der Kantenversion der deterministischen Irrfahrt
• Untersuchung der Effektivität auf speziellen Graphenstrukturen wie Bäumen, bipartiten und vollständigen Graphen
• Mathematische Herleitung von Schranken für die Irrfahrtlänge und Endlichkeit
• Vergleich der deterministischen Ansätze mit klassischen randomisierten Irrfahrten

Auszug aus dem Buch

Zusammenfassung der Kapitel

1 Einleitung: Einführung in die Problemstellung und Motivation für deterministische Irrfahrten auf Graphen durch Prof. Armin Mikler.

2 Einordnung in die Literatur: Historischer Überblick über die Entwicklung von Irrfahrten (Random Walks) von Karl Pearson bis zu modernen Anwendungen wie PageRank.

3 Graphentheoretische Grundlagen: Definition grundlegender Begriffe der Graphentheorie wie Ecken, Kanten, Grad, Abstand und Baum.

4 Die deterministische Irrfahrt in der Eckenversion: Definition und mathematische Analyse der Eckenversion der Irrfahrt sowie deren Verhalten auf Bäumen und vollständig bipartiten Graphen.

5 Die deterministische Irrfahrt in der Kantenversion: Einführung der Kantenversion und Untersuchung von Endlichkeit und Erfolg auf speziellen Graphenstrukturen.

6 Zusammenfassung: Reflexion über die Ergebnisse, Diskussion von Schranken für die Irrfahrtlängen und Ausblick auf zukünftige Forschungsfragen.

Schlüsselwörter

Deterministische Irrfahrt, Graphentheorie, Eckenversion, Kantenversion, Kantenzug, vollständiger Graph, bipartiter Graph, Baum, Algorithmus, Netzwerkanalyse, Startecke, Wanderung, Pfadlänge, Markow-Kette, Suchalgorithmus.

Häufig gestellte Fragen

Worum geht es in dieser Diplomarbeit grundsätzlich?

Die Arbeit entwickelt und untersucht deterministische Irrfahrten, die Ecken oder Kanten in unbekannten Netzwerken absuchen, ohne dabei den Graphen vollständig im Speicher ablegen zu müssen.

Was sind die zentralen Themenfelder?

Die zentralen Felder sind die Graphentheorie, speziell Algorithmen auf Netzwerken, sowie die formale Analyse von Pfadlängen und Erfolgsbedingungen bei deterministischen Suchstrategien.

Was ist das primäre Ziel der Arbeit?

Das Ziel ist es, einen deterministischen Algorithmus zu finden, der durch reines Zählen von Besuchen alle Ecken eines Graphen erreicht und zur Startecke zurückkehrt.

Welche wissenschaftliche Methode wird verwendet?

Es werden formale mathematische Definitionen und Beweise durch vollständige Induktion verwendet, um das Verhalten der Irrfahrten auf verschiedenen Graphklassen zu analysieren.

Was wird im Hauptteil behandelt?

Der Hauptteil gliedert sich in die Untersuchung einer Eckenversion und einer Kantenversion der Irrfahrt, wobei jeweils auf Bäumen und speziellen Graphentypen wie vollständigen Graphen operiert wird.

Welche Schlüsselwörter charakterisieren die Arbeit?

Zu den wichtigsten Begriffen gehören deterministische Irrfahrt, Graphentheorie, Kantenzug, Erfolgskriterien bei Graphensuche und algorithmische Komplexität.

Was unterscheidet die Eckenversion von der Kantenversion?

Die Eckenversion wählt als Entscheidungsgrundlage die seltensten Besuche von Nachbarecken, während die Kantenversion dies basierend auf den Kanten des Graphen tut.

Sind die vorgestellten Irrfahrten auf allen Graphen erfolgreich?

Nein, die Arbeit zeigt, dass die Irrfahrten im Allgemeinen nicht erfolgreich sind; sie sind lediglich auf Bäumen unter spezifischen Bedingungen (Grad der Startecke = 1) erfolgreich.