Komplementgraph
Als Komplementgraph, komplementären Graph oder Komplement bezeichnet man in der Graphentheorie einen speziellen Graphen, den man aus einem gegebenen Graphen erhält.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/2/2f/Petersen_graph_complement.svg/220px-Petersen_graph_complement.svg.png)
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
BearbeitenSei 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.
Weblinks
BearbeitenEinzelnachweise
Bearbeiten- ↑ Reinhard Diestel: Graphentheorie. 3. Auflage. Springer, 2006, ISBN 978-3-662-53633-9, S. 138.