Deterministische Irrfahrten auf Graphen - Katrin von Otte

Blick ins Buch

Deterministische Irrfahrten auf Graphen (eBook)

Katrin von Otte (Autor)

eBook Download: PDF

2016 | 1. Auflage
30 Seiten
GRIN Verlag
9783668206434 (ISBN)

Lese- und Medienproben

Ebook-Leseprobe (PDF)

Diplomarbeit aus dem Jahr 2016 im Fachbereich Mathematik - Sonstiges, Note: 1,7, Technische Universität Ilmenau (Institut für Mathematik und Naturwissenschaften), Sprache: Deutsch, Abstract: 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.

Erscheint lt. Verlag	27.4.2016
Verlagsort	München
Sprache	deutsch
Themenwelt	Mathematik / Informatik ► Mathematik
Themenwelt	Technik
Schlagworte	Diskrete Mathematik • Graphentheorie • Irrfahrten auf Graphen • Mathematik • Random Walk
ISBN-13	9783668206434 / 9783668206434

Informationen gemäß Produktsicherheitsverordnung (GPSR)
Haben Sie eine Frage zum Produkt?

PDF (Ohne DRM)

Digital Rights Management: ohne DRM
Dieses eBook enthält kein DRM oder Kopierschutz. Eine Weitergabe an Dritte ist jedoch rechtlich nicht zulässig, weil Sie beim Kauf nur die Rechte an der persönlichen Nutzung erwerben.

Dateiformat: PDF (Portable Document Format)
Mit einem festen Seitenlayout eignet sich die PDF besonders für Fachbücher mit Spalten, Tabellen und Abbildungen. Eine PDF kann auf fast allen Geräten angezeigt werden, ist aber für kleine Displays (Smartphone, eReader) nur eingeschränkt geeignet.

Systemvoraussetzungen:
PC/Mac: Mit einem PC oder Mac können Sie dieses eBook lesen. Sie benötigen dafür einen PDF-Viewer - z.B. den Adobe Reader oder Adobe Digital Editions.
eReader: Dieses eBook kann mit (fast) allen eBook-Readern gelesen werden. Mit dem amazon-Kindle ist es aber nicht kompatibel.
Smartphone/Tablet: Egal ob Apple oder Android, dieses eBook können Sie lesen. Sie benötigen dafür einen PDF-Viewer - z.B. die kostenlose Adobe Digital Editions-App.

Buying eBooks from abroad
For tax law reasons we can sell eBooks just within Germany and Switzerland. Regrettably we cannot fulfill eBook-orders from other countries.

Print-Ausgabe

Buch | Softcover

CHF 25,10