Komplementgraph

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
Petersen-Graph (links) und dessen Komplementgraph (rechts).

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 Ursprungsgraph, unterscheidet sich aber in seinen Kanten: Der Komplementgraph besitzt genau die Kanten, die der Ursprungsgraph nicht hat.

Definition[Bearbeiten]

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

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[Bearbeiten]

  • Das Komplement des Komplementes von G ist G selbst.