Dominerende verzameling

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken
Dominerende verzamelingen zijn aangegeven door roodgekleurde knopen. (a) en (b) zijn onafhankelijke dominerende verzamelingen. (a) is geen minimale dominerende verzameling, (b) en (c) wel.

Dominerende verzameling is een begrip uit de grafentheorie.

Voor een graaf G = (VE) is een deelverzameling D van de knopenverzameling V een dominerende verzameling wanneer elke knoop die geen element is van D verbonden is met minstens een element van D.

Het dominantiegetal van de graaf, γ(G), is het aantal knopen in de kleinst mogelijke dominerende verzameling voor G, met andere woorden de minimale cardinaliteit van een dominerende verzameling.

Enkele eigenschappen[bewerken]

  • Een dominerende verzameling is nooit leeg (behalve als de graaf zelf leeg is).
  • De verzameling V van alle knopen is vanzelfsprekend altijd een dominerende verzameling.
  • In een bipartiete graaf G is het dominantiegetal gelijk aan het aantal bogen in een maximumkoppeling in G (stelling van König).

Verband met onafhankelijke verzameling[bewerken]

Een deelverzameling S van V is onafhankelijk wanneer geen twee knopen in S met elkaar verbonden zijn in de graaf.

Het onafhankelijkheidsgetal β(G) is de maximale cardinaliteit van een onafhankelijke verzameling in G.

Er geldt: een maximale onafhankelijke verzameling in G is steeds een dominerende verzameling. Dus γ(G) ≤ β(G) voor elke G.

Totale dominerende verzameling[bewerken]

Een deelverzameling D van V is een totale dominerende verzameling wanneer elke knoop in V (dus ook de knopen in D) verbonden is met een element in D. De minimale cardinaliteit van alle totale dominerende verzamelingen is het totale dominantiegetal γt(G). Een totale dominerende verzameling heeft geen geïsoleerde knopen. In de figuur is enkel (c) een voorbeeld van een totale dominerende verzameling.

Verband met knopenbedekking[bewerken]

Elke knopenbedekking is een dominerende verzameling. Het omgekeerde is niet waar; in de figuur hiernaast 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.

Complexiteit[bewerken]

Het beslissingsprobleem om voor een gegeven graaf G en gegeven natuurlijk getal k te beslissen of er een dominerende verzameling bestaat met hoogstens k knopen is NP-volledig. k is strikt kleiner dan het aantal knopen in de graaf.

Van meer belang is het probleem om een minimale dominerende verzameling, en dus het dominantiegetal, te vinden voor een graaf G. Dit is een NP-moeilijk probleem.