Complementgraaf

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken
De Petersen-graaf, links, met zijn complementgraaf

In de grafentheorie is de complementgraaf van een enkelvoudige graaf , een enkelvoudige graaf met dezelfde knopen als , die met een zijde verbonden zijn als en slechts als ze in niet met een zijde zijn verbonden.

De complementgraaf van een graaf wordt vaak aangeduid met .

Formeler is de complementgraaf van met knopen en zijden , gegeven door het paar , waarvoor geldt:

=


De complementgraaf van een complementgraaf is de oorspronkelijke graaf.

Een graaf die isomorf is met zijn complementgraaf noemt men zelf-complementair.

De complementgraaf van een volledige graaf is een ledige graaf, die enkel bestaat uit knopen en die geen zijden heeft.