Was besagt der Satz von Dirac?

Der Satz von Dirac (1952) besagt, dass jeder einfache ungerichtete Graph mit n größer oder gleich 3 Knoten, in dem jeder Knoten einen Grad von mindestens n geteilt durch 2 hat, einen Hamiltonkreis besitzt. Dies ist eine hinreichende, aber keine notwendige Bedingung.

Was besagt der Satz von Ore?

Der Satz von Ore (1960) besagt: Wenn für jedes Paar nicht benachbarter Knoten u und v in einem einfachen Graphen mit n größer oder gleich 3 Knoten die Summe ihrer Grade mindestens n ist, dann hat der Graph einen Hamiltonkreis.

Was ist die Warnsdorff-Heuristik?

Die Warnsdorff-Regel (1823) besagt, dass man bei jedem Schritt den nächsten Knoten besuchen sollte, der die wenigsten verbleibenden unbesuchten Nachbarn hat. Diese gierige Regel verkürzt den Backtracking-Baum in der Praxis drastisch.

Hamilton-Pfad-Prüfer

Prüfen Sie, ob ein Graph einen Hamiltonpfad oder Hamiltonkreis enthält. Führt Backtracking mit Warnsdorff-Pruning aus, verifiziert Konnektivitäts- und Grad-Voraussetzungen, testet hinreichende Bedingungen nach Dirac und Ore und zeigt den Zeugenpfad in einer animierten SVG-Visualisierung an.

Schnellbeispiele:

K4 minus Kante 5-Zyklus Linearer Pfad Petersen-Graph Gerichteter Kreis 4×4 Matrix

↔ Kantenliste ▦ Adjazenzmatrix

Graph-Daten

Akzeptiert A-B, A->B, A B, A,B oder Matrixzeilen wie 0 1 1 0. Verwenden Sie Buchstaben, Ziffern oder Unterstriche für Beschriftungen.

Matrix-Labels (optional)

Komma- oder Leerzeichen-getrennte Labels, eines pro Zeile. Standardmäßig A, B, C… falls weggelassen.

Was prüfen?

Graphtyp

Embed Hamilton-Pfad-Prüfer Widget

Hamilton-Pfad-Prüfer

Der Hamilton-Pfad-Prüfer entscheidet, ob ein Graph einen Hamiltonpfad (eine Folge, die jeden Knoten exakt einmal besucht) oder einen Hamiltonkreis (der zusätzlich zum Startknoten zurückkehrt) enthält. Er kombiniert schnelle strukturelle Vorabprüfungen (Konnektivität, Gradanforderungen, Dirac-Satz, Ore-Satz) mit einer Backtracking-Suche, die durch die Warnsdorff-Heuristik optimiert ist, und visualisiert den Zeugenpfad mit einer Schritt-für-Schritt-Animation.

Was ist ein Hamiltonpfad?

Gegeben sei ein Graph G = (V, E) mit n Knoten. Ein Hamiltonpfad ist eine geordnete Folge v₁, v₂, …, v_n aller Knoten, sodass jedes aufeinanderfolgende Paar (v_i, v_i+1) eine Kante von G ist und jeder Knoten exakt einmal vorkommt. Wenn zusätzlich (v_n, v₁) eine Kante ist, handelt es sich um einen Hamiltonkreis.

Hamiltonpfad: v1 — v2 — v3 — … — vn (alle verschieden, jedes Paar ist eine Kante) Hamiltonkreis: v1 — v2 — v3 — … — vn — v1 (schließt zum Start zurück)

Das Problem ist nach William Rowan Hamilton benannt, der 1857 das Ikosianische Spiel erfand — ein Rätsel, bei dem man einen Kreis finden muss, der jeden Knoten eines regulären Dodekaeders exakt einmal besucht.

Warum es schwierig ist: NP-Vollständigkeit

Sowohl das Entscheidungsproblem für Hamiltonpfade als auch für Hamiltonkreise sind NP-vollständig (Karp, 1972). Sofern nicht P = NP gilt, existiert kein Algorithmus in Polynomialzeit, der jede Instanz löst. Im schlechtesten Fall exploriert Backtracking einen Suchbaum der Größe bis zu (n−1)! für einen Kreis. Aus diesem Grund begrenzt der Rechner die Eingabe auf 20 Knoten — eine kleine polynomielle Steigerung von n führt zu einem explosiven Anstieg der Laufzeit.

