imported>LukeLR: /* Eigenschaften */ Tippfehler korrigiert

2023-12-08T19:12:56Z

Eigenschaften: Tippfehler korrigiert

Neue Seite

[[Datei:Petersen graph complement.svg|mini|[[Petersen-Graph]] (links) und dessen Komplementgraph (rechts).]]

Als '''Komplementgraph''', '''komplementären Graph''' oder '''Komplement''' bezeichnet man in der [[Graphentheorie]] einen speziellen [[Graph (Graphentheorie)|Graphen]], den man aus einem gegebenen Graphen erhält.

Dabei besitzt der komplementäre Graph die gleichen [[Knoten (Graphentheorie)|Knoten]] wie der Ursprungsgraph, unterscheidet sich aber in seinen [[Kante (Graphentheorie)|Kanten]]: Der Komplementgraph besitzt genau die Kanten, die der Ursprungsgraph ''nicht'' hat.

== Definition ==
Sei <math>G_1=(V,E_1)</math> ein [[Ungerichteter Graph|ungerichteter]] bzw. [[Gerichteter Graph|gerichteter]] [[Graph ohne Mehrfachkanten]]. Der ungerichtete bzw. gerichtete Graph ohne Mehrfachkanten <math>G_2=(V,E_2)</math> heißt ''Komplementgraph'' von <math>G_1</math>, wenn die [[Schnittmenge]] von <math>E_1</math> und <math>E_2</math> leer ist und die [[Vereinigungsmenge]] von <math>E_1</math> und <math>E_2</math>
* im ungerichteten Fall die Menge aller 2-elementigen [[Teilmenge]]n von ''V'' bzw.
* im gerichteten Fall das [[Kartesisches Produkt|kartesische Produkt]] <math>V\times V</math>
ergibt.

Der Komplementgraph eines gegebenen Graphen <math>G</math> wird häufig auch mit <math>\overline{G}</math> bezeichnet. Als ''selbstkomplementär'' bezeichnet man Graphen, die [[Isomorphie von Graphen|isomorph]] zu ihrem komplementären Graphen sind.

== Eigenschaften ==
* Das Komplement des Komplementes von ''<math>G</math>'' ist ''<math>G</math>'' selbst.
* Ist <math>|V|\geq 2</math>, so gilt: Ist <math>G</math> nicht zusammenhängend, dann ist <math>\overline{G}</math> zusammenhängend.
* Das Komplement eines [[Bipartiter Graph|bipartiten]] Graphen ist stets [[Perfekter Graph|perfekt]]. Diese Aussage ist äquivalent zum [[Satz von König (Graphentheorie)|Satz von König]].<ref>{{Literatur |Autor=Reinhard Diestel |Titel=Graphentheorie |Auflage=3 |Verlag=Springer |Datum=2006 |ISBN=978-3-662-53633-9 |Seiten=138}}</ref>
* Nach dem [[Schwacher Perfekte-Graphen-Satz|Satz von Lovász]] ist ein Graph genau dann perfekt, wenn sein Komplementgraph perfekt ist.

== Weblinks ==
{{Commonscat|Complement graph|Komplementgraph}}

== Einzelnachweise ==
<references />

[[Kategorie:Grundbegriff (Graphentheorie)]]

Komplementgraph - Versionsgeschichte

imported>LukeLR: /* Eigenschaften */ Tippfehler korrigiert