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.

DefinitionBearbeiten

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.

EigenschaftenBearbeiten

  • 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 Loász ist ein Graph genau dann perfekt, wenn sein Komplementgraph perfekt ist.

WeblinksBearbeiten

Commons: Komplementgraph – Sammlung von Bildern, Videos und Audiodateien

EinzelnachweiseBearbeiten

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