Problem der exakten Überdeckung

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

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 sind eine Menge und eine Menge von nichtleeren Teilmengen von , 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 ( ist eine Partition 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]