Allgemein, Informatik, Mathematik

Über den Hamiltonkreis und NP-Vollständigkeit

Im heutigen Artikel möchte ich euch noch einmal mit in die Welt der Graphentheorie nehmen.

Vor einem Weilchen hatte ich euch ja bereits über das Königsberger Brückenproblem berichtet. Dabei ging es darum, dass Leonhard Euler ein einfaches Kriterium angeben konnte, wie sich die Anzahl der Brücken (dargestellt durch Kanten) und der Landteile (dargestellt durch Punkte / Ecken) zueinander verhalten müsste, damit es in einem Graphen einen Eulerkreis geben kann. Dabei ist ein Eulerkreis ein Weg durch den Graphen, bei dem jede Kante genau einmal passiert wird. Wer den kompletten Artikel dazu noch einmal lesen möchte, klickt HIER.

Der Graph zum Königsberger Brückenproblem. Einen Eulerweg gibt es nicht, wie ist es mit einem Hamiltonweg?

Heute geht es um eine ganz leicht veränderte Fragestellung, die aber einen riesigen Unterschied in der Lösung machen wird!

Im 19 Jahrhundert erfand der irische Mathematiker Sir William Rowan Hamilton ein Spiel, das aus einem Spielfeld in Form eines regelmäßigen Dodekaeders bestand und die Ecken mit Städten assoziierte. „The Traveller’s Dodehadecron“ hatte zum Ziel, dass man einen Weg zwischen den Städten finden sollte, sodass man am Ende jede Stadt genau einmal besucht hatte. Die Problemstellung ist im Prinzip die gleiche, wie bei dem Königsberger Brückenproblem. Der Unterschied besteht darin, dass nicht die Kanten jeweils genau einmal passiert werden sollen, sondern die Ecken. Man nennt solch einen Pfad (also Weg) in einem Graphen Hamiltonweg, beziehungsweise Hamiltonkreis, falls er geschlossen ist (also Start- und Endpunkt identisch sind).

Leider ist die Lösung der Frage, ob für einen gegebenen Graph ein Hamiltonweg oder -kreis existiert, ungleich komplizierter und komplexer, als bei dem Eulerkreis. Das Problem gehört zu den 21 klassischen NP-vollständigen Problemen. Diese Liste kombinatorischer und graphentheoretischer Probleme wurde Anfang der 1970er Jahre von Richard Karp, einem amerikanischen Informatiker, aufgestellt. Er wies in einem Artikel auch nach, dass es sich bei diesem Problem tatsächlich um ein NP-vollständiges Problem handelt.

Für einen übersichtlichen Graph, wie hier, kann man leicht überprüfen, ob es einen Hamiltonkreis gibt. Für Computer wird es bei großen Graphen mit vielen Ecken und Kanten schnell sehr aufwändig.

Was genau ein NP-vollständiges Problem ist, ist einen komplett eigenen Artikel wert. Aber grob gesagt handelt es sich um Aufgaben, die extrem viel Zeit (auf Computern) zum Lösen bräuchten. Formall werden nur Entscheidungsprobleme zu dieser Klasse gezählt – das sind Probleme, die mit „Ja“ oder „Nein“ beantwortet werden können. Damit wäre auch die Frage, ob es für einen Graphen einen Hamiltonweg gibt, ein Entscheidungsproblem. Allerdings weiß man noch nicht sicher, ob die NP-vollständigen Probleme vielleicht doch in polynomieller Zeit lösbar sein könnten und wie sie sich genau zu den N- und NP-Problemen verhalten. Das alles gehört zu dem großen N-NP-Problem, was eines der größten, ungelösten Probleme der Mathematik und theoretischen Informatik ist und deswegen auch zu den Milleniumsproblem gehört.

 

Advertisements

Ich freue mich auf deinen Kommentar!

Trage deine Daten unten ein oder klicke ein Icon um dich einzuloggen:

WordPress.com-Logo

Du kommentierst mit Deinem WordPress.com-Konto. Abmelden /  Ändern )

Google+ Foto

Du kommentierst mit Deinem Google+-Konto. Abmelden /  Ändern )

Twitter-Bild

Du kommentierst mit Deinem Twitter-Konto. Abmelden /  Ändern )

Facebook-Foto

Du kommentierst mit Deinem Facebook-Konto. Abmelden /  Ändern )

Verbinde mit %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.