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 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.

Karps 21 NP-vollständige Probleme

Wikimedia Foundation.

Игры ⚽ Поможем решить контрольную работу

Schlagen Sie auch in anderen Wörterbüchern nach:

Überdeckung — steht für: Überdeckung (Mathematik), ein mathematischer Begriff der Topologie Kanonische Überdeckung, ein Begriff aus der Informatik das Problem der exakten Überdeckung in der Kombinatorik die notwendige Überdeckung von Luftbildern für die… … Deutsch Wikipedia
Erfüllbarkeitsproblem der Aussagenlogik — Das Erfüllbarkeitsproblem der Aussagenlogik (SAT, von engl. satisfiability) ist ein Entscheidungsproblem. Es fragt, ob eine aussagenlogische Formel erfüllbar ist. Anwendungen finden sich unter anderem in der Komplexitätstheorie, Verifikation und… … Deutsch Wikipedia
Hitting-Set-Problem — Das Hitting Set Problem ist ein NP vollständiges Problem aus der Mengentheorie. Es gehört zur Liste der 21 klassischen NP vollständigen Probleme von denen Richard M. Karp 1972 die Zugehörigkeit zu dieser Klasse zeigen konnte. Gegeben ist eine… … Deutsch Wikipedia
Tanz der Kanten — ist eine Technik zum effektiven Umgang mit Listen in der Informatik. Sie ermöglicht es auf unkomplizierte Weise, Elemente in Listen zu entfernen oder einzufügen. Element B wird aus der Liste entfernt. Zum Beispiel habe das Element B einer Liste… … Deutsch Wikipedia
Feedback Vertex Set — Der Begriff Feedback Vertex Set bzw. kreiskritische Knotenmenge bezeichnet in der Komplexitätstheorie ein graphentheoretisches Entscheidungsproblem, das NP vollständig ist. Definition Es fragt, ob es zu einem ungerichteten Multigraphen G = (V,E) … Deutsch Wikipedia
Exact Cover — Das Problem der exakten Überdeckung (englisch Exact Cover) ist ein Entscheidungsproblem der Kombinatorik. Gegeben ist eine Menge X und eine Menge S, die Teilmengen von X enthält, also , wobei die Potenzmenge von X bezeichnet. Gesucht ist eine… … Deutsch Wikipedia
Karps 21 NP-vollständige Probleme — Eines der bedeutendsten Resultate der Komplexitätstheorie ist der von Stephen Cook im Jahr 1971 erbrachte Nachweis, dass das Erfüllbarkeitsproblem der Aussagenlogik (meist nur kurz SAT genannt) NP vollständig ist. 1972 griff Richard Karp diese… … Deutsch Wikipedia
Mengenüberdeckungsproblem — Das Mengenüberdeckungsproblem (oft mit set covering Problem notiert) ist ein Entscheidungsproblem der Kombinatorik. Es fragt, ob zu einer Menge U und n Teilmengen Sj von U und einer natürlichen Zahl eine Vereinigung von k oder weniger Teilmengen… … Deutsch Wikipedia
Steinerbaumproblem — Das Steinerbaumproblem (oft mit STEINER TREE notiert), ein nach dem Schweizer Mathematiker Jakob Steiner benanntes Problem der Graphentheorie, ist eine Verallgemeinerung des Problems des minimalen Spannbaums. Beim Steinerbaumproblem sucht man in… … Deutsch Wikipedia
Hamiltonkreisproblem — Ein Hamiltonkreis ist ein geschlossener Pfad in einem Graphen, der jeden Knoten genau einmal enthält. Ob ein solcher Kreis in einem gegebenen Graph besteht, ist ein fundamentales Problem der Graphentheorie. Im Gegensatz zum leicht lösbaren… … Deutsch Wikipedia

Academic dictionaries and encyclopedias

Problem der exakten Überdeckung

Schlagen Sie auch in anderen Wörterbüchern nach:

Share the article and excerpts

Academic dictionaries and encyclopedias

Deutsch Wikipedia

Problem der exakten Überdeckung

Schlagen Sie auch in anderen Wörterbüchern nach:

Share the article and excerpts

Direct link