Co-Graph
# Co-Graph

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

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

* Der Graph $K_{1}$ mit genau einem Knoten ist ein Co-Graph (in Zeichen $K_{1}=\bullet$).
* 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.
* 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

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

* $G$ ist ein Co-Graph.
* $G$ enthält keinen induzierten $P_{4}$, wobei $P_{4}$ den ungerichteten Weg mit vier Knoten bezeichnet.
* Der Komplementgraph jedes zusammenhängenden induzierten Teilgraphen von $G$ mit mindestens zwei Knoten ist unzusammenhängend.
* $G$ lässt sich mit den folgenden drei Regeln konstruieren:
* Jeder Graph $K_{1}$ mit genau einem Knoten ist ein Co-Graph.
* Für zwei Co-Graphen $G_{1}$ und $G_{2}$ ist die disjunkte Vereinigung $G_{1}\cup G_{2}$ ein Co-Graph.
* Für einen Co-Graphen $G$ ist auch der Komplementgraph ${\bar {G}}$ ein Co-Graph.

## Co-Baum

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:

* Der Co-Baum $T$ zu dem Co-Graphen $G=\bullet$ ist der Baum mit einem Knoten, der mit $\bullet$ markiert ist.
* 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}$.
* 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

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

| Co-Graph | Co-Baum |
| - | - |
| $G_{1}=\bullet$ | $T_{1}$ |
| $G_{2}=G_{1}\cup G_{1}$ | $T_{2}$ |
| $G_{3}=G_{1}\times G_{2}$ | $T_{3}$ |
| $G_{4}=G_{3}\cup G_{3}$ | $T_{4}$ |
| $G_{5}=G_{1}\times G_{4}$ | $T_{5}$ |

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

## Eigenschaften von Co-Graphen

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

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.

