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 jeden Knoten genau einmal geht und dessen Startknoten auch der Zielknoten ist.

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

Da man jeden Knoten besuchen soll, müssen die Knoten mindestens den Grad zwei haben - Knoten mit Grad eins wären eine Sackgasse.

Definitionen

Ein hamiltonscher Graph enthält einen hamiltonschen Kreis, also einen Linienzug, der durch jeden Knoten genau einmal führt und dessen Start- und Zielknoten 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 Knoten des Graphen enthält (dann wäre der Kreis ja hamiltonsch).

Ein Weg ist dann ein Linienzug, der durch alle auf dem Weg liegenden Knoten genau einmal geht, dessen Start- und Zielknoten 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 Knotengrads bestimmt werden, ob überhaupt ein hamiltonscher Kreis existiert (Ausnahme: es existiert mindestens ein Knoten 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 eines Knoten alle Kanten streicht, die man an dem besuchten Knoten nicht verwendet hat. Dabei dürfen zwei Dinge nicht passieren:

  1. Es dürfen keine Knoten 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 Kreises 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 jedem Knoten mindestens halb so viele Kanten vorhanden sind wie Knoten im Graphen, bei n Knoten also insgesamt $(n \cdot \frac{n}{2}) : 2 = \frac{n^2}{4}$ Kanten. Das heißt aber nicht, dass nicht auch mit weniger Kanten ein hamiltonscher Kreis zu finden ist - die Existenz wird nur unwahrscheinlicher.

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

Ein Testverfahren

Der Begriff „hamiltonscher Kreis“ sagt ja, dass man einen gegebenen Graphen so umzeichnen könnte, dass alle Knoten 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 einen Knoten 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 Knoten mit den zugehörigen Kanten entfernt werden, kann der ursprüngliche Graph in zwei Teile zerfallen. Jeder weitere entfernte Knoten 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 eines Knoten (oder von n Knoten) 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 eines Knoten zusammenhängend bleibt…

Travelling 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 Knoten, 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, die kürzeste Strecke im 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 Travelling 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.
schule/graphen/hamilton.txt · Zuletzt geändert: 2018/06/09 15:29 von ahrens
CC Attribution-Noncommercial-Share Alike 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0