Co-Graph
In der Informatik ist ein Co-Graph ein ungerichteter Graph <math>G = (V, E)</math>, 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 <math>G = (V, E)</math> ist ein Co-Graph, falls er sich mit den folgenden drei Operationen konstruieren lässt:
- Der Graph <math>K_{1}</math> mit genau einem Knoten ist ein Co-Graph (in Zeichen <math>K_{1} = \bullet</math>).
- Für zwei Co-Graphen <math>G_{1} = (V_{1}, E_{1})</math> und <math>G_{2} = (V_{2}, E_{2})</math> ist die disjunkte Vereinigung <math>G_{1} \cup G_{2} := (V_{1} \cup V_{2}, E_{1} \cup E_{2})</math> ein Co-Graph.
- Für zwei Co-Graphen <math>G_{1} = (V_{1}, E_{1})</math> und <math>G_{2} = (V_{2}, E_{2})</math> ist die disjunkte Summe <math>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)</math> ein Co-Graph.
Äquivalente Charakterisierungen
Für einen Graphen <math>G</math> sind folgende Aussagen äquivalent:
- <math>G</math> ist ein Co-Graph.
- <math>G</math> enthält keinen induzierten <math>P_{4}</math>, wobei <math>P_{4}</math> den ungerichteten Weg mit vier Knoten bezeichnet.
- Der Komplementgraph jedes zusammenhängenden induzierten Teilgraphen von <math>G</math> mit mindestens zwei Knoten ist unzusammenhängend.
- <math>G</math> lässt sich mit den folgenden drei Regeln konstruieren:
- Jeder Graph <math>K_{1}</math> mit genau einem Knoten ist ein Co-Graph.
- Für zwei Co-Graphen <math>G_{1}</math> und <math>G_{2}</math> ist die disjunkte Vereinigung <math>G_{1} \cup G_{2}</math> ein Co-Graph.
- Für einen Co-Graphen <math>G</math> ist auch der Komplementgraph <math>\bar G</math> 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 <math>\bullet</math> und dessen innere Knoten mit <math>\cup</math> bzw. <math>\times</math> markiert sind.
Ein Co-Baum <math>T</math> ist wie folgt definiert:
- Der Co-Baum <math>T</math> zu dem Co-Graphen <math>G = \bullet</math> ist der Baum mit einem Knoten, der mit <math>\bullet</math> markiert ist.
- Seien <math>G_{1}</math> und <math>G_{2}</math> Co-Graphen mit den Co-Bäumen <math>T_{1}</math> und <math>T_{2}</math>. Der Co-Baum <math>T</math> zu der disjunkten Vereinigung von <math>G_{1}</math> und <math>G_{2}</math> besteht aus einem mit <math>\cup</math> markierten Wurzelknoten mit den Kindern <math>T_{1}</math> und <math>T_{2}</math>.
- Seien <math>G_{1}</math> und <math>G_{2}</math> Co-Graphen mit den Co-Bäumen <math>T_{1}</math> und <math>T_{2}</math>. Der Co-Baum <math>T</math> zu der disjunkten Summe von <math>G_{1}</math> und <math>G_{2}</math> besteht aus einem mit <math>\times</math> markierten Wurzelknoten mit den Kindern <math>T_{1}</math> und <math>T_{2}</math>.
Beispiel
Das nachfolgende Beispiel skizziert die Konstruktion eines Co-Graphen <math>G_{5}</math> mit zugehörigem Co-Baum <math>T_{5}</math>:
| Co-Graph | Darstellung des Co-Graphen | Darstellung des Co-Baumes | Co-Baum |
|---|---|---|---|
| <math>G_{1} = \bullet</math> | Datei:Cograph g1.png | Datei:Cotree t1.png | <math>T_{1}</math> |
| <math>G_{2} = G_{1} \cup G_{1}</math> | Datei:Cograph g2.png | Datei:Cotree t2.png | <math>T_{2}</math> |
| <math>G_{3} = G_{1} \times G_{2}</math> | Datei:Cograph g3.png | Datei:Cotree t3.png | <math>T_{3}</math> |
| <math>G_{4} = G_{3} \cup G_{3}</math> | Datei:Cograph g4.png | Datei:Cotree t4.png | <math>T_{4}</math> |
| <math>G_{5} = G_{1} \times G_{4}</math> | Datei:Cograph g5.png | Datei:Cotree t5.png | <math>T_{5}</math> |
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 <math>\cup</math> und <math>\times</math> 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.
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