Hamiltonkreisproblem

Stichpunkte

Allgemein
	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
	der alle Knoten aus V enthält
	Kreis
	so nennt man H Hamiltonpfad bzw
	Hamiltonkreis
	so nennt man G hamiltonisch
	Falls ein Graph G einen Hamiltonkreis besitzt
	bzw. ob er hamiltonisch ist
	ob ein gegebener Graph einen Hamiltonpfad besitzt
	nennt man Hamiltonpfadproblem bzw
	Das Problem zu entscheiden
	Hamiltonkreisproblem
	In Zusammenhang mit dem Problem des Handlungsreisenden wird eine wichtige Anwendung von Hamiltonkreisen deutlich. [Bearbeiten]
Wichtige Aussagen und Sätze
	y} hamiltonisch ist
	Sind x und y zwei nicht benachbarte Knoten
	in einem ungerichteten Graphen G
	deren Gradsumme dG(x)+dG(y) mindestens so groß wie die Anzahl der Knoten |V(G)| in G ist
	so ist G hamiltonisch genau dann
	wenn G+{x
	k} durch Hinzufügen einer Kante {x
	y} mit dGi-1(x)+dGi-1(y)≥|V(Gi-1)| entsteht und dGk(x)+dGik(y)≤|V(Gi-1)| für jedes Paar in Gk nicht benachbarter Knoten x und y
	wobei Gi aus Gi-1 für jedes i aus {1
	...
	so bezeichnet man Gk als Hamiltonabschluss von G0
	Ist G0
	...
	Gk eine Folge von ungerichteten Graphen
	dass der Hamiltonabschluss für jeden Graphen eindeutig ist
	Ein weiterer Satz besagt
	Ein Graph ist daher genau dann hamiltonisch
	wenn sein Hamiltonabschluss hamiltonisch ist
	Daraus lassen sich folgende hinreichender Bedingungen für hamiltonische Graphen ableiten
	dass es Gegenbeispiele bei minimal schwächeren Voraussetzungen gibt. [Bearbeiten]
	y} die nicht zu E(G) gehören oder der Minimalgrad mindestens |V(G)|/2 ist oder die Knotenzusammenhangszahl von G mindestens so groß wie die Stabilitätszahl von G ist. Diese Aussagen sind scharf in dem Sinne
	Unter anderem ist ein Graph G mit mindestens drei Knoten hamiltonisch falls: dG(x)+dG(y)≥|V(G)| für alle {x
Graphentheoretische Probleme und ihre algorithmische Komplexität
	Die Probleme Hamiltonpfad und Hamiltonkreis sind NP-vollständig
	zusätzlich einen Hamiltonpfad bzw. einen Hamiltonkreis in einem Graphen zu finden
	Entsprechend schwierig gestaltet es sich dann auch
	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. en:Hamiltonian path ja:�ミルトン路 zh:哈密尔顿图

Dieser Artikel basiert auf dem Artikel Hamiltonkreisproblem aus der freien Enzyklopädie wikipedia und steht unter der GNU Lizenz für freie Dokumentation. In der wikipedia ist eine Liste der Autoren verfügbar.