Komplexitätsbetrachtungen

Berechnungsaufwand als Problem

Wie aufwendig ist es, zu überprüfen, ob es in einem gegebenen Graphen einen Eulerkreis bzw. Hamiltonkreis gibt? Diese Frage soll zunächst am Beispiel durchgespielt werden.

Graph 1 hat nur 5 Knoten und ist durch die folgende Darstellung mit Nachbarschaftslisten gegeben:

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

Graph 2 hat mit 9 Knoten fast doppelt so viele Knoten wie Graph 1:

1: 2, 3, 7, 8
2: 1, 3
3: 2, 1, 8, 4
4: 3, 7, 9, 5
5: 9, 4
6: 7, 9
7: 1, 4, 9, 6
8: 1, 3
9: 4, 7, 6, 5

Aufgabe 1

(a) Überprüfe, ob Graph 1 und Graph 2 einen Eulerkreis / Hamiltonkreis haben. Arbeite nur mit den gegebenen Daten (ohne die Graphen zeichnerisch darzustellen).

(b) Vergleiche den benötigten Aufwand: Was lässt sich schneller überprüfen - die Existenz von Euler- oder Hamiltonkreisen? Wie wirkt sich eine Verdopplung der Anzahl der Knoten aus?

Aufwand zur Bestimmung von Eulerkreisen

Die Frage, ob es zu einem gegebenen Graphen einen Eulerkreis gibt, lässt sich mit dem folgenden verfeinerten Algorithmus bestimmen.

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

Zunächst muss die Problemgröße erfasst werden. Die Problemgröße ist dabei eine präzise Beschreibung des Umfangs der zu verarbeitenden Daten, von dem das Laufzeitverhalten (bzw. das Speicherverhalten) maßgeblich beeinflusst wird. Im vorliegenden Fall können wir die Anzahl der Knoten des Graphen als Problemgröße betrachten.

Als nächstes muss ein Kostenmaß zur Abschätzung des Berechnungsaufwands festgelegt werden. Zur Abschätzung des Berechnungsaufwands beim vorliegenden Algorithmus betrachten wir seine Struktur: Besuche und verarbeite (im ungünstigsten Fall) jeden Knoten und verarbeite bei jedem dieser Knoten die jeweiligen Nachbarknoten. Die Kosten werden hier also wesentlich durch die Anzahl der zu verarbeitenden Nachbarknoten beeinflusst.

Wir können folgende grobe Kostenanalyse vornehmen: Wenn der Graph n Knoten hat, so sind (im ungünstigsten Fall) höchstens n*n Verarbeitungen von Nachbarknoten zu erledigen. Die Kostenfunktion kann demnach durch eine quadratische Funktion abgeschätzt werden. Der Algorithmus hat also eine quadratische Komplexität.

Aufgabe 2

Überprüfe experimentell das Laufzeitverhalten (einer Implementierung) des Algorithmus. Entwickle hierzu selbst eine Implementierung oder benutze die Implementierung in der Datei eulerkreis.txt.

Aufwand zur Bestimmung von Hamiltonkreise mit einem naiven Algorithmus

Wir betrachten zunächst den folgenden naiven Algorithmus zur Entscheidung, ob in einem übergebenen Graphen ein Hamiltonkreis vorliegt:

ALGORITHMUS hamiltonkreis_naiv
    Übergabe: Graph, dargestellt mit Nachbarschaftslisten
    hamiltonkreisGefunden = False
    lege einen Startknoten fest
    erzeuge eine Ausgangsanordnung der zu besuchenden Knoten
    esGibtNochWeitereAnordnungen = True
    SOLANGE esGibtNochWeitereAnordnungen und nicht hamiltonkreisGefunden:
        WENN die Anordnung einen zulässigen Kreis beschreibt:
            hamiltonkreisGefunden = True
        erzeuge systematisch eine neue Anordnung der zu besuchenden Knoten
        WENN die neue Anordnung gleich der Ausgangsanordnung ist:
            esGibtNochWeitereAnordnungen = False
    Rückgabe: hamiltonkreisGefunden

Die Problemgröße lässt sich auch hier hier durch die Anzahl der Knoten des zu überprüfenden Graphen beschreiben.

Der Berechnungsaufwand wird wesentlich durch die Anzahl der Anordnungen bestimmt, die hier systematisch erzeugt und überprüft werden. Mit der sogenannten Kostenfunktion K(n) beschreiben wir diese Anzahl von Anordnungen bei einer Problemgröße n.

