Complementgraaf

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken
De Petersen-graaf, links, met zijn complementgraaf

In de grafentheorie is de complementgraaf van een enkelvoudige graaf G, een enkelvoudige graaf H met dezelfde knopen als G, die met een zijde verbonden zijn als en slechts als ze in G niet met een zijde zijn verbonden.

De complementgraaf van een graaf G wordt vaak aangeduid met \overline{G}.

Formeler is de complementgraaf \overline{G} van G = (V(G), E(G)) met knopen V(G) en zijden E(G), 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) \wedge v_1 \not = v_2\} \backslash 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 ledige graaf, die enkel bestaat uit knopen en die geen zijden heeft.