Na matemática, dada uma coleção de subconjuntos de um conjunto X, uma cobertura exata é uma subcoleção de de tal que cada elemento de X está contido em exatamente um subconjunto em . Pode-se dizer que cada elemento de X é coberto por exatamente um subconjunto em . Uma cobertura exata é um tipo de cobertura.

Em ciência da computação, o problema da cobertura exata é um problema de decisão para determinar se uma cobertura exata existe. O problema da cobertura exata é NP-completo ^ M.R. Garey; D.S.Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W.H. Freeman. ISBN 0-7167-1045-5.Esse livro é um classico, desenvolvimento da teoria, então cataloga muitos problemas NP-Completos.e é um dos 21 problemas NP-completos de Karp.Richard M. Karp (1972). "Reducibility among combinatorial problems". In R.E. Miller and J.W. Thatcher (editors). Complexity of Computer Computations. Proc. of a Symp. on the Complexity of Computer Computations. New York: Plenum. pp. 85–103. ISBN 0-3063-0707-3. O problema da cobertura exata é um tipo de problema de satisfação de restrições.

Um problema de cobertura exata pode ser representado por uma matriz de incidência ou por um grafo bipartido.

O Algoritmo X de Knuth é um algoritmo que encontra todas as soluções de um problema de cobertura exata. Dancing Links, comumente conhecido como DLX, é uma técnica sugerida por Donald Knuth para implementar eficientemente seu Algoritmo X em um computador.Knuth, Donald (2000). "Dancing links". arXiv:cs/0011047.

O problema da cobertura exata padrão pode ser generalizado ligeiramente para envolver não apenas "exatamente uma" restrição, mas também "no máximo uma" restrição.

Encontrar blocos de pentaminós e resolver Sudoku são exemplos dignos de nota de problemas de cobertura exata. O problema das 8 damas é um problema de cobertura exata ligeiramente generalizado.

Definição formal

Dada uma coleção de subconjuntos de um conjunto X, uma cobertura exata de X é uma subcoleção de que satisfaz duas condições: A interseção de qualquer subconjuntos distintos em é vazia, ou seja, os subconjuntos em são disjuntos. Em outras palavras, cada elemtento em X está contido em no máximo um subconjunto em . A união dos subconjuntos em é X, ou seja, os subconjuntos em cobrem X. Em outras palavras, cada elemento em X está contido em pelo menos um subconjunto em . Brevemente, uma cobertura exata é "exata" no sentido de que cada elemento em X está contido em exatamente um subconjunto em .

Equivalentemente, uma cobertura exata de X é uma subcoleção de que particiona X.

Para uma cobertura exata de X existir, é necessário que: A união dos subconjuntos em seja X. Em outras palavras, cada elemento em X está contido em pelo menos um subconjunto em . Se o conjunto vazio ∅ está contido em , então não faz diferença ser ou não uma cobertura exata. Portanto é típico assumir que: O conjunto vazio não está em . Em outras palavras, cada subconjunto em contém pelo menos um elemento.

Exemplos básicos Seja = {N, O, E, P} uma coleção de subconjuntos de um conjunto X = {1, 2, 3, 4} tal que: N = { }, O = {1, 3}, E = {2, 4} e P = {2, 3}. A subcoleção {O, E} é uma cobertura exata de X, uma vez que os subconjuntos O = {1, 3} e E = {2, 4} são disjuntos e a união deles é X = {1, 2, 3, 4}.

A subcoleção {N, O, E} é também uma cobertura exata de X. Incluindo o conjunto vazio N = { } não faz diferença, pois é disjunto de todos os subconjuntos e não altera a união.

A subcoleção {E, P} não é uma cobertura exata de X. A interseção dos subconjuntos E e P, {2}, não é vazia: os subconjuntos E e P não são disjuntos. Além disso, a união dos subconjuntos E e P, {2, 3, 4}, não é X = {1, 2, 3, 4}: Nem E nem P cobrem o elemento 1.

Por outro lado, não há cobertura exata—de fato, não há sequer uma cobertura—de Y = {1, 2, 3, 4, 5} porque = {1, 2, 3, 4} é um subconjunto próprio de Y: nenhum dos subconjuntos em contem o elemento 5.

