Complementgraaf

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

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

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

${\displaystyle E({\overline {G}})}$ = ${\displaystyle \{\{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 ${\displaystyle G}$ induceert een onafhankelijke verzameling in de complementaire graaf ${\displaystyle {\overline {G}}}$ ervan.