Grin logo
en de es fr
Shop
GRIN Website
Publish your texts - enjoy our full service for authors
Go to shop › Mathematics - Miscellaneous

Deterministische Irrfahrten auf Graphen

Title: Deterministische Irrfahrten auf Graphen

Diploma Thesis , 2016 , 30 Pages , Grade: 1,7

Autor:in: Katrin von Otte (Author)

Mathematics - Miscellaneous
Excerpt & Details   Look inside the ebook
Summary Excerpt Details

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.

Excerpt


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.

Excerpt out of 30 pages  - scroll top

Details

Title
Deterministische Irrfahrten auf Graphen
College
Technical University of Ilmenau  (Institut für Mathematik und Naturwissenschaften)
Grade
1,7
Author
Katrin von Otte (Author)
Publication Year
2016
Pages
30
Catalog Number
V321316
ISBN (eBook)
9783668206434
ISBN (Book)
9783668206441
Language
German
Tags
Diskrete Mathematik Mathematik Graphentheorie Random Walk Irrfahrten auf Graphen
Product Safety
GRIN Publishing GmbH
Quote paper
Katrin von Otte (Author), 2016, Deterministische Irrfahrten auf Graphen, Munich, GRIN Verlag, https://www.grin.com/document/321316
Look inside the ebook
  • Depending on your browser, you might see this message in place of the failed image.
  • Depending on your browser, you might see this message in place of the failed image.
  • Depending on your browser, you might see this message in place of the failed image.
  • Depending on your browser, you might see this message in place of the failed image.
  • Depending on your browser, you might see this message in place of the failed image.
  • Depending on your browser, you might see this message in place of the failed image.
  • Depending on your browser, you might see this message in place of the failed image.
  • Depending on your browser, you might see this message in place of the failed image.
  • Depending on your browser, you might see this message in place of the failed image.
  • Depending on your browser, you might see this message in place of the failed image.
Excerpt from  30  pages
Grin logo
  • Grin.com
  • Payment & Shipping
  • Contact
  • Privacy
  • Terms
  • Imprint