Hamilton Decomposition Decision Problem

10

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 .G=(V,E)VViGVi|Vi|=2

Beispiel : Der vollständige zweigliedrige Graph besitzt genau dann eine Hamilton-Zerlegung, wenn m = n ist .Km,nm=n

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.EG

Volker Turau
quelle

Antworten:

17

|Vi|3|Vi|=2

Markus Bläser
quelle