Complementgraaf

Graaf met 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}\}\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.