Hamiltonsche Graphen

Hamiltonsche Graphen helfen z.B. bei der Reiseplanung einer Städtetour: Jede Stadt soll nur einmal besucht werden, dabei müssen dann natürlich nicht alle Wege von einer Stadt in die andere abgefahren werden.

Übersetzt in die Graphentheorie bedeutet das, dass man in einem Graphen einen Linienzug sucht, der durch jede Ecke genau einmal geht und dessen Startecke auch die Zielecke ist.

Wie bei den eulerschen Graphen kann jede Kante nur einmal benutzt werden (denn wenn eine Kante doppelt verwendet wird, ist man in einer der beiden damit verbundenen Ecken zweimal gewesen), jedoch können jetzt auch Kanten „übrig“ bleiben, also nicht für den Linienzug verwendet werden.

Da man jede Ecke besuchen soll müssen die Ecken mindestens den Grad zwei haben - Ecken mit Grad eins wären eine Sackgasse.

Definitionen

Ein hamiltonscher Graph enthält einen hamiltonschen Kreis, also einen Linienzug, der durch jede Ecke genau einmal führt und dessen Start- und Zielecke identisch sind.

In Graphen, die nicht hamiltonsch sind, lassen sich aber eventuell Kreise oder Wege finden.

Ein Kreis ist ein geschlossener Linienzug, der durch jede enthaltene Ecke genau einmal geht, aber nicht unbedingt alle Ecken des Graphen enthält (dann wäre der Kreis ja hamiltonsch).

Ein Weg ist dann ein Linienzug, der durch alle auf dem Weg liegenden Ecken genau einmal geht, dessen Start- und Zielecke aber unterschiedlich sind. 1)

Finden eines hamiltonschen Kreises

Für eulersche Graphen existiert ein Algorithmus um eulersche Touren zu finden. Etwas vergleichbares gibt es für das Finden von hamiltonschen Kreisen nicht. Auch kann nicht einfach durch Bestimmung des Eckengrads bestimmt werden, ob überhaupt ein hamiltonscher Kreis existiert (Ausnahme: es existiert mindestens eine Ecke mit dem Grad eins, dann ist der Graph sicher nicht hamiltonsch). Es bleibt einem zunächst also nichts anderes übrig als auszuprobieren, ob man einen hamiltonschen Kreis findet.

Beim Suchen nach einem hamiltonschen Kreis kann man sich helfen, indem man nach dem Besuch einer Ecke alle Kanten streicht, die man an der besuchten Ecke nicht verwendet hat. Dabei dürfen zwei Dinge nicht passieren:

  1. Es dürfen keine Ecken mit dem Grad eins entstehen.
  2. Es dürfen keine Teilgraphen abgespalten werden, die mit dem übrigen Graphen nicht mehr zusammenhängen.

Je mehr Kanten ein Graph hat, desto unübersichtlicher ist das Finden eines hamiltonschen Graphen zunächst - aber desto mehr Möglichkeiten hat man auch, überhaupt einen hamiltonschen Kreis zu finden. Damit ist ein Graph in der Regel hamiltonsch, wenn er genügend viele Kanten hat. Nach Dirac heißt „genügend viele“ in einem einfachen Graphen, dass an jeder Ecke mindestens halb so viele Kanten vorhanden sind wie Ecken im Graphen.

Vollständige Vielecke sind z.B. sicher hamiltonsche Graphen, da hier jede der n Ecken an n-1 Kanten liegt, da jede Ecke mit jeder anderen verbunden ist.

Ein Testverfahren

Der Begriff „hamiltonscher Kreis“ sagt ja, dass man einen gegebenen Graphen so umzeichnen könnte, dass alle Ecken auf einer Kreislinie liegen. Nicht benötigte Kanten für die Kreislinie werden dann zu Sehnen im Kreis, Schlingen im Graphen bleiben Schlingen an der isomorphen Kreisfigur.

Würde man jetzt eine Ecke des Kreise, zusammen mit den daranhängenden Kanten, entfernen, so bliebe ein zusammenhängender Graph übrig (genau wie z.B. ein Gummiband auch an einem Stück bliebt, wenn man es an einer Stelle aufschneidet). Erst wenn zwei Ecken mit den zugehörigen Kanten entfernt werden kann der ursprüngliche Graph in zwei Teile zerfallen. Jede weitere entfernte Ecke erhöht die Anzahl der Teile um eines.

Kehrt man diese Überlegung um, so hat mein ein Testverfahren für die Eigenschaft hamiltonsch:

  • Wenn beim Entfernen einer Ecke (oder n Ecken) mit den dazugehörigen Kanten ein Graph in mindestens zwei Teilgraphen (oder n+1 Teilgraphen) zerfällt, so war der ursprüngliche Graph nicht hamiltonsch.

Dieser Satz bedeutet aber nicht, dass ein Graph hamiltonsch sein muss, wenn er beim Entfernen einer Ecke zusammenhängend bleibt…

Traveling Salesman Problem

Stellt man sich jetzt vor, dass die Kanten eines Graphen noch mit Zahlen versehen sind, die das „Gewicht“ oder den „Preis“ oder einfach nur die „Länge“ einer solchen Kante angeben, so verändert sich die Aufgabe der Suche eines Kreises im Graphen. Man sucht jetzt nicht mehr irgendeinen Kreis durch alle Ecken, sondern den günstigsten - also den Kreis, bei dem die Summe der Kantengewichte (der Zahlen an den Kanten) so klein wie möglich ist.

Für einen umherreisenden Vertreter wäre es also die Aufgabe, den kürzestens Kreis zu finden, bei der Produktion von Waren würde man sicher die kostengünstigste suchen.

Da das Finden eines hamiltonschen Kreises nicht automatisierbar ist, ist auch das Traveling Salesman Problem noch nicht theoretisch gelöst. In der Praxis gibt es aber Möglichkeiten, mehr oder weniger automatisch einen günstigen Kantenzug zu finden (z.B. „nimm immer die günstigste mögliche Kante“), was in der Regel für eine praktische Lösung ausreicht. Es ist dann aber noch nicht bewiesen, dass der gefundene Linienzug wirklich die beste Lösung ist - das würde aber auch nur die Mathematik verlangen.

1) Wege in nicht-hamiltonschen Graphen sind also vergleichbar mit den Touren in nicht-eulerschen Graphen - im Gegensatz zu den Touren lassen sich Wege aber auch in hamiltonschen Graphen finden.
mint/graphen/hamilton.txt · Zuletzt geändert: 2012/01/08 17:49 von ahrens
CC Attribution-Noncommercial-Share Alike 3.0 Unported
www.chimeric.de Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0