Complementgraaf

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

Graaf met complementgraaf

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}\}\mid v_{1},v_{2}\in V(G)\wedge v_{1}\not =v_{2}\}\setminus 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.