Complementgraaf

In de grafentheorie is de complementgraaf van een enkelvoudige graaf $G$ een enkelvoudige graaf $H$ met dezelfde knopen als $G$ , waarin twee knopen door een zijde verbonden worden dan en slechts dan als die twee knopen in de oorspronkelijke graaf $G$ niet door een zijde verbonden worden. De complementgraaf van een graaf $G$ wordt vaak aangeduid met $\overline{G}$ .

De complementgraaf $\overline{G}$ van $G = (V (G), E (G))$ met knopen $V (G)$ en zijden $E (G)$ is de graaf gegeven door het paar $(V (\overline{G})$ , $E (\overline{G}))$ waarvoor geldt:

V (\overline{G}) = V (G)

E (\overline{G})

=

{{v_{1}, v_{2}} ∣ v_{1}, v_{2} \in V (G) \land v_{1} = v_{2}} ∖ E (G)

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 lege graaf, die alleen uit knopen bestaat en geen zijden heeft. Een clique in een graaf $G$ induceert een onafhankelijke verzameling in de complementaire graaf $\overline{G}$ ervan.

Complementgraaf

Navigatiemenu

Zoeken