Dominerende verzameling

In de grafentheorie is een dominerende verzameling van een graaf een deelverzameling van de knopen waarmee elke knoop buiten de dominerende verzameling verbonden is.

Voor een graaf ${\displaystyle G=(V,E)}$ heet een deelverzameling ${\displaystyle D}$ van de knopenverzameling ${\displaystyle V}$ een dominerende verzameling, als elke knoop die geen element is van ${\displaystyle D}$ verbonden is met minstens één element van ${\displaystyle D}$,

Het dominantiegetal ${\displaystyle \gamma (G)}$ van de graaf is het aantal knopen in de kleinst mogelijke dominerende verzameling voor ${\displaystyle G.}$

Een deelverzameling ${\displaystyle S}$ van de knopenverzameling ${\displaystyle V}$ heet onafhankelijk, als geen twee knopen in ${\displaystyle S}$ met elkaar zijn verbonden.

Het onafhankelijkheidsgetal ${\displaystyle \beta (G)}$ is de maximale cardinaliteit van een onafhankelijke verzameling in ${\displaystyle G.}$

Aangezien een maximale onafhankelijke verzameling in ${\displaystyle G}$ steeds een dominerende verzameling is, geldt voor elke graaf ${\displaystyle G}$:

${\displaystyle \gamma (G)\leq \beta (G)}$

Een dominerende verzameling is niet leeg, tenzij de graaf zelf leeg is.

De verzameling van alle knopen is triviaal een dominerende verzameling.

In een bipartiete graaf is het dominantiegetal gelijk aan het aantal bogen in een maximumkoppeling. Dit is de stelling van König.

Elke knopenbedekking is een dominerende verzameling, maar het omgekeerde is niet waar. In de figuur is geen enkele van de dominerende verzamelingen een knopenbedekking, want er zijn steeds kanten in de graaf die geen eindpunt in de dominerende verzameling hebben.

Een deelverzameling ${\displaystyle D}$ van ${\displaystyle V}$ is een totale dominerende verzameling wanneer elke knoop in ${\displaystyle V}$, dus ook de knopen in ${\displaystyle D}$, met een element in ${\displaystyle D}$ is verbonden. De minimale kardinaliteit van alle totale dominerende verzamelingen is het totale dominantiegetal ${\displaystyle \gamma _{t}(G)}$. Een totale dominerende verzameling heeft geen geïsoleerde knopen. In de figuur is alleen (c) een voorbeeld van een totale dominerende verzameling.

Het beslissingsprobleem om voor een gegeven graaf ${\displaystyle G}$ en gegeven natuurlijk getal ${\displaystyle k}$ te beslissen of er een dominerende verzameling bestaat met hoogstens ${\displaystyle k}$ knopen is NP-volledig. ${\displaystyle k}$ is strikt kleiner dan het aantal knopen in de graaf. Het is van meer belang het probleem om een minimale dominerende verzameling, dus het dominantiegetal, voor een graaf te vinden. Dit is een NP-moeilijk probleem.