Was ist ein Hamiltonweg?

Es ist ein Weg durch einen Graphen, der jeden Knoten genau einmal besucht und dabei nur Kanten verwendet, die im Graphen existieren — er muss nicht zu seinem Startpunkt zurückkehren (das würde ihn stattdessen zu einem Hamiltonkreis machen).

Warum ist es schwer, einen Hamiltonweg zu finden?

Das Hamiltonweg-Problem ist NP-vollständig, was bedeutet, dass kein Algorithmus bekannt ist, der es dramatisch schneller löst als das Ausprobieren von Kombinationen von Ordnungen, und die Anzahl der möglichen Ordnungen wächst faktoriell mit der Anzahl der Knoten.

Warum ist dieser Rechner auf 10 Knoten beschränkt?

Die Backtracking-Suche erkundet einen Suchraum, der im schlimmsten Fall faktoriell wachsen kann. Zehn Knoten hält diese Suche für ein browserbasiertes Werkzeug angenehm schnell, während weiterhin die meisten handeingegebenen Graphenbeispiele abgedeckt werden, die Menschen überprüfen möchten.

Wie funktioniert die Backtracking-Suche?

Sie baut einen Weg Knoten für Knoten auf und erweitert immer zu einem unbesuchten Nachbarn; erreicht sie eine Sackgasse, in der kein unbesuchter Nachbar verfügbar ist, macht sie einen Rückzieher (macht den letzten Schritt rückgängig) und probiert einen anderen Nachbarn, wiederholt dies von jedem möglichen Startknoten aus.

Was ist der Unterschied zwischen einem Hamiltonweg und einem Hamiltonkreis?

Ein Hamiltonweg muss nur jeden Knoten einmal besuchen; ein Hamiltonkreis erfordert zusätzlich, dass der Weg zu seinem Startknoten zurückkehrt und eine geschlossene Schleife bildet — beide sind NP-vollständig zu erkennen.

Hat jeder Graph einen Hamiltonweg?

Nein — viele Graphen, besonders spärliche oder unverbundene, haben überhaupt keinen. Ein unverbundener Graph kann niemals einen Hamiltonweg haben, da der Weg zwischen Komponenten springen müsste, ohne dass eine Kante zur Verfügung steht.

Wie unterscheidet sich das vom Minimaler-Spannbaum-Rechner?

Ein minimaler Spannbaum verbindet jeden Knoten mit einer Baumstruktur (die sich verzweigen kann), während ein Hamiltonweg eine einzelne unverzweigte Linie ist, die jeden Knoten genau einmal besucht — eine viel restriktivere Anforderung.

Wo wird das Hamiltonweg-Problem im echten Leben verwendet?

Es ist eng mit dem Problem des Handlungsreisenden verwandt und erscheint in der Routenplanung, der DNA-Sequenzierung (Fragmentzusammenstellung) und Rätselproblemen wie dem Springerproblem auf einem Schachbrett.

Hamiltonweg-Prüfer — Finden Sie einen Weg, der jeden Knoten genau einmal besucht

Unser Hamiltonweg-Prüfer sucht nach einem Weg durch einen Graphen, der jeden Knoten genau einmal besucht, indem er jeden möglichen Startknoten ausprobiert und durch mögliche Routen zurückverfolgt, wobei Ihr Graph als einfache Text-Kantenliste eingegeben wird (z. B. A-B, B-C, C-D).

Kurzantwort

Geben Sie Ihren Graphen als Kantenliste ein (bis zu 10 Knoten), um sofort einen Hamiltonweg zu suchen — eine Route, die jeden Knoten genau einmal besucht — über Backtracking.

Kanten (kommagetrennt)

Geben Sie Kanten als KnotenA-KnotenB ein, z. B. A-B, B-C, C-D. Maximal 10 Knoten.

So verwenden Sie Hamiltonweg-Prüfer — Jeden Knoten Einmal Besuchen Online

1
Geben Sie Ihren Graphen als kommagetrennte Kantenliste ein, z. B. A-B, B-C, C-D.
2
Klicken Sie auf 'Berechnen', um nach einem Hamiltonweg zu suchen.
3
Sehen Sie sich den gefundenen Weg an, oder die Bestätigung, dass keiner existiert.

Warum Hamiltonweg-Prüfer — Jeden Knoten Einmal Besuchen Online verwenden?

Ein Hamiltonweg besucht jeden Knoten in einem Graphen genau einmal — anders als ein Eulerweg, bei dem es darum geht, jede Kante zu besuchen, geht es hier darum, jeden Knoten zu besuchen. Zu bestimmen, ob einer existiert, ist im Allgemeinen NP-vollständig, was bedeutet, dass kein Algorithmus bekannt ist, der dramatisch schneller ist als das systematische Ausprobieren von Möglichkeiten, sodass dieser Rechner Backtracking-Suche verwendet: einen Weg Knoten für Knoten aufbauen und zurückverfolgen, wann immer eine Sackgasse erreicht wird, wobei jeder mögliche Startknoten ausprobiert wird. Da der Suchraum faktoriell mit der Graphgröße wächst, ist dieser Rechner bewusst auf höchstens 10 Knoten beschränkt, wo eine erschöpfende Backtracking-Suche immer noch sofort abgeschlossen wird.

Hamiltonweg-Prüfer — Finden Sie einen Weg, der jeden Knoten genau einmal besucht

Kurzantwort

So verwenden Sie Hamiltonweg-Prüfer — Jeden Knoten Einmal Besuchen Online

Warum Hamiltonweg-Prüfer — Jeden Knoten Einmal Besuchen Online verwenden?

Häufig gestellte Fragen

Ähnliche Tools

Handlungsreisenden-Löser — Exakte Held-Karp-DP Online

Topologische-Sortierung-Rechner — Kahn-Algorithmus Online

Minimaler-Spannbaum-Rechner — Kruskal-Algorithmus Online