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 Gradsumme d_G(x)+d_G(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 G₀,...,G_k eine Folge von ungerichteten Graphen, wobei G_i aus G_i-1 für jedes i aus {1,...,k} durch Hinzufügen einer Kante {x,y} mit d_Gi-1(x)+d_Gi-1(y)?|V(G _i-1)| entsteht und d_Gk(x)+d_Gik(y)?|V(G _i-1)| für jedes Paar in G_k nicht benachbarter Knoten x und y, so bezeichnet man G_k als Hamiltonabschluss von G₀. 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:

1. d_G(x)+d_G(y)?|V(G)| für alle {x,y} die nicht zu E(G) gehören oder
2. der Minimalgrad mindestens |V(G)|/2 ist oder
3. die Knotenzusammenhangszahl von G mindestens so groß wie die Stabilitätszahl von G ist.

Diese Aussagen sind scharf in dem Sinne, dass es Gegenbeispiele bei minimal schwächeren Voraussetzungen gibt.

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 ungerichteten Hamiltonkreisen lassen sich auf gerichtete reduzieren. Das Problem des Handlungsreisenden lässt sich auf Probleme mit ungerichteten Hamiltonkreisen reduzieren.