Problem der exakten Überdeckung
aus Wikipedia, der freien Enzyklopädie
Das Problem der exakten Überdeckung (oft mit EXACT COVER notiert) ist ein Entscheidungsproblem der Kombinatorik.
Es fragt, ob für eine endliche Menge X und eine Familie S von Teilmengen von X eine exakte Überdeckung existiert, das heißt eine Teilmenge U von S, so dass jedes Element aus X in genau einer Menge aus U liegt.
Das Problem der exakten Überdeckung gehört zur Liste der 21 klassischen NP-vollständigen Probleme von denen Richard Karp 1972 die Zugehörigkeit zu dieser Klasse zeigen konnte.
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 dann, dass in diesem Fall tatsächlich eine exakte Überdeckung existiert.