Die Herleitung einer Formel für K(n) soll hier für den Fall n = 5 durchgespielt werden.

Da der Start- und Endknoten fest gewählt wird, müssen nur Anordnungen der verbleibenden n-1 = 4 Knoten betrachtet werden.

Wenn man jetzt eine Anordnung bildet, dann gibt es 4 Möglichkeiten für den ersten Knoten, 3 Möglichkeiten für den zweiten Knoten, 2 Möglichkeiten den dritten Knoten und schließlich 1 Möglichkeit für den vierten Knoten.

Ingesamt können bei einem Graphen mit 5 Knoten also 4*3*2*1 verschiedene Anordnungen (Permutationen) für Rundwege mit festem Startknoten gebildet werden. Mathematiker schreiben auch 4! (gelesen: 4 Fakultät) für das Produkt 4*3*2*1.

Wenn man die Überlegungen verallgeinert, so erhält man

K(n) = (n-1)!

Mathematiker haben gezeigt, dass n! ≥ (n/2)^(n/2) gilt.

Mit dieser Abschätzung erhält man K(n) ≥ ((n-1)/2)^((n-1)/2). Die Kostenfunktion hat also mindestens ein exponentielles Wachstumsverhalten. Der betrachtete Algorithmus hat somit keine polynomiale Komplexität.

Aufgabe 3

(a) Bestimme die Anzahl der Anordnungen bei den oben gegebenen Graphen.

(b) Wenn der übergebene Graph relativ wenig Kanten hat, erzeugt der gezeigte Algorithmus eine riesige Menge an Anordnungen, die alle keinen zulässígen Rundweg bilden. Überlege dir Verbesserungen des Algorithmus.

Aufgabe 4

Gibt es bessere Algorithmen? Der folgende Algorithmus versucht, systematisch alle möglichen Rundwege durch den Graphen zu erzeugen, bricht aber ab, wenn ein Weg nicht erweiterbar ist.

ALGORITHMUS hamiltonkreis
    Übergabe: Graph, dargestellt mit Nachbarschaftslisten
    kreisExistiert = False
    lege einen startKnoten fest
    # erzeuge eine Liste wege, mit der die Anfangsteile möglicher Rundreisewege verwaltet werden
    wege = [[startKnoten]]
    SOLANGE wege nicht leer ist und nicht kreisExistiert:
        aktuellerWeg = erster Weg in wege
        entferne akteuellerWeg aus wege
        WENN aktuellerWeg alle Knoten des Graphen enthält:
            WENN es eine Kante vom letzten Knoten von aktuellerWeg zum startKnoten gibt:
                kreisExistiert = True
        SONST:
            letzterKnoten = letzter Knoten von aktuellerWeg
            FÜR alle nachbarKnoten von letzterKnoten:
                WENN nachbarKnoten nicht bereits in aktuellerWeg vorkommt:
                    erweiterterWeg = aktuellerWeg erweitert um nachbarKnoten
                    nimm erweiterterWeg in der Liste wege auf
    Rückgabe: kreisExistiert

Die aus Komplexitätssicht entscheidende Frage lautet: Handelt es sich um einen Algorithmus mit polynomialem Berechnungsaufwand?

(a) Teste das Programm in der Datei hamiltonkreis.txt. Führe zunächst einfache Tests wie hamiltonkreis(graph1) aus und deute die Ergebnisse.

(b) Vorbemerkungen: Bei automatisierten Tests werden die zu verarbeitenden Graphen mit dem Zufallsgenerator erzeugt. In der aktuellen Testversion werden jedem Knoten 4 Nachbarknoten zufällig zugeordnet. Beachte, dass hierdurch ein Knoten auch sich selbst als Nachbar haben kann und dass ein Nachbar in der Nachbarschaftsliste eines Knotens mehrfach vorkommen kann. Der resultierende Graph ist in der Regel gerichtet, da nicht darauf geachtet wird, dass die Nachbarschaftsbeziehung symmetrisch ist. Automatisierte Tests liefern Ergebnisse wie z.B.:

>>> 
4 22
5 49
6 83
7 137
8 255
9 645
10 1307
11 2437
12 4422
13 9879
14 17468
15 24083
...

Welche Art von Wachstum liegt hier vor? Vergleiche die Zahlen mit den Zweierpotenzen. Wie könnte man das Ergebnis plausibel machen. Bei der Erklärung könntest du z.B. die Annahme machen, dass etwa die Hälfte aller angefangenen Wege erweiterbar ist.