Knopenbedekking

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

In de grafentheorie is een knopenbedekking (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):

Vertex-cover.svg

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

Minimum-vertex-cover.svg

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 \tau_t(G).

Voorbeeld: voor een cyclische graaf met n knopen is het knopenbedekkingsgetal  \tau(G) = \lceil {n \over 2} \rceil, en het totale knopenbedekkingsgetal  \tau_t(G) = \lceil {{2 \over 3} n} \rceil. ( \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[bewerken]

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[bewerken]

  • 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 Km,n heeft als knopenbedekkingsgetal min(m,n).

Zie ook[bewerken]

Bronnen, noten en/of referenties