Onafhankelijke verzameling

In de grafentheorie verstaat men onder onafhankelijke verzameling of stabiele verzameling (independent set in het Engels) van een graaf, een deelverzameling van de knopen van die graaf die twee aan twee niet verbonden zijn door een zijde.

In deze graaf vormen de blauwe knopen een grootste onafhankelijke verzameling.

Definities

Stel G=(V,E) is een niet-gerichte enkelvoudige graaf met knopen V en zijden E, en U is een deelverzameling van V. Als voor elke twee verschillende knopen v en w uit U geldt dat ze niet door een zijde zijn verbonden, dan is U een stabiele of onafhankelijke verzameling van G.

Een onafhankelijke verzameling U van G is maximaal als men geen andere knoop v aan U kan toevoegen, zodanig dat U samen met v een onafhankelijke verzameling vormt.

Onder alle maximale onafhankelijke verzamelingen is er minstens een die het grootste aantal knopen heeft. Die noemt men de grootste onafhankelijke (of stabiele) verzameling, en het aantal knopen ervan is het stabiliteitsgetal of onafhankelijkheidsgetal.

Eigenschappen

Elke onafhankelijke verzameling van een graaf G vormt een clique in de complementgraaf van G en vice versa. Deze twee begrippen zijn dus complementair.

Problemen

Het beslissingsprobleem om van een graaf G te bepalen of die een stabiele verzameling van minstens k knopen bevat, noemt men het stabiliteitsprobleem. Verwant hiermee is het zoekprobleem: bepaal de grootste stabiele verzameling, of anders gezegd: bepaal het stabiliteitsgetal van de graaf. Het stabiliteitsprobleem is een klassiek probleem uit de complexiteitstheorie. Uit de complementariteit van stabiele verzamelingen en cliques volgt dat het stabiliteitsprobleem complementair is met het cliqueprobleem, en net als het cliqueprobleem NP-volledig is. Van een perfecte graaf kan men het stabiliteitsgetal in polynomiale tijd berekenen.

Het vinden van een grootste onafhankelijke verzameling is een NP-moeilijk probleem.