Hamiltonkreisproblem

aus Wikipedia, der freien Enzyklopädie
(Weitergeleitet von Hamiltonweg)
Zur Navigation springen Zur Suche springen

Ein Hamiltonkreis ist ein geschlossener Pfad in einem Graphen, der jeden Knoten genau einmal enthält. Die Frage, ob ein solcher Kreis in einem gegebenen Graphen existiert, ist ein wichtiges Problem der Graphentheorie. Im Gegensatz zum leicht lösbaren Eulerkreisproblem, bei dem ein Kreis gesucht wird, der alle Kanten genau einmal durchläuft, ist das Hamiltonkreisproblem NP-vollständig.

Man unterscheidet das Gerichtete Hamiltonkreisproblem in gerichteten Graphen und das Ungerichtete Hamiltonkreisproblem in ungerichteten Graphen. Eine Verallgemeinerung des Hamiltonkreisproblems ist das Problem des Handlungsreisenden, bei dem nach einem kürzesten Hamiltonkreis in einem Graphen mit Kantengewichten gefragt wird.

Geschichte[Bearbeiten | Quelltext bearbeiten]

Das Dodekaeder ist, wie alle platonischen Körper, hamiltonsch.

Namensgeber des Problems ist der irische Astronom und Mathematiker Sir William Rowan Hamilton, der 1857 das Spiel „The Icosian Game“ erfand (und später verbesserte zum „Traveller's Dodecahedron or A Voyage Round The World“).

Der „Traveller's Dodecahedron“ besteht aus einem hölzernen, regulären Dodekaeder, wobei die 20 Knoten mit Namen bekannter Städte assoziiert sind. Ziel ist es, eine Reiseroute entlang der Kanten des Dodekaeders zu finden, die jede Stadt genau einmal besucht und dort aufhört, wo sie beginnt.

Zunächst erscheint die Aufgabenstellung ähnlich dem 1736 von Leonhard Euler (verneinend) gelösten Königsberger Brückenproblem, einem Spezialfall des Eulerkreisproblems und Grundsteinlegung der Graphentheorie. Während für das Eulerkreisproblem aber besonders effiziente Lösungs-Algorithmen existieren, ist bekannt, dass beide Varianten des Hamiltonkreisproblems besonders schwer algorithmisch lösbare Probleme sind. Sowohl die gerichtete als auch die ungerichtete Variante des Hamiltonkreisproblems gehört zur Liste der 21 klassischen NP-vollständigen Probleme, für die Richard M. Karp 1972 in seinem berühmten Artikel die Zugehörigkeit zu dieser Klasse von Problemen nachgewiesen hat.

Definitionen[Bearbeiten | Quelltext bearbeiten]

Sei ein Graph mit Knoten (oder Ecken) und Kanten.

heißt hamiltonsch, wenn er einen Hamiltonkreis zulässt, d. h., wenn es einen Kreis in gibt, der alle Knoten aus enthält. Ein Hamiltonpfad ist ein Pfad in , der alle Knoten aus enthält. Hat Hamiltonpfade, jedoch keinen Hamiltonkreis, so heißt semihamiltonsch.

Zur Potenz eines Graphen: Für einen Graphen und bezeichnet den Graphen auf , bei dem zwei Knoten genau dann benachbart sind, wenn sie in einen Abstand kleiner gleich haben. Offenbar gilt .

Ein beliebiges Tupel natürlicher Zahlen heißt hamiltonsch, wenn jeder Graph mit Knoten und punktweise größerer Gradsequenz hamiltonsch ist. Eine Gradsequenz heißt dabei punktweise größer als , wenn gilt für alle .

Ein Graph heißt hypohamiltonsch, wenn er keinen hamiltonschen Kreis besitzt, aber zu jedem seiner Knoten ein Kreis existiert, der alle anderen Knoten enthält.

Der Hamiltonabschluss eines Graphen ist der Obergraph von mit identischer Knotenmenge und zusätzlich iterativ eingefügten Kanten, die nichtadjazente Knoten mit Gradsumme größer gleich miteinander verbinden, solange dies möglich ist. Der Hamiltonabschluss eines Graphen ist eindeutig.

Eigenschaften[Bearbeiten | Quelltext bearbeiten]

Jeder Hamiltonkreis kann durch Entfernen einer seiner Kanten in einen Hamiltonweg umgewandelt werden. Ein Hamiltonweg kann jedoch nur dann zu einem Hamiltonkreis erweitert werden, wenn seine Endknoten benachbart sind.

Alle hamiltonschen Graphen sind 2-zusammenhängend, aber ein 2-zusammenhängender Graph muss nicht hamiltonsch sein, zum Beispiel der Petersen-Graph.

Ein eulerscher Graph, also ein zusammenhängender Graph, in dem jeder Knoten einen geraden Grad hat, besitzt notwendigerweise einen Eulerkreis, wobei der geschlossene Weg genau einmal durch jede Kante verläuft. Dieser Weg entspricht einem Hamiltonkreis im zugehörigen Kantengraphen, sodass der Kantengraph jedes eulerschen Graphen ein hamiltonscher Graph ist. Kantengraphen können andere Hamiltonkreise haben, die nicht den Eulerkreisen entsprechen, und insbesondere ist der Kantengraph jedes hamiltonschen Graphen selbst hamiltonsch, unabhängig davon, ob der Graph ein eulerscher Graph ist.

Ein Turniergraph mit mehr als zwei Knoten ist genau dann ein hamiltonscher Graph, wenn er stark zusammenhängend ist.

Die Anzahl der verschiedenen Hamiltonkreise in einem vollständigen ungerichteten Graphen mit Knoten beträgt und in einem vollständigen gerichteten Graphen mit Knoten . Dabei werden Hamiltonkreise, die bis auf ihren Startknoten gleich sind, nicht mehrfach gezählt.

Sätze über Hamiltonkreise[Bearbeiten | Quelltext bearbeiten]

Welche Bedingungen an einen Graphen mit haben die Existenz eines Hamiltonkreises zur Folge? Besonders wichtige Theoreme sind folgend chronologisch aufgelistet.

Sätze[Bearbeiten | Quelltext bearbeiten]

  • G. A. Dirac (1952), der historische Ausgangspunkt der Entdeckung einer ganzen Reihe von Bedingungen: Jeder einfache Graph mit Minimalgrad mindestens hat einen Hamiltonkreis.[1]
  • Ø. Ore (1960): Ist die Summe der Grade je zweier nicht-adjazenter Knoten eines einfachen Graphen mindestens , so ist hamiltonsch.[1]
  • L. Pósa (1962) mit einer Verallgemeinerung früherer Ergebnisse von G. A. Dirac und Ø. Ore: Sei ein einfacher Graph mit Knoten. Es gelte außerdem für alle natürlichen Zahlen , dass die Anzahl der Knoten mit Grad kleiner als ist. Falls ungerade ist, sei die Anzahl aller Knoten mit Grad kleiner oder gleich . Dann besitzt einen Hamiltonkreis.[1]
  • P. Erdős (1962): Sei ein einfacher Graph mit Knoten und Kanten. Jeder Knoten in habe einen Grad . Es gelte und es sei . Dann gilt:
    • 1. Jeder Graph mit besitzt einen Hamiltonkreis.
    • 2. Es existiert ein Graph , der keinen Hamiltonkreis besitzt.[1]
  • V. Chvátal (1972): Ein Tupel natürlicher Zahlen mit ist genau dann hamiltonsch, wenn für jedes gilt: .
  • V. Chvátal und P. Erdős (1972): Ist k-zusammenhängend und die Mächtigkeit jeder Menge unabhängiger Knoten aus , so ist hamiltonsch.
  • H. Fleischner (1974): Ist 2-zusammenhängend, so hat einen Hamiltonkreis.
  • J. A. Bondy und V. Chvátal (1976): ist genau dann hamiltonsch, wenn sein Hamiltonabschluss hamiltonsch ist.

Weitere hinreichende Eigenschaften[Bearbeiten | Quelltext bearbeiten]

Ein Graph ist hamiltonsch, wenn er

Notwendige Eigenschaften[Bearbeiten | Quelltext bearbeiten]

Hat ein Graph einen Hamiltonkreis, dann

  • hat er keinen Schnittknoten.
  • hat er keine Brücke.
  • ist sein Blockgraph ein isolierter Knoten.
  • hat er einen 2-Faktor.
  • ist er 2-zusammenhängend.
  • ist sein Minimalgrad mindestens 2.
  • ist sein Durchmesser höchstens .
  • ist er 1-tough, d. h. für jede nicht-leere Menge von Knoten gilt, dass der Graph ohne diese Knoten höchstens Zusammenhangskomponenten besitzt.
  • ist path-tough, d. h. für jeden Knoten gilt, dass der Graph ohne diesen Knoten einen Hamiltonschen Weg besitzt, das ist ein Weg, der alle Knoten des Graphen enthält.

Vermutungen[Bearbeiten | Quelltext bearbeiten]

In diesem Zusammenhang wurden diese wichtigen – nicht allgemein gelösten – Vermutungen geäußert:

  • P. Seymour (1974): Ist der Minimalgrad von , so hat einen Hamiltonkreis mit . Für entspricht dies dem Satz von G. A. Dirac, 1952, (siehe oben).
    Die Aussage für war bereits 1963 von L. Pósa vermutet worden und wurde 1996 für hinreichend große von J. Komlós, G. N. Sárközy & E. Szemerédi bewiesen.

Programmierung[Bearbeiten | Quelltext bearbeiten]

Das folgende Beispiel in der Programmiersprache C# zeigt die Implementierung eines Algorithmus, der einen Hamiltonkreis für einen ungerichteten Graphen bestimmt. Der ungerichtete Graph wird als zweidimensionales Array für die Adjazenzmatrix deklariert. Der Algorithmus verwendet Backtracking mit einer rekursiven Methode. Bei der Ausführung des Programms wird die Methode Main verwendet, die den Hamiltonkreis auf der Konsole ausgibt.[2]

using System;

public class HamiltonianCycle
{
	// Diese Methode prüft, ob der gegebene Knoten in den Hamiltonkreis eingefügt werden kann
	private bool IsValidVertex(int vertex, int[,] graph, int[] path, int index)
	{
		if (graph[path[index - 1], vertex] == 0) // Prüft, ob der Knoten ein Nachbarknoten des zuletzt eingefügt Knotens ist
		{
			return false;
		}
		for (int i = 0; i < index; i++) // Prüft, ob der Knoten schon eingefügt wurde
		{
			if (path[i] == vertex) // Wenn der Knoten schon eingefügt wurde, wird false zurückgegeben, sonst true
			{
				return false;
			}
		}
		return true;
	}
	
	// Diese rekursive Methode bestimmt einen Hamiltonkreis und gibt true zurück, wenn vorhanden, sonst false
	private bool GetHamiltonianCycleRecursive(int[,] graph, int[] path, int index)
	{
		if (index == path.Length) // Wenn alle Knoten im Pfad enthalten sind
		{
			return graph[path[index - 1], path[0]] == 1; // Wenn der erste und letzte Knoten des Pfads verbunden sind, wird true zurückgegeben, sonst false
		}
		for (int i = 1; i < path.Length; i++) // for-Schleife, in der nacheinander die Knoten mit den Indexen 1, 2, ..., n - 1 geprüft werden
		{
			if (IsValidVertex(i, graph, path, index)) // Aufruf der Methode, die prüft, ob der gegebene Knoten in den Hamiltonkreis eingefügt werden kann
			{
				path[index] = i; // Fügt den Knoten in den Pfad ein
				if (GetHamiltonianCycleRecursive(graph, path, index + 1)) // Rekursiver Aufruf mit dem nächsten Index
				{
					return true;
				}
				path[index] = -1; // Wenn der Knoten nicht in den Hamiltonkreis passt, wird er entfernt
			}
		}
		return false; // Wenn kein Knoten eingefügt werden kann, wird false zurückgegeben
	}
	
	// Diese Methode bestimmt einen Hamiltonkreis mithilfe von Backtracking und gibt true zurück, wenn vorhanden, sonst false
	private bool GetHamiltonianCycle(int[,] graph, int[] path)
	{
		for (int i = 0; i < path.Length; i++)
		{
			path[i] = -1;
		}
		path[0] = 0; // Fügt den Knoten mit dem Index 1 dem Pfad hinzu. Wenn es einen Hamiltonkreis gibt, kann dieser mit jedem Knoten beginnen.
		if (GetHamiltonianCycleRecursive(graph, path, 1)) // Wenn kein Hamiltonkreis gefunden wurde, wird true zurückgegeben, sonst false
		{
			return true;
		}
		return false;
	}
	
	// Diese Methode gibt den Hamiltonkreis, die als Array von Indexen übergeben wird, in der Form A, B, C, ... als Text zurück.
	private static string HamiltonianCycleToString(int[] path)
	{
		string text = "";
		for (int i = 0; i < path.Length; i++) // for-Schleife, die die Knoten durchläuft
		{
			text += path[i] + ", ";
		}
		text += path[0];
		return text;
	}
	
	// Hauptmethode, die das Programm ausführt
	public static void Main()
	{
		HamiltonianCycle hamiltonian = new HamiltonianCycle();
		
		// Deklariert und initialisiert ein zweidimensionales Array für die Adjazenzmatrix eines ungerichteten Graphen mit 5 Knoten
		int[,] graph = {{0, 1, 0, 1, 0},
			{1, 0, 1, 1, 1},
			{0, 1, 0, 0, 1},
			{1, 1, 0, 0, 1},
			{0, 1, 1, 1, 0},
		};
		int numberOfVertices = (int) graph.GetLongLength(0); // Variable für die Anzahl der Knoten
		int[] path = new int[numberOfVertices]; // Deklariert ein Array für den Hamiltonkreis
		if (hamiltonian.GetHamiltonianCycle(graph, path)) // Wenn ein Hamiltonkreis gefunden wurde
		{
			Console.WriteLine(HamiltonianCycleToString(path)); // Ausgabe auf der Konsole
		}
		else
		{
			Console.WriteLine("Es existiert kein Hamiltonkreis."); // Ausgabe auf der Konsole
		}
		
		Console.ReadLine();
	}
}

Siehe auch[Bearbeiten | Quelltext bearbeiten]

  • Ein Spezialfall des Hamiltonkreises ist das sogenannte Springerproblem.
  • Die Gray-Codes sind die Lösungen des Hamiltonkreisproblems für einen Hyperwürfel.

Einzelnachweise[Bearbeiten | Quelltext bearbeiten]

  1. a b c d Horst Sachs: Einführung in die Theorie der endlichen Graphen (Band 1). 1. Auflage. BSB B.G. Teubner Verlagsgesellschaft, Leipzig 1970.
  2. GeeksforGeeks: Hamiltonian Cycle | Backtracking-6

Weblinks[Bearbeiten | Quelltext bearbeiten]

Commons: Hamiltonian paths – Sammlung von Bildern, Videos und Audiodateien