Komplementgraph

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

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

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.

Definition

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

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

ergibt.

Der Komplementgraph eines gegebenen Graphen $G$ wird häufig auch mit ${\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.
Ist $|V|\geq 2$ , so gilt: Ist $G$ nicht zusammenhängend, dann ist ${\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.

Weblinks

Commons: Komplementgraph – Sammlung von Bildern, Videos und Audiodateien

Einzelnachweise

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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

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