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 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
4 Die deterministische Irrfahrt in der Eckenversion
Definition 8. Eine deterministische Irrfahrt = (G, v0,(fv)v∈V ) auf dem Graphen G mit der Startecke v0 und einer Familie von Abbildungen (fv)v∈V mit
fv : N(v) → N, injektiv
sei eine Folge von Kantenzügen = (K0, K1,...), die schrittweise entstehe: Es sei K0 := v0. Kp := v0 ...vp. Kp+1 := v0 ...vpvp+1, wobei vp+1 ∈ N(vp) mit dKp (vp+1) < dKp (vi) ∀vi ∈ N(vp), vi = vp+1 bzw. falls keine solche Ecke existiert, also ∃vi, vj , i = j : dKp (vi) = dKp (vj ) = minr {dKp (vr)|vr ∈ N(vp)}, dann sei vp+1 ∈ N(vp) mit fvp (vp+1) = minr {fvp (vr)|vr ∈ N(vp) ∧ dKp (vr) = mins {dKp (vs)|vs ∈ N(vp)}}. Die Irrfahrt = (K0, K1,...,Kp) ende, sobald dKp (v0)=2, und in diesem Fall, dass die Irrfahrt endet, sei der letzte Kantenzug bezeichnet mit K. Eine Irrfahrt werde als erfolgreich bezeichnet, wenn bei der Rückkehr zur Startecke alle Ecken des Graphen mindestens einmal besucht wurden, d.h. ∀vi ∈ V : dK(vi) ≥ 1.
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.
- Arbeit zitieren
- Katrin von Otte (Autor:in), 2016, Deterministische Irrfahrten auf Graphen, München, GRIN Verlag, https://www.grin.com/document/321316
