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 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

  • Das Komplement des Komplementes von G ist G selbst.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.