Exacte overdekking

In de wiskunde is exacte overdekking een bijzonder geval van het begrip overdekking van een verzameling. Een exacte overdekking van een verzameling ${\mathcal {S}}$ van deelverzamelingen van een verzameling $X$ is een deelverzameling ${\mathcal {S}}^{*}\subseteq {\mathcal {S}}$ zodat elk element van $X$ juist één keer in een deelverzameling uit ${\mathcal {S}}^{*}$ 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 $X$ en een verzameling ${\mathcal {S}}$ die bestaat uit deelverzamelingen van $X$, dus ${\mathcal {S}}\subseteq {\mathcal {P}}(X)$, waarbij ${\mathcal {P}}(X)$ de machtsverzameling van $X$ voorstelt. Een exacte overdekking van $X$is een deelverzameling ${\mathcal {S}}^{*}$ van ${\mathcal {S}}$ (dus ${\mathcal {S}}^{*}\subseteq {\mathcal {S}}$), die aan twee voorwaarden voldoet:

• De deelverzamelingen in ${\mathcal {S}}^{*}$ zijn paarsgewijs disjunct, met andere woorden elk element in $X$ komt hoogstens in één deelverzameling uit ${\mathcal {S}}^{*}$ voor.
• ${\mathcal {S}}^{*}$ is een overdekking van $X$, met andere woorden elk element in $X$ komt minstens in één deelverzameling uit ${\mathcal {S}}^{*}$ voor.

Een alternatieve definitie luidt als volgt: ${\mathcal {S}}^{*}\subseteq {\mathcal {S}}$ is een exacte overdekking van $X$ als ${\mathcal {S}}^{*}$ een partitie van $X$ vormt.

Verder zijn er nog enkele eigenschappen:

• De exacte overdekking bestaat slechts als elk element van $X$ in minstens één deelverzameling uit ${\mathcal {S}}$ zit.
• Conventioneel wordt aangenomen van de lege verzameling geen deel uitmaakt van de exacte overdekking. Hieruit volgt dat elke deelverzameling in de exacte overdekking ${\mathcal {S}}^{*}$ minstens één element bevat.

Eenvoudig voorbeeld

Stel $X=\{1,2,3,4\}$ en ${\mathcal {S}}=\{A,B,C,D\}$, met

• $A=\varnothing$
• $B=\{1,3\}$
• $C=\{2,3\}$
• $D=\{2,4\}$

De deelverzameling $\{B,D\}=\{\{1,3\},\{2,4\}\}$ is een exacte overdekking van $X$: 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. $\{\varnothing ,B,D\}=\{\{\},\{1,3\},\{2,4\}\}$ is nog steeds een exacte overdekking.

Een andere voorbeeld is $\{B,C,D\}=\{\{1,3\},\{2,3\},\{2,4\}\}$ is een overdekking, maar geen exacte overdekking: elk element zit minstens in één deelverzameling, maar zowel 2 als 3 zitten in meerdere deelverzamelingen.

Bevat ${\mathcal {S}}$ ook een exacte overdekking voor de verzameling $Y=\{1,2,3,4,5\}$? Nee, ${\mathcal {S}}$ 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 ${\mathcal {S}}$ en element in $X$. 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:

• $1\in B$
• $2\in C,D$
• $3\in B,C$
• $4\in D$

Matrixvoorstelling

De relatie kan ook voorgesteld worden middels een incidentiematrix. De matrix bestaat uit een kolom per element in $X$ en een rij per deelverzameling in ${\mathcal {S}}$. 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:

	$A$	$B$	$C$	$D$
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 $X$ en een boog voor elke deelverzameling in ${\mathcal {S}}$.

Graafvoorstelling

Een andere graafvoorstelling maakt gebruik van bipartite graaf. De knopen worden verdeeld in twee disjuncte verzamelingen: een voor de elementen van $X$ en een voor de deelverzameling in ${\mathcal {S}}$. 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 $X$ en een verzameling ${\mathcal {S}}$ van deelverzamelingen van $X$, is een exact hitting set een deelverzameling ${\mathcal {S}}^{*}$ van $X$ zodat elke verzameling uit ${\mathcal {S}}$ exact een element uit ${\mathcal {S}}^{*}$ bevat. Het probleem om een exact hitting set te vinden voor gegeven $X$ en ${\mathcal {S}}$ is equivalent aan het exacte-overdekkingsprobleem.

Voorbeeld

Stel $X=\{1,2,3\}$ en ${\mathcal {S}}=\{S_{1},S_{2},S_{3}\}$ met $S_{1}=\{1,3\}$, $S_{2}=\{2\}$ en $S_{3}=\{1,2\}$.

Een exact hitting set in dit geval is ${\mathcal {S}}^{*}=\{2,3\}$.

Verzamelingenoverdekking

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

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 $n$ dames op een $n$ bij $n$ 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 $9\cdot 9\cdot 9=729$ 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.