Exemplo detalhado Seja = {A, B, C, D, E, F} a coleção de subconjuntos de um conjunto X = {1, 2, 3, 4, 5, 6, 7} tal que: A = {1, 4, 7}, B = {1, 4}, C = {4, 5, 7}, D = {3, 5, 6}, E = {2, 3, 6, 7} e F = {2, 7}. Então a subcoleção = {B, D, F} é uma cobertura exata, uma vez que cada elemento em X está contido em exatamente um dos subconjuntos: B = {1, 4}, D = {3, 5, 6} ou F = {2, 7}. Além disso, {B, D, F} é o única cobertura exata, como o seguinte argumento demonstra: porque A e B são os únicos subconjuntos contendo 1, uma cobertura exata deve conter A ou B, mas não ambos. Se uma cobertura exata contém A, então esta não contém B, C, E ou F, pois cada um desses subconjuntos tem um elemento em comum com A. Então D é o único subconjunto restante, mas a coleção {A, D} não cobre o elemento 2. Em conclusão, não há cobertura exata contendo A. Por outro lado, se uma cobertura exata contém B, então ela não contém A ou C, pois cada um desses subconjuntos têm um elemento em comum com B. Porque D é o único subconjunto restante contento 5, D deve ser parte de uma cobertura completa. Se uma cobertura completa contém D, então ela não contém E, pois E tem um elemento em comum com D. Então F é o único subconjunto restante, e a coleção {B, D, F} é de fato uma cobertura exata. Veja o exemplo no artigo do Algoritmo X do Knuth para a versão da matriz base desse argumento. Representações

Um problema de cobertura completa é definido por uma relação binária "contém" entre subconjuntos em e elementos em X. Existem diferentes modos equivalentes de representar essa relação.

Representação padrão

A maneira padrão de representar a relação "contém" é listar os elementos em cada subconjunto.

Por exemplo, o exemplo detalhado acima usa esta representação padrão: A = {1, 4, 7}; B = {1, 4}; C = {4, 5, 7}; D = {3, 5, 6}; E = {2, 3, 6, 7}; e F = {2, 7}. Novamente, a subcoleção \mathcal{S}^*= {B, D, F} é uma cobertura exacta, uma vez que cada elemento está contido em exatamente um subconjunto selecionado, como o realce torna claro.

Representação inversa

A relação "contém" entre os subconjuntos e elementos pode ser invertida, listando os subconjuntos cada elemento está contido.

Por exemplo, a relação "contem" no exemplo acima detalhado pode ser representado ao listar os subconjuntos cada elemento está contido em: 1 está contido em A, B; 2 está contido em E, F; 3 está contido em D, E; 4 é contido em A, B, C; 5 está contido em C, D; 6 está contido em D, E; e 7 está contido em A, C, E, F. Mais uma vez, a subcoleção \mathcal{S}^*= {B, D, F} é uma cobertura exata, uma vez que cada elemento está contido em exatamente um subconjunto selecionado, como o realce torna claro.

Quando resolver um problema de cobertura exata , muitas vezes é útil alternar entre o padrão e as representações inversas.

Representações em Matriz e Hiper-grafos

A relação "contém" pode ser representada por uma matriz de incidência.

A matriz inclui uma linha para cada subconjunto em \mathcal{S} e uma coluna para cada elemento em X. A entrada em uma linha e coluna particular é 1 se o subconjunto correspondente contém o elemento correspondente, e é 0 de outra forma. À medida que cada linha representa os elementos contidos no subconjunto correspondente e cada coluna representa os subconjuntos que contém o elemento correspondente, uma matriz de incidência eficazmente fornece tanto  representações padrão e inversas.

Na representação matriz, uma cobertura exata é uma seleção de linhas de modo que cada coluna contém um 1 em exatamente uma linha selecionada.

Por exemplo, a relação "contém" no exemplo detalhado acima pode ser representado por uma matriz 6 × 7 de incidência: Donald Knuth in his paper "Dancing Links" gives this example, as equation (3), only with the rows reordered. 1234567A1001001B1001000C0001101D0010110E0110011F0100001

