Komplementgraph

Als Komplementgraph, komplementären Graph oder Komplement bezeichnet man in der Graphentheorie einen speziellen Graphen, den man aus einem gegebenen Graphen erhält.

Dabei besitzt der komplementäre Graph die gleichen Knoten wie der Ursprungsgraph, unterscheidet sich aber in seinen Kanten: Der Komplementgraph besitzt genau die Kanten, die der Ursprungsgraph nicht hat.

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.

• Das Komplement des Komplementes von ${\displaystyle G}$ ist ${\displaystyle G}$ selbst.
• Ist ${\displaystyle |V|\geq 2}$, so gilt: Ist ${\displaystyle G}$ nicht zusammenhängend, dann ist ${\displaystyle {\overline {G}}}$ zusammenhängend.
• Das Komplement eines bipartiten Graphen ist stets perfekt. Diese Aussage ist äquivalent zum Satz von König.^[1]
• Nach dem Satz von Lovász ist ein Graph genau dann perfekt, wenn sein Komplementgraph perfekt ist.

Commons: Komplementgraph – Sammlung von Bildern, Videos und Audiodateien

1. ↑ Reinhard Diestel: Graphentheorie. 3. Auflage. Springer, 2006, ISBN 978-3-662-53633-9, S. 138.