Deterministische Irrfahrten auf Graphen
Apr 2016 · GRIN Verlag
e-Buku
30
Halaman
family_home
Layak
info
reportRating dan ulasan tidak disahkan Ketahui Lebih Lanjut
Perihal e-buku ini
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.
Berikan rating untuk e-Buku ini
Beritahu kami pendapat anda.
Maklumat pembacaan
Telefon pintar dan tablet
Pasang apl Google Play Books untuk Android dan iPad/iPhone. Apl ini menyegerak secara automatik dengan akaun anda dan membenarkan anda membaca di dalam atau luar talian, walau di mana jua anda berada.
Komputer riba dan komputer
Anda boleh mendengar buku audio yang dibeli di Google Play menggunakan penyemak imbas web komputer anda.
eReader dan peranti lain
Untuk membaca pada peranti e-dakwat seperti Kobo eReaders, anda perlu memuat turun fail dan memindahkan fail itu ke peranti anda. Sila ikut arahan Pusat Bantuan yang terperinci untuk memindahkan fail ke e-Pembaca yang disokong.
