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 $\bar{G}$.

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

$V(\bar{G})=V(G)$

$E(\bar{G})$ = $\{\{v_1,v_2\}\mid v_1,v_2\in V(G)\wedge v_1=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 $\bar{G}$ ervan.