In der Praxis macht die Warnsdorff-Heuristik (ursprünglich 1823 von Heinrich Warnsdorff für das Springerproblem entwickelt) die Suche auf strukturierten Graphen drastisch schneller: Bei jedem Schritt erweitert der Algorithmus den aktuellen Pfad zum unbesuchten Nachbarn mit der geringsten Anzahl an verbleibenden unbesuchten Nachbarn. Diese gierige Regel verhindert oft, dass sich die Suche "festläuft".

Notwendige Bedingungen — Schnelle Ablehnung

Bevor eine aufwendige Suche gestartet wird, lehnt der Rechner Graphen ab, die unmöglich einen Hamiltonpfad enthalten können:

Konnektivität. Ein Hamiltonpfad muss jeden Knoten besuchen, daher muss der Graph exakt eine zusammenhängende Komponente haben. Bei gerichteten Graphen ist schwacher Zusammenhang erforderlich.
Grad (ungerichtet). Höchstens zwei Knoten dürfen den Grad 1 haben — diese sind die einzigen Kandidaten für die Endpunkte des Pfades. Für einen Hamiltonkreis muss jeder Knoten mindestens den Grad 2 haben.
Grad (gerichtet). Für einen Hamiltonpfad darf höchstens ein Knoten den Eingangsgrad 0 haben (der Start) und höchstens einer den Ausgangsgrad 0 (das Ende). Für einen Hamiltonkreis muss jeder Knoten sowohl Eingangsgrad ≥ 1 als auch Ausgangsgrad ≥ 1 haben.

Hinreichende Bedingungen — Klassische Sätze

Mehrere klassische Sätze liefern hinreichende (aber nicht notwendige) Bedingungen, die einen Hamiltonkreis in ungerichteten einfachen Graphen garantieren. Falls einer dieser Sätze zutrifft, markiert der Rechner das Ergebnis als "GARANTIERT", ohne die Suche zwingend zu benötigen — zeigt aber dennoch einen Zeugenkreis an.

Satz von Dirac (1952)

Wenn G ein einfacher ungerichteter Graph mit n ≥ 3 Knoten ist und jeder Knoten einen Grad von mindestens n / 2 hat, dann besitzt G einen Hamiltonkreis.

δ(G) ≥ n / 2 ⟹ G ist hamiltonsch

Satz von Ore (1960)

Wenn für jedes Paar nicht benachbarter Knoten u und v gilt deg(u) + deg(v) ≥ n, dann hat G einen Hamiltonkreis. Die Ore-Bedingung ist schwächer als die von Dirac, somit impliziert Ore Dirac.

∀ nicht benachbarten u, v: deg(u) + deg(v) ≥ n ⟹ G ist hamiltonsch

Der interne Suchalgorithmus

Wenn die Vorabprüfungen keine Klärung bringen, führt der Rechner eine Backtracking-Suche auf der Adjazenzdarstellung des Graphen aus. Wichtige Taktiken:

Bitmaske für besuchte Knoten. Die besuchten Knoten werden als Bitmaske gespeichert (schneller O(1)-Test für bis zu 20 Knoten).
Warnsdorff-Heuristik. Bei jeder Erweiterung werden Nachbarn in der Reihenfolge ihres verbleibenden Grads (kleinste zuerst) ausprobiert.
Wurzelauswahl. Für einen Hamiltonkreis wird nur ein Startknoten benötigt (Kreise sind rotationsinvariant). Für einen Hamiltonpfad werden Startknoten in aufsteigender Reihenfolge des Ausgangsgrads probiert.
Schritt-Budget. Eine harte Grenze verhindert, dass pathologische Instanzen unendlich laufen; das UI meldet bei Budgetüberschreitung ein "Timeout".

Hamilton vs. Euler

Man verwechselt Hamilton- und Euler-Probleme oft leicht — sie klingen ähnlich, sind aber grundlegend verschieden:

Eigenschaft	Hamiltonpfad / -kreis	Eulerzug / -kreis
Besucht jede…	Knoten exakt einmal	Kante exakt einmal
Komplexität	NP-vollständig	Polynomialzeit (O(n+m))
Bedingung	Keine einfache Charakterisierung	Zusammenhängend + alle Grade gerade (für Kreis)
Benannt nach	W. R. Hamilton (1857)	L. Euler (1736, Königsberger Brücken)
Klassisches Beispiel	Traveling Salesman, Ikosianisches Spiel	Routeninspektion, Postbotenproblem

Unterstützte Eingabeformate

Kantenliste

Eine Kante pro Zeile oder durch Komma getrennt. Unterstützte Trenner: A-B, A B, A,B, A--B, A->B, A<-B. Verwenden Sie ->, um eine gerichtete Interpretation zu erzwingen.

