Hamiltonian Path & Cycle: Jeden Knoten genau einmal besuchen

Ein Hamiltonian Path besucht jeden Knoten eines Graphen genau einmal.

Ein Hamiltonian Cycle ist ein Hamiltonian Path, dessen letzter Knoten wieder mit dem Startknoten verbunden ist.

Path und Cycle

Hamiltonian Path:

A → B → C → D

Hamiltonian Cycle:

A → B → C → D → A

Unterschied zu Euler

Hamiltonian-Probleme beziehen sich auf Knoten:

jeden Vertex genau einmal

Euler-Probleme beziehen sich auf Kanten:

jede Edge genau einmal

Dieser Unterschied ist zentral.

Beziehung zum TSP

Hamiltonian Cycle fragt, ob eine entsprechende Rundreise existiert.

Das Travelling Salesman Problem fügt Gewichte hinzu und sucht unter allen gültigen Rundreisen die kostengünstigste.

Backtracking

Eine einfache exakte Lösung probiert einen unbenutzten Nachbarn, setzt die Suche rekursiv fort und nimmt die Wahl zurück, wenn ein Dead End entsteht.

JavaScript-Beispiel

function findHamiltonianPath(graph) {
  const nodes = Object.keys(graph);

  function search(current, path, used) {
    if (path.length === nodes.length) {
      return [...path];
    }

    for (const next of graph[current] ?? []) {
      if (used.has(next)) continue;

      used.add(next);
      path.push(next);

      const result = search(next, path, used);

      if (result) return result;

      path.pop();
      used.delete(next);
    }

    return null;
  }

  for (const start of nodes) {
    const result = search(start, [start], new Set([start]));
    if (result) return result;
  }

  return null;
}

Komplexität

Naives Backtracking kann im schlechtesten Fall ungefähr

O(V!)

benötigen.

Subset-DP mit Bitmasken kann die Laufzeit auf etwa

O(V² × 2^V)

reduzieren, bleibt aber exponentiell.

NP-Complete

Die Entscheidungsvarianten von Hamiltonian Path und Hamiltonian Cycle sind klassische NP-Complete-Probleme.

Anwendungen

• Besuchsreihenfolgen ohne Wiederholung
• Route Sequencing
• Graph-Puzzles
• strukturelle Grundlage des TSP
• Reihenfolgen von Tasks mit erlaubten Übergängen

Wann verwenden?

Wenn jeder Knoten genau einmal besucht werden muss und die Existenz oder Konstruktion einer gültigen Reihenfolge entscheidend ist.

Fazit

Hamiltonian konzentriert sich auf Knoten, Eulerian auf Kanten. Für kleine Graphen ist Backtracking praktikabel; für größere Instanzen sind DP, Pruning oder spezialisierte Verfahren nötig.