Euler-Kreise und -Wege Übung

Aus ProgrammingWiki

Wechseln zu: Navigation, Suche

Inhaltsverzeichnis

Aufgabe 1 - Unterscheidung der Graphen

Unterscheiden Sie die Graphen nach eulersch, semi-eulersch oder weder noch.
a)Kerich Uebungsaufgabe1 1.png
b)Kerich Uebungsaufgabe1 2.png
c)Kerich Uebungsaufgabe1 3.png
d)Kerich Uebungsaufgabe1 4.png
e)Kerich Uebungsaufgabe1 5.png

Aufgabe 2 - Worträtsel

Bilden Sie einen Euler-Weg, der vom rotmarkierten Punkt beginnt ,sodass die abgelaufenen Kanten eine Lösungswortgruppe ergeben.
Kerich Uebung worträtsel.png

Aufgabe 3 - Algorithmus

Wenden Sie einen der beiden in der Vorlesung behandelten Algorithmen zum Nachweisen der Eulerschkeit eines Graphen(Hierholzer/Fleury) an.
Kerich Uebung Algorithmus.png

Aufgabe 4 - Postbotenproblem

Wenden Sie den Postbotenalgorithmus für folgenden Graphen an.
Kerich Uebung Postbote.png


Aufgabe 5 - Empirische Analyse

Führen Sie eine empirische Analyse durch

Aufgabe 6 - Zeichnen

Zeichnen Sie mindestens 3 Graphen mit 5 Knoten die einen Eulerkreis beinhalten.


Lösungen

Aufgabe 1: a) nicht eulersch b) eulersch c) semi-eulersch d) eulersch e) nicht eulersch


Aufgabe 2: Lösungswort: great work


Aufgabe 3: Eine von vielen möglichen Lösungen des Hierholzer Algorithmuses: Uebung Algorithmus lsg.png
Und die Lösung mit dem Agorithmus von Fleury:
Fleury.gif


Aufgabe 4: Der vollständige Graph G' aus allen Knoten mit ungeraden Grad, die kürzesten Wege zwischen diesen sowie eingefügten Matchingkanten: Uebung Postbote lsg.png
Die Integrierung in den Graphen G (rot = doppelte Kante):
Uebung Postbote lsg2.png
Anwendung des Hierholzer Algorithmus:
Uebung Postbote lsg3.png


Aufgabe 6: 3 von vielen Möglichkeiten:
1. Lsg 1.png 2. Lsg 2.png
3. Lsg 3.png

Persönliche Werkzeuge