Deterministische Irrfahrten auf Graphen

ISBN-13: 9783668206441 / Niemiecki / Miękka / 2016 / 36 str.

Katrin Von Otte

Opis

Diplomarbeit aus dem Jahr 2016 im Fachbereich Mathematik - Sonstiges, Note: 1,7, Technische Universitat Ilmenau (Institut fur Mathematik und Naturwissenschaften), Sprache: Deutsch, Abstract: Die Idee fur diese Arbeit stammt von Prof. Armin Mikler 2007, der nach einem (moglichst deterministischen) Algorithmus suchte, der jede Ecke eines unbekannten Graphen mindestens einmal besucht und danach zur Ausgangsecke zuruckkehrt. Aus dieser Grundidee entstanden die beiden deterministischen Irrfahrten in der Eckenversion und in der Kantenversion. Die Irrfahrt in der Eckenversion wahlt von der Startecke aus eine benachbarte Ecke und im Anschluss immer die Ecke, die am seltensten besucht wurde, auer alle Ecken wurden gleich oft besucht, dann wird die nachste Ecke ausgewahlt entsprechend einer zuvor festgesetzten Reihenfolge unter den Ecken. Die Irrfahrt endet, wenn die Startecke zum zweiten Mal erreicht wird. Die Irrfahrt in der Kantenversion wahlt von der Startecke aus eine benachbarte Kante und im Anschluss immer die Kante, die am seltensten besucht wurde, auer alle Kanten wurden gleich oft besucht, dann wird die nachste Kante ausgewahlt 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, auer auf Baumen, 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 zuruck? Auerdem ergibt sich die Frage, ob es uberhaupt einen Algorithmus geben kann, der durch reines Zahlen der Besuche der Ecken bzw. Kanten das Netzwerk vollstandig absuchen und danach zur Startecke zuruckkehren kann.