Studium, Ausbildung und Beruf

web uni-protokolle.de
 powered by
NachrichtenLexikonProtokolleBücherForenSonntag, 27. Mai 2012 

Hamiltonkreis


Dieser Artikel von Wikipedia ist u.U. veraltet. Die neue Version gibt es hier.
Sei G =( V E ) ein ( gerichteter ) Graph ohne Mehrfachkanten . Ist H ein Pfad bzw. Kreis der alle Knoten aus V enthält so nennt man W Hamiltonpfad bzw. Hamiltonkreis . Falls ein Graph G einen Hamiltonkreis besitzt so nennt man G hamiltonisch . Das Problem zu entscheiden ob ein Graph einen Hamiltonpfad besitzt bzw. ob er ist nennt man Hamiltonpfad-Problem bzw. Hamiltonkreis-Problem .

In Zusammenhang mit dem Problem des Handlungsreisenden wird eine wichtige Anwendung von Hamiltonkreisen

Wichtige Aussagen und Sätze

Sind x und y zwei nicht benachbarte Knoten in einem Graphen G deren Gradsumme d G ( x )+ d G ( y ) mindestens so groß wie die Anzahl Knoten | V ( G )| in G ist so ist G hamiltonisch genau dann wenn G +{ x y } hamiltonisch ist. Ist G 0 ... G k eine Folge von ungerichteten Graphen wobei G i aus G i -1 für jedes i aus {1 ... k } durch Hinzufügen einer Kante { x y } mit d G i -1 ( x )+ d G i -1 ( y )&ge| V ( G i -1 )| entsteht und d G k ( x )+ d G i k ( y )&le| V ( G i -1 )| für jedes Paar in G k nicht benachbarter Knoten x und y so bezeichnet man G k als Hamiltonabschluss von G 0 . Ein weiterer Satz besagt dass der für jeden Graphen eindeutig ist. Ein Graph daher genau dann hamiltonisch wenn sein Hamiltonabschluss ist.

Daraus lassen sich folgende hinreichender Bedingungen hamiltonische Graphen ableiten. Unter anderem ist ein G mit mindestens drei Knoten hamiltonisch falls:

  1. d G ( x )+ d G ( y )≥| V ( G )| für alle { x y } die nicht zu E ( G ) gehören oder
  2. der Minimalgrad mindestens | V ( G )|/2 ist oder
  3. die Knotenzusammenhangszahl von G mindestens so groß wie die Stabilitätszahl von G ist.
Diese Aussagen sind scharf in dem das es Gegenbeispiele bei minimal schwächeren Voraussetzungen

Graphentheoretische Probleme und ihre algorithmische Komplexität

Die Probleme Hamiltonpfad und Hamiltonkreis sind NP-vollständig . Entsprechend schwierig gestaltet es sich dann zusätzlich einen Hamiltonpfad bzw. einen Hamiltonkreis in Graphen zu finden sofern dieser existiert. Probleme gerichteten Hamiltonkreisen lassen sich auf 3-SAT polynominal reduzieren. Probleme mit ungerichtete Hamiltonkreisen sich auf gerichtete reduzieren. Das Problem des Handlungsreisenden lässt sich auf Probleme mit ungerichteten reduzieren.




Bücher zum Thema Hamiltonkreis

Dieser Artikel von Wikipedia unterliegt der GNU FDL.

Impressum • Lesezeichen setzen • Seite versenden • Seite drucken

HTML-Code zum Verweis auf diese Seite:
<a href="http://www.uni-protokolle.de/Lexikon/Hamiltonscher_Graph.html">Hamiltonkreis </a>