Exacte overdekking
In de wiskunde is exacte overdekking een bijzonder geval van het begrip overdekking van een verzameling. Een exacte overdekking van een verzameling  van deelverzamelingen van een verzameling  is een deelverzameling  zodat elk element van  juist één keer in een deelverzameling uit  zit.

Het beslissingsprobleem over het bestaan van een exacte overdekking en het vinden van de exacte overdekking zijn gerelateerde problemen uit de computationele meetkunde. Het vinden van een overdekking is NP-volledig en een van Karps 21 NP-volledige problemen.

Formele definitie
Gegeven een verzameling  en een verzameling  die bestaat uit deelverzamelingen van , dus , waarbij  de machtsverzameling van  voorstelt. Een exacte overdekking van is een deelverzameling  van  (dus ), die aan twee voorwaarden voldoet:

 De deelverzamelingen in  zijn paarsgewijs disjunct, met andere woorden elk element in  komt hoogstens in één deelverzameling uit  voor.
  is een overdekking van , met andere woorden elk element in  komt minstens in één deelverzameling uit  voor.

Een alternatieve definitie luidt als volgt:  is een exacte overdekking van  als  een partitie van  vormt.

Verder zijn er nog enkele eigenschappen:

 De exacte overdekking bestaat slechts als elk element van  in minstens één deelverzameling uit  zit.
 Conventioneel wordt aangenomen van de lege verzameling geen deel uitmaakt van de exacte overdekking. Hieruit volgt dat elke deelverzameling in de exacte overdekking  minstens één element bevat.

Eenvoudig voorbeeld 
Stel  en , met

 
 
  
 

De deelverzameling  is een exacte overdekking van : elk element is hoogstens in één deelverzameling en elk element is ook in minstens één deelverzameling. Het toevoegen van de lege verzameling aan deze exacte overdekking heeft geen effect, d.w.z.  is nog steeds een exacte overdekking.

Een andere voorbeeld is  is een overdekking, maar geen exacte overdekking: elk element zit minstens in één deelverzameling, maar zowel 2 als 3 zitten in meerdere deelverzamelingen.

Bevat  ook een exacte overdekking voor de verzameling ? Nee,  bevat zelfs geen overdekking: 5 komt in geen enkele deelverzameling voor.

Voorstelling 
Het probleem van het vinden van exacte overdekkingen wordt gedefinieerd door de tweeplaatsige relatie "element van" tussen deelverzamelingen uit  en element in . Deze relatie kan op meerdere manieren voorgesteld worden.

Standaardvoorstelling 
De gebruikelijke manier om de relatie "element van" voor te stellen is het oplijsten van de elementen in de deelverzamelingen. Dit wordt bijvoorbeeld gebruikt door het voorbeeld hierboven.

Inverse voorstelling 
Zoals de relatie geïnverteerd kan worden, kan ook de voorstelling dat ook. Dit betekent voor elk element vermelden in welke deelverzamelingen het zit. Voor het voorbeeld wordt dit:

Matrixvoorstelling 
De relatie kan ook voorgesteld worden middels een incidentiematrix. De matrix bestaat uit een kolom per element in  en een rij per deelverzameling in . Als een element een element is van een bepaalde deelverzameling, zal het overeenkomstige element in de matrix 1 zijn, anders 0. Voor het voorbeeld van hierboven wordt dit:

{| border="1" cellpadding="5" cellspacing="0"
! !!!!!!!!
|-
! 1
| 0 || 1 || 0 || 0 
|-
!2
| 0 || 0 || 1 || 1
|-
!3
| 0 || 1 || 1 || 0 
|-
!4
| 0 || 0 || 0 || 1 
|}

Deze voorstelling is nauw verwant aan een algoritme voor het vinden van exacte overdekkingen genaamd Algorithm X. Het werd geformuleerd door Donald Knuth en is een recursief algoritme dat gebruik maakt van backtracking. Als het geïmplementeerd wordt op de efficiënte wijze zoals beschreven door Knuth spreekt men van DLX. Hierbij wordt een techniek gebruikt die door Knuth omschreven wordt als dancing links.

Deze matrix kan op zijn beurt voorgesteld worden als een hypergraaf. Deze graaf bevat een knoop voor elk element van  en een boog voor elke deelverzameling in .

Graafvoorstelling 
Een andere graafvoorstelling maakt gebruik van bipartite graaf. De knopen worden verdeeld in twee disjuncte verzamelingen: een voor de elementen van  en een voor de deelverzameling in . Als een deelverzameling een element bevat, zal er een boog zijn die de knoop van dat element verbindt met de deelverzameling waartoe het element behoort.

Verwante problemen

Exact hitting set
Voor een verzameling  en een verzameling  van deelverzamelingen van , is een exact hitting set een deelverzameling  van  zodat elke verzameling uit  exact een element uit  bevat. Het probleem om een exact hitting set te vinden voor gegeven  en  is equivalent aan het exacte-overdekkingsprobleem.

Voorbeeld
Stel  en  met ,  en . 

Een exact hitting set in dit geval is .

Verzamelingenoverdekking
Wanneer men in de definitie de eis dat de elementen van  disjuncte verzamelingen zijn laat vallen, en men dus toelaat dat een element uit  in meer dan één deelverzameling uit  voorkomt, krijgt men het verzamelingenoverdekkingsprobleem (set cover problem). Als beslissingsprobleem luidt dit: is het mogelijk om voor een gegeven positief geheel getal , een selectie  te maken van ten hoogste  verzamelingen uit , zodat hun unie gelijk is aan ? Het corresponderende optimalisatieprobleem zoekt naar de kleinst mogelijke  (dit wil zeggen die met het kleinst aantal selecties uit ).

Toepassingen
Dit zijn enkele van de problemen die men kan reduceren tot een exacte-overdekkingsprobleem:

 het betegelen van een schaakbord met de 12 pentomino's (polyomino's met vijf vierkanten). De vier centrale vakjes van het bord blijven daarbij vrij. Elke pentomino kan slechts eenmaal geplaatst worden, en elk van de 60 vakjes moet door een en slechts een polyomino bedekt worden.

 het achtdamesprobleem: plaats  dames op een  bij  schaakbord zodanig dat ze elkaar niet kunnen aanvallen. In elke rij en elke kolom van het bord moet dan exact een dame staan, evenals in elke diagonale rij.

 Sudoku: in een vierkant van 9 op 9 zijn er  kandidaten (toewijzingen van een van negen cijfers aan elk vakje). Elk vakje moet exact een cijfer bevatten; elke rij, kolom of deelvierkant van 3 op 3 moet exact eenmaal elk cijfer van 1 tot 9 bevatten. Deze voorwaarden kan men formuleren als verzamelingen van toewijzingen (324 in totaal: 9x9 voor vakjes, rijen, kolommen en deelvierkanten). Dit geeft een matrix van 729 rijen en 324 kolommen.

NP-volledig probleem
Complexiteitstheorie