A-B, B-C, C-D, D-A, A-C (ungerichteter Graph mit 5 Kanten) A->B, B->C, C->D, D->A (gerichteter 4-Zyklus)

Adjazenzmatrix

Quadratische Matrix aus 0/1-Werten, eine Reihe pro Zeile, Leerzeichen- oder Komma-getrennt. Geben Sie optionale Labels im Feld "Matrix-Labels" an; ansonsten wird A, B, C… automatisch verwendet.

Anwendung des Prüfers

Eingabeformat wählen — Kantenliste für kleine handgeschriebene Graphen, Adjazenzmatrix für Kopien aus Code oder Lehrbüchern.
Graph einfügen im Textbereich. Bei Matrix-Eingabe optional Knoten-Labels angeben.
Prüfmodus wählen: Nur Pfad, nur Kreis oder beides in einem Durchlauf.
Graphtyp wählen — Die Auto-Erkennung leitet die Gerichtetheit aus dem Pfeilstil (->) oder der Matrix-Symmetrie ab.
Hamilton-Eigenschaft prüfen klicken. Die Ergebnisseite zeigt das Urteil, die Vorabprüfung, Dirac-/Ore-Tests, den Zeugenpfad und eine interaktive Visualisierung.
Zeugen abspielen mit den Play-/Schritt-Reglern.

Fallbeispiel — Der Petersen-Graph

Der berühmte Petersen-Graph (10 Knoten, 15 Kanten) ist ein klassisches Beispiel für einen Graphen mit Hamiltonpfad, aber ohne Hamiltonkreis. Fügen Sie dies in das Feld für die Kantenliste ein:

1-2, 2-3, 3-4, 4-5, 5-1, 6-8, 8-10, 10-7, 7-9, 9-6, 1-6, 2-7, 3-8, 4-9, 5-10

Der Prüfer bestätigt: Hamiltonpfad gefunden (z. B. 1 — 2 — 7 — 10 — 5 — 4 — 9 — 6 — 8 — 3), aber die erschöpfende Suche findet keine Möglichkeit, die Schleife zu schließen.

Häufig gestellte Fragen

Was ist ein Hamiltonpfad?

Ein Hamiltonpfad ist ein Weg durch einen Graphen, der jeden Knoten exakt einmal besucht. Er ist nach William Rowan Hamilton benannt. Da das Problem NP-vollständig ist, gibt es keinen bekannten Algorithmus, der es für alle Graphen in Polynomialzeit löst.

Wie unterscheidet sich ein Hamiltonkreis von einem Hamiltonpfad?

Ein Hamiltonkreis kehrt zu seinem Startknoten zurück. Jeder Hamiltonkreis enthält einen Hamiltonpfad (wenn man die schließende Kante weglässt), aber viele Graphen haben zwar einen Pfad, aber keinen Kreis.

Warum ist die Suche auf 20 Knoten begrenzt?

Hamiltonpfad-Probleme sind NP-vollständig. Die Laufzeit skaliert exponentiell. Über 20 Knoten hinaus sollten spezialisierte Solver wie Concorde oder Integer-Programming-Formulierungen verwendet werden.

Weiterführende Literatur

Zitieren Sie diesen Inhalt, diese Seite oder dieses Tool als:

"Hamilton-Pfad-Prüfer" unter https://MiniWebtool.com/de/hamilton-pfad-pruefer/ von MiniWebtool, https://MiniWebtool.com/

vom miniwebtool-Team. Aktualisiert: 21. April 2026

Sie können auch unseren KI-Mathematik-Löser GPT ausprobieren, um Ihre mathematischen Probleme durch natürliche Sprachfragen und -antworten zu lösen.

Hamilton-Pfad-Prüfer

Hamilton-Pfad-Prüfer

Was ist ein Hamiltonpfad?

Warum es schwierig ist: NP-Vollständigkeit

Notwendige Bedingungen — Schnelle Ablehnung

Hinreichende Bedingungen — Klassische Sätze

Satz von Dirac (1952)

Satz von Ore (1960)

Der interne Suchalgorithmus

Hamilton vs. Euler

Unterstützte Eingabeformate

Kantenliste

Adjazenzmatrix

Anwendung des Prüfers

Fallbeispiel — Der Petersen-Graph

Häufig gestellte Fragen

Was ist ein Hamiltonpfad?

Wie unterscheidet sich ein Hamiltonkreis von einem Hamiltonpfad?

Warum ist die Suche auf 20 Knoten begrenzt?

Weiterführende Literatur

Erweiterte Rechenoperationen:

Ausgewählte Werkzeuge: