Diagramm ergänzen - Complement graph
In der Graphentheorie , das Komplement oder inverse ein Graphen G ist ein Graph H auf den gleichen Scheitelpunkte, so dass zwei verschiedene Ecken aus H benachbart sind , wenn und nur dann , wenn sie in nicht benachbart sind G . Das heißt, um das Komplement eines Graphen zu erzeugen, füllt man alle fehlenden Kanten aus, die erforderlich sind, um einen vollständigen Graphen zu bilden , und entfernt alle zuvor vorhandenen Kanten.
Das Komplement ist nicht das Mengenkomplement des Graphen; nur die Kanten werden ergänzt.
Definition
Sei G = ( V , E ) ein einfacher Graph und K bestehe aus allen 2-elementigen Teilmengen von V . Dann ist H = ( V , K \ E ) das Komplement von G , wobei K \ E das relative Komplement von E in K ist . Für gerichtete Graphen kann das Komplement auf dieselbe Weise wie ein gerichteter Graph auf derselben Knotenmenge definiert werden, indem die Menge aller 2-elementigen geordneten Paare von V anstelle der Menge K in der obigen Formel verwendet wird. In Bezug auf die Adjazenzmatrix A des Graphen, wenn Q die Adjazenzmatrix des vollständigen Graphen der gleichen Anzahl von Knoten ist (dh alle Einträge sind Eins außer den diagonalen Einträgen, die Null sind), dann ist die Adjazenzmatrix des Komplements von A ist QA .
Für Multigraphen ist das Komplement nicht definiert . In Graphen, die Selbstschleifen (aber nicht mehrfache Nachbarschaften) zulassen, kann das Komplement von G definiert werden, indem eine Selbstschleife zu jedem Scheitelpunkt hinzugefügt wird, der keine in G hat , und ansonsten die gleiche Formel wie oben verwendet. Diese Operation unterscheidet sich jedoch von der für einfache Graphen, da ihre Anwendung auf einen Graphen ohne Selbstschleifen zu einem Graphen mit Selbstschleifen an allen Knoten führen würde.
Anwendungen und Beispiele
Mehrere graphentheoretische Konzepte sind durch Komplementation miteinander verbunden:
- Das Komplement eines kantenlosen Graphen ist ein vollständiger Graph und umgekehrt.
- Jeder induzierte Teilgraph des Komplementgraphen eines Graphen G ist das Komplement des entsprechenden induzierten Teilgraphen in G .
- Eine unabhängige Menge in einem Graphen ist eine Clique im Komplementgraphen und umgekehrt. Dies ist ein Spezialfall der vorherigen beiden Eigenschaften, da eine unabhängige Menge ein kantenlos induzierter Teilgraph und eine Clique ein vollständiger induzierter Teilgraph ist.
- Die Automorphismusgruppe eines Graphen ist die Automorphismusgruppe seines Komplements.
- Das Komplement jedes dreiecksfreien Graphen ist ein klauenfreier Graph , obwohl das Gegenteil nicht der Fall ist.
Selbstkomplementäre Graphen und Graphenklassen
Ein selbstkomplementärer Graph ist ein Graph, der zu seinem eigenen Komplement isomorph ist . Beispiele hierfür sind die vier Vertex Weg Graph und fünf Vertex Zyklus Graph . Es gibt keine bekannte Charakterisierung von selbstkomplementären Graphen.
Mehrere Klassen von Graphen sind in dem Sinne selbstkomplementär, dass das Komplement eines Graphen in einer dieser Klassen ein anderer Graph derselben Klasse ist.
- Perfekte Graphen sind Graphen, in denen für jeden induzierten Teilgraphen die chromatische Zahl gleich der Größe der maximalen Clique ist. Die Tatsache, dass das Komplement eines perfekten Graphen auch perfekt ist, ist der Satz für perfekte Graphen von László Lovász .
- Cographen sind definiert als die Graphen, die aus einzelnen Knoten durch disjunkte Vereinigungs- und Komplementationsoperationen aufgebaut werden können. Sie bilden eine sich selbst ergänzende Familie von Graphen: Das Komplement eines jeden Kographen ist ein weiterer anderer Kograph. Für Kographen mit mehr als einem Knoten ist genau ein Graph in jedem komplementären Paar zusammenhängend, und eine äquivalente Definition von Kographen ist, dass jeder ihrer zusammenhängenden induzierten Untergraphen ein unzusammenhängendes Komplement hat. Eine andere, sich selbst ergänzende Definition ist, dass es sich um die Graphen ohne induzierten Untergraphen in Form eines Pfads mit vier Knoten handelt.
- Eine weitere selbstkomplementäre Graphenklasse ist die Klasse der Splitgraphen , die Graphen, bei denen die Knoten in eine Clique und eine unabhängige Menge unterteilt werden können. Dieselbe Partition ergibt eine unabhängige Menge und eine Clique im Komplementgraphen.
- Die Schwellenwertgraphen sind die Graphen, die durch wiederholtes Hinzufügen entweder eines unabhängigen Scheitels (einer ohne Nachbarn) oder eines universellen Scheitels (angrenzend an alle zuvor hinzugefügten Scheitel) gebildet werden. Diese beiden Operationen sind komplementär und erzeugen eine selbstkomplementäre Klasse von Graphen.
Algorithmische Aspekte
Bei der Analyse von Algorithmen für Graphen ist die Unterscheidung zwischen einem Graphen und seinem Komplement wichtig, da ein dünn besetzter Graph (einer mit einer kleinen Anzahl von Kanten im Vergleich zur Anzahl von Knotenpaaren) im Allgemeinen kein dünn besetztes Komplement hat , und so kann ein Algorithmus, der proportional zur Anzahl der Kanten auf einem gegebenen Graphen Zeit benötigt, viel länger dauern, wenn derselbe Algorithmus auf einer expliziten Darstellung des Komplement-Graphen ausgeführt wird. Daher haben Forscher Algorithmen untersucht, die Standardgraphenberechnungen am Komplement eines Eingabegraphen durchführen, wobei eine implizite Graphendarstellung verwendet wird , die nicht die explizite Konstruktion des Komplementgraphen erfordert. Insbesondere ist es möglich, entweder die Tiefensuche oder die Breitensuche auf dem Komplementgraphen in einer Zeitdauer zu simulieren , die in der Größe des gegebenen Graphen linear ist, selbst wenn der Komplementgraph eine viel größere Größe haben kann . Es ist auch möglich, diese Simulationen zu verwenden, um andere Eigenschaften bezüglich der Konnektivität des Komplementgraphen zu berechnen.
