Hamiltonkreis
Ein Hamiltonkreis ist eine bestimmte Art von Kreis in der Graphentheorie, benannt nach dem irischen Mathematiker Sir William Rowan Hamilton.Sei G=(V, E) ein (gerichteter) Graph ohne Mehrfachkanten. Ist H ein Pfad bzw. Kreis, der alle Knoten aus V enthält, so nennt man H Hamiltonpfad bzw. Hamiltonkreis. Falls ein Graph G einen Hamiltonkreis besitzt, so nennt man G hamiltonisch. Das Problem zu entscheiden, ob ein gegebener Graph einen Hamiltonpfad besitzt, bzw. ob er hamiltonisch ist, nennt man Hamiltonpfad-Problem bzw. Hamiltonkreis-Problem.
In Zusammenhang mit dem Problem des Handlungsreisenden wird eine wichtige Anwendung von Hamiltonkreisen deutlich.
Wichtige Aussagen und Sätze
Sind x und y zwei nicht benachbarte Knoten, in einem ungerichteten Graphen G, deren Gradsummesumme dG(x)+dG(y) mindestens so groß wie die Anzahl der Knoten |V(G)| in G ist, so ist G hamiltonisch genau dann, wenn G+{x,y} hamiltonisch ist. Ist G0,...,Gk eine Folge von ungerichteten Graphen, wobei Gi aus Gi-1 für jedes i aus {1,...,k} durch Hinzufügen einer Kante {x,y} mit dGi-1(x)+dGi-1(y)&ge|V(Gi-1)| entsteht und dGk(x)+dGik(y)&le|V(Gi-1)| für jedes Paar in Gk nicht benachbarter Knoten x und y, so bezeichnet man Gk als Hamiltonabschluss von G0. Ein weiterer Satz besagt, dass der Hamiltionabschluss für jeden Graphen eindeutig ist. Ein Graph ist daher genau dann hamiltonisch, wenn sein Hamiltonabschluss hamiltonisch ist.
Daraus lassen sich folgende hinreichender Bedingungen für hamiltonische Graphen ableiten. Unter anderem ist ein Graph G mit mindestens drei Knoten hamiltonisch falls:
- dG(x)+dG(y)≥|V(G)| für alle {x,y} die nicht zu E(G) gehören oder
- der Minimalgrad mindestens |V(G)|/2 ist oder
- die Knotenzusammenhangszahl von G mindestens so groß wie die Stabilitätszahl von G ist.
Graphentheoretische Probleme und ihre algorithmische Komplexität
Die Probleme Hamiltonpfad und Hamiltonkreis sind NP-vollständig. Entsprechend schwierig gestaltet es sich dann auch zusätzlich einen Hamiltonpfad bzw. einen Hamiltonkreis in einem Graphen zu finden, sofern dieser existiert. Probleme mit gerichteten Hamiltonkreisen lassen sich auf 3-SAT polynominal reduzieren. Probleme mit ungerichtete Hamiltonkreisen lassen sich auf gerichtete reduzieren. Das Problem des Handlungsreisenden lässt sich auf Probleme mit ungerichteten Hamiltonkreisen reduzieren.