Co-Graph

In der Informatik ist ein Co-Graph ein ungerichteter Graph ${\displaystyle 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

Abbildung eines Co-Graphen. Wie man sieht, ist kein induzierter${\displaystyle P_{4}}$ enthalten.

Dieser Graph ist kein Co-Graph, da ein induzierter${\displaystyle P_{4}}$ enthalten ist.

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

1. Der Graph ${\displaystyle K_{1}}$ mit genau einem Knoten ist ein Co-Graph (in Zeichen ${\displaystyle K_{1}=\bullet }$).
2. Für zwei Co-Graphen ${\displaystyle G_{1}=(V_{1},E_{1})}$ und ${\displaystyle G_{2}=(V_{2},E_{2})}$ ist die disjunkte Vereinigung ${\displaystyle G_{1}\cup G_{2}:=(V_{1}\cup V_{2},E_{1}\cup E_{2})}$ ein Co-Graph.
3. Für zwei Co-Graphen ${\displaystyle G_{1}=(V_{1},E_{1})}$ und ${\displaystyle G_{2}=(V_{2},E_{2})}$ ist die disjunkte Summe ${\displaystyle 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 ${\displaystyle G}$ sind folgende Aussagen äquivalent:

• ${\displaystyle G}$ ist ein Co-Graph.
• ${\displaystyle G}$ enthält keinen induzierten ${\displaystyle P_{4}}$, wobei ${\displaystyle P_{4}}$ den ungerichteten Weg mit vier Knoten bezeichnet.
• Der Komplementgraph jedes zusammenhängenden induzierten Teilgraphen von ${\displaystyle G}$ mit mindestens zwei Knoten ist unzusammenhängend.
• ${\displaystyle G}$ lässt sich mit den folgenden drei Regeln konstruieren:

1. Jeder Graph ${\displaystyle K_{1}}$ mit genau einem Knoten ist ein Co-Graph.
2. Für zwei Co-Graphen ${\displaystyle G_{1}}$ und ${\displaystyle G_{2}}$ ist die disjunkte Vereinigung ${\displaystyle G_{1}\cup G_{2}}$ ein Co-Graph.
3. Für einen Co-Graphen ${\displaystyle G}$ ist auch der Komplementgraph ${\displaystyle {\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 ${\displaystyle \bullet }$ und dessen innere Knoten mit ${\displaystyle \cup }$ bzw. ${\displaystyle \times }$ markiert sind.

Ein Co-Baum ${\displaystyle T}$ ist wie folgt definiert:

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

Beispiel

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

Co-Graph	Darstellung des Co-Graphen	Darstellung des Co-Baumes	Co-Baum
${\displaystyle G_{1}=\bullet }$			${\displaystyle T_{1}}$
${\displaystyle G_{2}=G_{1}\cup G_{1}}$			${\displaystyle T_{2}}$
${\displaystyle G_{3}=G_{1}\times G_{2}}$			${\displaystyle T_{3}}$
${\displaystyle G_{4}=G_{3}\cup G_{3}}$			${\displaystyle T_{4}}$
${\displaystyle G_{5}=G_{1}\times G_{4}}$			${\displaystyle T_{5}}$

Weitere Beispiele für Co-Graphen s​ind vollständige Graphen u​nd 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 ${\displaystyle \cup }$ und ${\displaystyle \times }$ vertauscht werden.

Weiterhin i​st die Menge d​er Co-Graphen u​nter Bildung induzierter Teilgraphen abgeschlossen.

Ebenfalls i​st bekannt, d​ass jeder Co-Graph e​in perfekter Graph ist.

Anwendung in der Algorithmik

Einige schwere Graphenprobleme lassen s​ich auf Co-Graphen i​n Linearzeit lösen. Dazu zählen u. A. d​ie Probleme UNABHÄNGIGE MENGE, CLIQUE u​nd KNOTENÜBERDECKUNG.

Mithilfe v​on dynamischer Programmierung a​uf den zugehörigen Co-Bäumen lassen s​ich einfach u​nd elegant Lösungen für d​ie genannten Probleme finden.

Literatur

• 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