Co-Graph

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

In der Informatik ist ein Co-Graph ein ungerichteter Graph G = (V, E), 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.

Definition[Bearbeiten]

Abbildung eines Co-Graphen. Wie man sieht, ist kein induzierterP_{4} enthalten.
Dieser Graph ist kein Co-Graph, da ein induzierterP_{4} enthalten ist.

Ein Graph G = (V, E) ist ein Co-Graph, falls er sich mit den folgenden drei Operationen konstruieren lässt:

  1. Der Graph K_{1} mit genau einem Knoten ist ein Co-Graph (in Zeichen K_{1} = \bullet).
  2. Für zwei Co-Graphen G_{1} = (V_{1}, E_{1}) und G_{2} = (V_{2}, E_{2}) ist die disjunkte Vereinigung G_{1} \cup G_{2} := (V_{1} \cup V_{2}, E_{1} \cup E_{2}) ein Co-Graph.
  3. Für zwei Co-Graphen G_{1} = (V_{1}, E_{1}) und G_{2} = (V_{2}, E_{2}) ist die disjunkte Summe G_{1} \times G_{2} := (V_{1} \cup V_{2}, E_{1} \cup E_{2} \cup \lbrace \lbrace u, v \rbrace | u \in V_{1}, v \in V_{2} \rbrace) ein Co-Graph.

Äquivalente Charakterisierungen[Bearbeiten]

Für einen Graphen G sind folgende Aussagen äquivalent:

  1. Jeder Graph K_{1} mit genau einem Knoten ist ein Co-Graph.
  2. Für zwei Co-Graphen G_{1} und G_{2} ist die disjunkte Vereinigung G_{1} \cup G_{2} ein Co-Graph.
  3. Für einen Co-Graphen G ist auch der Komplementgraph \bar G ein Co-Graph.

Co-Baum[Bearbeiten]

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 \bullet und dessen innere Knoten mit \cup bzw. \times markiert sind.

Ein Co-Baum T ist wie folgt definiert:

  1. Der Co-Baum T zu dem Co-Graphen G = \bullet ist der Baum mit einem Knoten, der mit \bullet markiert ist.
  2. Seien G_{1} und G_{2} Co-Graphen mit den Co-Bäumen T_{1} und T_{2}. Der Co-Baum T zu der disjunkten Vereinigung von G_{1} und G_{2} besteht aus einem mit \cup markierten Wurzelknoten mit den Kindern T_{1} und T_{2}.
  3. Seien G_{1} und G_{2} Co-Graphen mit den Co-Bäumen T_{1} und T_{2}. Der Co-Baum T zu der disjunkten Summe von G_{1} und G_{2} besteht aus einem mit \times markierten Wurzelknoten mit den Kindern T_{1} und T_{2}.

Beispiel[Bearbeiten]

Das nachfolgende Beispiel skizziert die Konstruktion eines Co-Graphen G_{5} mit zugehörigem Co-Baum T_{5}:

Co-Graph Darstellung des Co-Graphen Darstellung des Co-Baumes Co-Baum
G_{1} = \bullet Cograph g1.png Cotree t1.png T_{1}
G_{2} = G_{1} \cup G_{1} Cograph g2.png Cotree t2.png T_{2}
G_{3} = G_{1} \times G_{2} Cograph g3.png Cotree t3.png T_{3}
G_{4} = G_{3} \cup G_{3} Cograph g4.png Cotree t4.png T_{4}
G_{5} = G_{1} \times G_{4} Cograph g5.png Cotree t5.png T_{5}

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

Eigenschaften von Co-Graphen[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 \cup und \times 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]

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.

Literatur[Bearbeiten]

  • 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