Knopenbedekking

In de grafentheorie is een knopenbedekking of knopenoverdekking (Engels: vertex cover) van een graaf G een verzameling C van knopen uit de graaf waarvoor geldt dat elke kant van G incident^[1] is aan minstens een knoop uit de verzameling C. Anders gezegd: elke kant van G heeft minstens een eindpunt in C. Men zegt dan dat C de kanten van G bedekt. De volgende figuur toont twee voorbeelden van knopenbedekkingen (in het rood):

Een minimum-knopenbedekking is een knopenbedekking met het kleinst mogelijk aantal knopen. Dat aantal noemt men het knopenbedekkingsgetal (Engels: vertex covering number) ${\displaystyle \tau (G)}$. De volgende figuur toont twee minimum-knopenbedekkingen:

Als k knopen in de graaf een clique vormen (zoals de drie linkerknopen in de grafen hierboven), dan maken ten minste k-1 van die knopen deel uit van een minimum-knopenbedekking.

Een totale knopenbedekking van G is een knopenbedekking C met de eigenschap dat elke knoop u in C een buur heeft in C. Met andere woorden: de geïnduceerde subgraaf van een totale knopenbedekking is een samenhangende graaf en bevat geen geïsoleerde knopen. De minimale cardinaliteit van alle totale knopenbedekkingen is het totale knopenbedekkingsgetal ${\displaystyle \tau _{t}(G)}$.

Voorbeeld: voor een cyclische graaf met n knopen is het knopenbedekkingsgetal ${\displaystyle \tau (G)=\lceil {n \over 2}\rceil }$, en het totale knopenbedekkingsgetal ${\displaystyle \tau _{t}(G)=\lceil {{2 \over 3}n}\rceil }$. (${\displaystyle \lceil x\rceil }$ is het kleinste geheel getal dat groter of gelijk is aan x).

Een totale knopenbedekking is tevens een totale dominerende verzameling.

Knopenbedekkingsprobleem

Het beslissingsprobleem: bestaat er voor een gegeven positief geheel getal k een knopenbedekking met ten hoogste k knopen? is een NP-volledig probleem. Dit knopenbedekkingsprobleem is een van de 21 NP-volledige problemen die Richard Karp in 1972 opsomde. Het vinden van een minimum-knopenbedekking en dus van het knopenbedekkingsgetal is een NP-moeilijk optimizatieprobleem. Dit probleem heeft vele toepassingen, onder meer in de studie van (communicatie)netwerken en in de bio-informatica. Praktische algoritmen voor dit probleem vinden een "goede", benaderende maar niet noodzakelijk optimale, oplossing voor een willekeurige graaf.^[2]

Voorbeelden

• De verzameling van alle knopen van G is een knopenbedekking.
• De begin- en eindpunten van een maximale koppeling vormen een knopenbedekking.
• Een volledige bipartiete graaf K_m,n heeft als knopenbedekkingsgetal min(m,n).

Zie ook

• Kantenbedekking