Exact Cover

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

Das Problem der exakten Überdeckung gehört zu den 21 klassischen NP-vollständigen Problemen, wie Richard Karp 1972 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, dass eine exakte Überdeckung existiert.


Wikimedia Foundation.

Игры ⚽ Нужен реферат?

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

  • Exact cover — In mathematics, given a set X and a collection mathcal{S} of subsets of X , an exact cover mathcal{S}^* is a subcollection of mathcal{S} such that every element in X is contained in exactly one set in mathcal{S}^*. An exact cover is a kind of… …   Wikipedia

  • Cover Her Face (novel) — infobox Book | name = Cover Her Face title orig = translator = image caption = author = P. D. James cover artist = country = United Kingdom language = English series = Adam Dalgliesh #1 genre = Crime, Mystery novel publisher = Faber and Faber… …   Wikipedia

  • Cover meter — A cover meter is an instrument to locate rebars and measure the exact concrete cover. Rebar detectors are less sophisticated devices that can only locate metallic objects below the surface. Due to the cost effective design, the pulse induction… …   Wikipedia

  • Vertex cover — In the mathematical discipline of graph theory, a vertex cover of a graph is a set of vertices such that each edge of the graph is incident to at least one vertex of the set. The problem of finding a minimum vertex cover is a classical… …   Wikipedia

  • Algorithmics of sudoku — The class of Sudoku puzzles consists of a partially completed row column grid of cells partitioned into N regions or zones each of size N cells, to be filled in using a prescribed set of N distinct symbols (typically the numbers {1, ..., N }), so …   Wikipedia

  • Dancing Links — In computer science, Dancing Links, also known as DLX, is the technique suggested by Donald Knuth to efficiently implement his Algorithm X.[1] Algorithm X is a recursive, nondeterministic, depth first, backtracking algorithm that finds all… …   Wikipedia

  • Knuth's Algorithm X — Donald Knuth s Algorithm X is a recursive, nondeterministic, depth first, backtracking algorithm that finds all solutions to the exact cover problem represented by a matrix A consisting of 0s and 1s.The goal is to select a subset of the rows so… …   Wikipedia

  • Set packing — is a classical NP complete problem in computational complexity theory and combinatorics, and was one of Karp s 21 NP complete problems. Suppose we have a finite set S and a list of subsets of S. Then, the set packing problem asks if some k… …   Wikipedia

  • Couverture exacte — Problème de la couverture exacte Le problème de la couverture exacte est un problème d optimisation combinatoire NP complet qui fait partie des 21 problèmes NP complets de Karp. Sommaire 1 Énoncé 1.1 Exemple 1 1.2 Exemple 2 …   Wikipédia en Français

  • Probleme de la couverture exacte — Problème de la couverture exacte Le problème de la couverture exacte est un problème d optimisation combinatoire NP complet qui fait partie des 21 problèmes NP complets de Karp. Sommaire 1 Énoncé 1.1 Exemple 1 1.2 Exemple 2 …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”