Rundreisealgorithmen

Eulerkreise

Das Königsberger Brückenproblem hat keine Lösung. Es gibt also keinen Rundgang durch Königsberg, der jede der sieben Brücken über den Fluss Pregel genau einmal benutzt. Das lässt sich leicht einsehen, wenn man die Brückensituation in Königsberg mit einem Graphen beschreibt.

Eine Rundreise, in der jede Kante (Brücke) genau einmal vorkommt, besucht einen Knoten (Stadtteil) über eine Kante (Brücke) und verlässt ihn über eine andere Kante (Brücke). Hieraus ergibt sich, dass die Anzahl der Kanten (Brücken), die von einem Knoten (Stadtteil) der Rundreise ausgehen, gerade sein muss, damit eine Rundreise der gewünschten Art zustande kommen kann. Diese notwendige Bedingung ist beim Königsberger Brückenproblem aber nicht erfüllt.

Wie verallgemeinern das Problem jetzt auf beliebige Graphen (und nennen es Euler-Problem): Gegeben ist ein Graph mit seinen Knoten und Kanten. Gesucht ist eine Rundreise durch den Graphen, in der jede Kante genau einmal vorkommt. Eine solche Rundreise wird auch Eulerkreis genannt.

Zur Lösung des Problems nutzt man den folgenden Zusammenhang: In einem Graphen gibt es einen Eulerkreis genau dann, wenn von allen Knoten eine gerade Anzahl von Kanten ausgeht und alle Knoten von einem willkürlich gewählten Startknoten aus erreichbar sind.

Das Euler-Problem lässt sich somit mit dem folgenden Algorithmus erledigen.

ALGORITHMUS eulerkreis:
    Übergabe: Graph, dargestellt mit einer Nachbarschaftstabelle
    kreisExistiert = True
    FÜR alle Knoten des Graphen:
        bestimme die Anzahl der Nachbarn des Knoten
        WENN diese Anzahl ungerade ist:
            kreisExistiert = False
    Rückgabe: kreisExistiert

Hamiltonkreise

Das Rundreiseproblem auf einem Dodekaeder hat eine Reihe von Lösungen, z.B.:

Auch hier verallgemeinern wir das Problem auf beliebige Graphen (und nennen es Hamilton-Problem): Gegeben ist ein Graph mit seinen Knoten und Kanten. Gesucht ist eine Rundreise durch den Graphen, in der jeder Knoten genau einmal vorkommt - nur Start- und Zielknoten kommen genau zweimal vor. Eine solche Rundreise wird auch Hamiltonkreis genannt.

Wie überprüft man, ob es einen Hamiltonkreis zu einem gegebenen Graphen gibt? Die Lösung lautet: durch systematisches Ausprobieren.

Wir verdeutlichen im Folgenden eine naive Vorgehensweise anhand des folgenden Graphen:

Knoten 1 soll der Start- und Zielknoten sein. Die Wahl dieses Startknotens ist nicht entscheidend, da ja jeder Knoten in der Rundreise vorkommen soll.

Jetzt bestimmen wir eine mögliche Reihenfolge der zu besuchenden Knoten, z.B.: 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20. Hieraus ergibt sich als mögliche Rundreise:

1-2-3-4-5-6-7-8-9-10-11-12-13-14-15-16-17-18-19-20-1

Anschließend überprüfen wir, ob die Rundreise überhaupt möglich ist, d.h., ob es jeweils Kanten zu den aufgelisteten Knoten gibt. Im vorliegenden Fall gibt es die Kante (20, 1) nicht. Die Knotenliste führt also nicht zu einem Hamiltonkreis.

Als nächstes erzeugen wir (systematisch) eine andere Reihenfolge der zu besuchenden Knoten, z.B.: 3 2 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20. Hieraus ergibt sich als mögliche Rundreise:

1-3-2-4-5-6-7-8-9-10-11-12-13-14-15-16-17-18-19-20-1

Auch diese Knotenliste führt nicht zu einem Hamiltonkreis, da die Kante (1, 3) nicht existiert.

Entsprechend fahren wir fort und erzeugen immer neue Anordnungen der zu besuchenden Knoten und überprüfen, ob die erzeugte Auflistung der Knoten zu einem Hamiltonkreis führt. Dieses Verfahren lässt sich wie folgt als Algorithmus formulieren.

ALGORITHMUS hamiltonkreis
    Ü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