Sei ein ungerichteter Graph. Eine Zerlegung von V in disjunkte Teilmengen V i wird als Hamilton-Zerlegung von G bezeichnet, wenn der durch jede Menge V i induzierte Teilgraph entweder ein Hamilton-Graph ist oder aus einer einzelnen Kante mit | besteht V i | = 2 .
Beispiel : Der vollständige zweigliedrige Graph besitzt genau dann eine Hamilton-Zerlegung, wenn m = n ist .
Ich suche nach einem Algorithmus, der entscheidet, ob ein gegebener Graph eine Hamilton-Zerlegung besitzt. Ist dieses Entscheidungsproblem NP-vollständig? Wenn nicht, wie können wir eine solche Zerlegung finden?
Anmerkung : In der Literatur bezeichnet eine Hamilton-Zerlegung häufig eine Zerlegung der Kanten von G, so dass die induzierten Teilgraphen Hamilton sind. Im Gegensatz dazu interessiert mich eine Zerlegung der Eckpunkte.