Problem der exakten Überdeckung

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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.