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 X und eine Menge S, die Teilmengen von X enthält, also S \subseteq \mathcal{P}(X), wobei \mathcal{P}(X) die Potenzmenge von X bezeichnet.

Gesucht ist eine Teilmenge U von S, deren Disjunkte Vereinigung X ist:

 X = \dot{\bigcup_{X_i\in U}}X_i .

D. h. jedes Element in X soll in genau einer der Mengen in U vorkommen. Die Mengen in U bilden also eine exakte Überdeckung von X.

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

Zum Beispiel sei

X = \{a, b, c, d, e, f\} und
S = \{ \{a,b\}, \{a,b,c\}, \{c, e\}, \{d, f\}, \{e, f\} \}.

Die Menge

U = \{ \{a,b\}, \{c, e\}, \{d, f\} \}

zeigt, dass eine exakte Überdeckung existiert.

Siehe auch[Bearbeiten]