Komplementgraph

Graphentheorie, Teilgebiet der Mathematik

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

Bearbeiten

Sei   ein ungerichteter bzw. gerichteter Graph ohne Mehrfachkanten. Der ungerichtete bzw. gerichtete Graph ohne Mehrfachkanten   heißt Komplementgraph von  , wenn die Schnittmenge von   und   leer ist und die Vereinigungsmenge von   und  

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

ergibt.

Der Komplementgraph eines gegebenen Graphen   wird häufig auch mit   bezeichnet. Als selbstkomplementär bezeichnet man Graphen, die isomorph zu ihrem komplementären Graphen sind.

Eigenschaften

Bearbeiten
  • Das Komplement des Komplementes von   ist   selbst.
  • Ist  , so gilt: Ist   nicht zusammenhängend, dann ist   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.
Bearbeiten
Commons: Komplementgraph – Sammlung von Bildern, Videos und Audiodateien

Einzelnachweise

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