Wege und Kreise in Graphen

Das Königsberger Brückenproblem | Eulerweg/-kreis | Hamiltonweg/-kreis | Problem des Handesreisenden

Das Königsberger Brückenproblem

a) Arbeiten Sie sich das AB durch!

b) Erläuterung


Der Eulerweg

Man kann eine Figur in einem Zug zeichnen, so dass keine Kante doppelt genutzt wird und der Endknoten gleich dem Anfangsknoten ist. Dies funktioniert nur, wenn der Grad jedes Knotens eine gerade Zahl ist.

Also: Es existiert genau dann ein Eulerweg in G, wenn höchstens 2 Knoten in V ungeraden Grades sind.

Beispiele:

Der Eulerkreis

Ein Eulerkreis ist ein Eulerweg, bei dem der Startknoten gleichzeitig der Zielknoten ist. Dazu müssen alle Knoten von geradem Grad sein.
Für einen Knoten, der in einem Eulerkreis nicht der Startknoten ist, gilt das gleiche wie in einem Eulerweg: Der Knoten muss geraden Grad besitzen.

c) Erläuterung

d) Erstellen Sie einen eigenen Graphen in diesem Applet und testen Sie, ob jeweils ein Eulerkreis zustande kommt.

e) Stellen Sie den Inhalt der Webseite ihren Mitschülern vor!

f) Informieren Sie sich hier , wie man einen Eulerweg/Eulerkreis findet. ihren Mitschülern vor!

Der Hamiltonweg/-kreis

Ein Hamiltonkreis ist ein Pfad, der jeden Knoten eines Graphen genau einmal besucht. Die Entscheidungsfrage ist nun, ob es in einem Graphen solch einen Hamiltonkreis gibt.
Ein Hamiltonweg ist ein Weg, der alle Knoten eines Graphen nur einmal durchläuft.

Beispiel:

Man stelle sich Neustadt einfach als einen Graphen vor: Die Kreuzungen sind die Knoten und die Straßenabschnitte zwischen diesen Knoten sind die Kanten. Eine Reisegruppe soll nun auf einem Weg an allen Sehenswürdigkeiten vorbeigeführt werden.

Lösungsmöglichkeit : Backtracking (für wenige Knoten)
- Beginne bei einem Knoten - meinetwegen bei der Stadtkirche - und speichere die Pfade zu unbesuchten Sehenswürdigkeiten, ausgehend von der Kirche.
- Für jeden Pfad sind neue Pfade - ausgehend vom letzten Knoten - zu unbesuchten Nachbarn zu speichern.
- Wiederhole diese Schritte, bis ein Hamilton Kreis gefunden wird oder bis alle Pfade besucht wurden oder du vor Müdigkeit auf einer Parkbank einschläfst.

Anmerkung: Man unterscheidet beim Hamiltonkreisproblem zwischen ungererichteten und gerichteten Graphen.

Leider ist uns keine effiziente Methode bekannt festzustellen, ob ein Graph einen Hamiltonschen Weg oder Kreis enthält. Ebens gibt es auch keinen Algorithmus zur Konstruktion eines solchen Weges oder Kreises.

Verwandt mit dem Hamiltonkreisproblem ist das Springerproblem .

Das Problem des Handelsreisenden ( traveling salesman problem)


Hier geht es um Optimierung.
Wer von Neustadt an der Orla nach Rostock will, gibt die beiden Orte ins Navi ein und erhält binnen Sekunden die optimale Route. Sollen auf dem Weg noch Berlin, Magdeburg, Salzwedel und Neubrandenburg in dieser Reihenfolge angefahren werden, berechnet die Elektronik erst den besten Weg von Neustadt an der Orla nach Berlin, dann die Strecke von Berlin nach Magdeburg usw.. Problematisch wird es, wenn in beliebiger Reihenfolge mehrere Städte besucht werden sollen, dabei aber auf dem kürzesten Gesamtweg. Möchte ein Duhlendorfer bei allen Karnevalshochburgen – nehmen wir an, es sind 26 - auf einer möglichst effizienten, also preisgünstigen Rundreise vorbeischauen, wären die schnellsten Computer der Welt mit der Reiseplanung hoffnungslos überfordert.

Angenommen, es gäbe zwischen den Städten immer nur eine Verbindung, sind über 1 000 000 000 000 000 000 000 000 Routen möglich. Aber diese Rechnung ist viel zu aufwändig.
Eine Million Dollar wurden von der Clay Foundation ausgelobt.