Problem der exakten Überdeckung

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Das Problem der exakten Überdeckung (englisch Exact Cover) ist ein Entscheidungsproblem der Kombinatorik. Es gehört zu den 21 klassischen NP-vollständigen Problemen, von denen Richard M. Karp 1972 gezeigt hat, dass sie NP-vollständig sind.

Gegeben ist eine Menge und eine Menge , die Teilmengen von enthält, also , wobei die Potenzmenge von bezeichnet.

Gesucht ist eine Teilmenge von , deren disjunkte Vereinigung ist:

.

Das heißt jedes Element in soll in genau einer der Mengen in vorkommen. Die Mengen in bilden also eine exakte Überdeckung von .

Grafische Darstellung des Beispiels (die exakte Überdeckung ist rot eingezeichnet)

Zum Beispiel sei

und
.

Die Menge

zeigt, dass eine exakte Überdeckung existiert.

Siehe auch[Bearbeiten | Quelltext bearbeiten]