Co-Graph

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

In der Informatik ist ein Co-Graph ein ungerichteter Graph , welcher sich mit bestimmten elementaren Operationen konstruieren lässt. Auf Co-Graphen lassen sich viele schwere Probleme wie z. B. CLIQUE und das damit eng verwandte UNABHÄNGIGE MENGE sowie KNOTENÜBERDECKUNG in Linearzeit lösen.

Abbildung eines Co-Graphen. Wie man sieht, ist kein induzierter enthalten.
Dieser Graph ist kein Co-Graph, da ein induzierter enthalten ist.

Ein Graph ist ein Co-Graph, falls er sich mit den folgenden drei Operationen konstruieren lässt:

  1. Der Graph mit genau einem Knoten ist ein Co-Graph (in Zeichen ).
  2. Für zwei Co-Graphen und ist die disjunkte Vereinigung ein Co-Graph.
  3. Für zwei Co-Graphen und ist die disjunkte Summe ein Co-Graph.

Äquivalente Charakterisierungen

[Bearbeiten | Quelltext bearbeiten]

Für einen Graphen sind folgende Aussagen äquivalent:

  1. Jeder Graph mit genau einem Knoten ist ein Co-Graph.
  2. Für zwei Co-Graphen und ist die disjunkte Vereinigung ein Co-Graph.
  3. Für einen Co-Graphen ist auch der Komplementgraph ein Co-Graph.

Um auf Co-Graphen effizient schwere Probleme lösen zu können, kann man sie mithilfe von Co-Bäumen darstellen. Ein Co-Baum ist ein binärer Baum, dessen Blätter mit und dessen innere Knoten mit bzw. markiert sind.

Ein Co-Baum ist wie folgt definiert:

  1. Der Co-Baum zu dem Co-Graphen ist der Baum mit einem Knoten, der mit markiert ist.
  2. Seien und Co-Graphen mit den Co-Bäumen und . Der Co-Baum zu der disjunkten Vereinigung von und besteht aus einem mit markierten Wurzelknoten mit den Kindern und .
  3. Seien und Co-Graphen mit den Co-Bäumen und . Der Co-Baum zu der disjunkten Summe von und besteht aus einem mit markierten Wurzelknoten mit den Kindern und .

Das nachfolgende Beispiel skizziert die Konstruktion eines Co-Graphen mit zugehörigem Co-Baum :

Co-Graph Darstellung des Co-Graphen Darstellung des Co-Baumes Co-Baum

Weitere Beispiele für Co-Graphen sind vollständige Graphen und vollständig unzusammenhängende Graphen.

Eigenschaften von Co-Graphen

[Bearbeiten | Quelltext bearbeiten]

Es ist leicht einzusehen, dass Co-Graphen unter Komplementbildung abgeschlossen sind. Um den Komplementgraphen zu erzeugen, müssen im zugehörigen Co-Baum lediglich die Operationen und vertauscht werden.

Weiterhin ist die Menge der Co-Graphen unter Bildung induzierter Teilgraphen abgeschlossen.

Ebenfalls ist bekannt, dass jeder Co-Graph ein perfekter Graph ist.

Anwendung in der Algorithmik

[Bearbeiten | Quelltext bearbeiten]

Einige schwere Graphenprobleme lassen sich auf Co-Graphen in Linearzeit lösen. Dazu zählen u. a. die Probleme UNABHÄNGIGE MENGE, CLIQUE und KNOTENÜBERDECKUNG.

Mithilfe von dynamischer Programmierung auf den zugehörigen Co-Bäumen lassen sich einfach und elegant Lösungen für die genannten Probleme finden.

  • Frank Gurski, Irene Rothe, Jörg Rothe, Egon Wanke: Exakte Algorithmen für schwere Graphenprobleme, Springer-Verlag, Berlin Heidelberg, 2010, ISBN 978-3-642-04499-1