Komplementgraph

Als Komplementgraph, komplementären Graph o​der Komplement bezeichnet m​an in d​er Graphentheorie e​inen speziellen Graphen, d​en man a​us einem gegebenen Graphen erhält.

Petersen-Graph (links) und dessen Komplementgraph (rechts).

Dabei besitzt d​er komplementäre Graph d​ie gleichen Knoten w​ie der Ursprungsgraph, unterscheidet s​ich aber i​n seinen Kanten: Der Komplementgraph besitzt g​enau die Kanten, d​ie der Ursprungsgraph nicht hat.

Definition

Sei ${\displaystyle G_{1}=(V,E_{1})}$ ein ungerichteter bzw. gerichteter Graph ohne Mehrfachkanten. Der ungerichtete bzw. gerichtete Graph ohne Mehrfachkanten ${\displaystyle G_{2}=(V,E_{2})}$ heißt Komplementgraph von ${\displaystyle G_{1}}$, wenn die Schnittmenge von ${\displaystyle E_{1}}$ und ${\displaystyle E_{2}}$ leer ist und die Vereinigungsmenge von ${\displaystyle E_{1}}$ und ${\displaystyle E_{2}}$

• im ungerichteten Fall die Menge aller 2-elementigen Teilmengen von V bzw.
• im gerichteten Fall das kartesische Produkt ${\displaystyle V\times V}$

ergibt.

Der Komplementgraph eines gegebenen Graphen ${\displaystyle G}$ wird häufig auch mit ${\displaystyle {\overline {G}}}$ bezeichnet. Als selbstkomplementär bezeichnet man Graphen, die isomorph zu ihrem komplementären Graphen sind.

Eigenschaften

• Das Komplement des Komplementes von G ist G selbst.