Komplexitätsbetrachtungen

Am Anfang der Stunde haben wir uns noch einmal kurz mit den Faktorisierungen beschäftigt und uns Vergleiche dazu angeschaut.

Eulerkreis

Eulerkreis def.: Ein Eulerkreis oder (geschlossener) Eulerzug (auch Eulertour oder Eulersche Linie) ist in der Graphentheorie ein Zyklus, der alle Kanten eines Graphen genau einmal enthält. (https://de.wikipedia.org/wiki/Eulerkreisproblem )

Nach der Wiederholung zu den Faktorisierungen, sind wir zu Inf-Schule übergegangen und haben uns die Komplexitätsbetrachtungen genauer angeschaut ( http://inf-schule.de/grenzen/komplexitaet/rundreiseprobleme/station_komplexitaetsbetrachtungen ). Wir haben uns dann die Frage gestellt ob es bei dem folgenden Graphen einen Eulerkreis gibt:

1: 2, 3
2: 1, 5, 4, 3
3: 2, 4, 5, 1
4: 2, 3
5: 2, 3

Da wir auf keine eindeutige Antwort gekommen sind, haben wir einen Algorithmus verwendet um zu bestimmen ob es zu dem Graphen einen Eulerkreis gibt oder nicht.

ALGORITHMUS eulerkreis:
    Übergabe: Graph, dargestellt mit Nachbarschaftslisten
    kreisExistiert = True
    wähle einen Knoten als Startknoten
    füge ihn in eine Liste zuBesuchen ein
    lege eine leere Liste besucht an
    SOLANGE zuBesuchen nicht leer ist und kreisExistiert den Wert True hat:
        wähle einen Knoten aus zuBesuchen aus
        bestimme die Anzahl der Nachbarn des Knoten
        WENN diese Anzahl ungerade ist:
            kreisExistiert = False
        entferne den Knoten aus zuBesuchen und
        füge ihn in besucht ein
        füge alle Nachbarknoten des ausgewählten Knoten, 
        die nicht bereits in besucht sind,
        in zuBesuchen hinzu
    Wenn in der Liste besucht nicht alle Knoten des Graphen liegen:
        kreisExistiert = False
    Rückgabe: kreisExistiert

Hausaufgabe

Kapitel 9.1.4.3 Nr 1 Graph 2 + Nr 2

Schreibe einen Kommentar