Novamente, a subcoleção \mathcal{S}^*= {B, D, F} é uma cobertura exata, uma vez que cada elemento está contido em exatamente um subconjunto selecionado, isto é, cada coluna contém um 1 em exatamente uma linha selecionada , como o realce deixa claro.

Veja o exemplo no artigo sobre Algoritmo X de Knuth para uma solução baseada na matriz para o exemplo detalhado acima.

Por sua vez, a matriz de incidência pode ser visto também como a descrição de um hipergrafo. O hipergrafo inclui um nó para cada elemento em X e uma aresta para cada subconjunto em \mathcal{S} ; cada nó está incluído em exatamente uma das arestas que formam a cobertura.

Representação por Grafos

A relação "contém" pode ser representada por um grafo bipartido.

Os vértices do grafo são divididos em dois conjuntos disjuntos, um representando os subconjuntos em \mathcal{S} e outro que representa os elementos em X. Se um subconjunto contém um elemento, uma linha conecta os vértices correspondentes no grafo.

Na representação por grafo, uma cobertura exata é uma seleção de vértices correspondentes aos subconjuntos de tal modo que cada vértice correspondente a um elemento está ligado a exatamente um vértice selecionado.

Por exemplo, a relação "contém" no exemplo detalhado acima pode ser representado por um grafo bipartido com 6 + 7 = 13 vértices:

Mais uma vez, o subcoleção \mathcal{S}^*= {B, D, F} é uma cobertura exata, uma vez que cada elemento está contido em exatamente um subconjunto selecionado, isto é, o vértice correspondente a cada elemento em X é conectado a exatamente um vértice selecionado, como o realce deixa claro.

Problemas equivalentes

Embora o problema canônico de cobertura exata envolve uma coleção de subconjuntos de um conjunto X, a lógica não depende da presença de subconjuntos contendo elementos. Um "problema abstrato de cobertura exata" surge sempre que há uma relação binária entre dois conjuntos P e Q e o objetivo é selecionar um subconjunto de P* de P tal que cada elemento em Q está relacionado com exatamente um elemento em P*. Em geral, os elementos da P representam escolhas e os elementos de Q representam "exatamente um" restrições sobre essas escolhas.

Mais formalmente, dada a relação binária R contido próprio em P × Q entre as séries P e Q, pode-se chamar um subconjunto P* de P uma "cobertura exata abstrata" de Q se cada elemento em Q é R^(−1) relacionada com a exatamente um elemento em P*. Aqui R^(−1)  é o inverso de R.

Em geral,  R^(−1)  restrito a Q × P* é uma função de Q para P*, que mapeia cada um dos elementos Q para o elemento único em que P* que é R-relacionado a aquele elemento em Q. Esta função é para, a menos que P* contenha o "conjunto vazio", ou seja, um elemento que não está relacionado-R a qualquer elemento em Q.

No problema canônico de cobertura exata, P é um conjunto \mathcal{S}

de subconjuntos de X, Q é o conjunto X, R é a relação binária "contém" entre os subconjuntos e elementos, e  R−1 restrito a Q × P* é a função "está contida no" a partir de elementos de subconjuntos selecionados.

Conjunto de acerto exato Em matemática, dada uma coleção \mathcal{S} de subconjuntos de um conjunto X, um conjunto de acerto exato X * é um subconjunto de X tal que cada subconjunto em \mathcal{S}

contém exatamente um elemento em X* . Diz-se que cada subconjunto em \mathcal{S} é atingido por exatamente um elemento em X*.

Em ciência da computação, o problema de conjunto de acerto exato é um problema de decisão para encontrar um conjunto de acerto exato ou então não existência de um.

O problema de conjunto de acerto exato é um problema abstrato de cobertura exata. Na notação acima, P é o conjunto X, Q é uma coleção \mathcal{S} de subconjuntos de X, R é a relação binária "está contido no" entre os elementos e subconjuntos, e R^(-1) restrito a Q × P* é a função "contém" a partir de subconjuntos de elementos selecionados.