imported>Invisigoth67: form

2023-07-14T17:01:05Z

form

Neue Seite

In der [[Informatik]] ist ein '''Co-Graph''' ein [[Graph (Graphentheorie)|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. [[Cliquenproblem|CLIQUE]] und das damit eng verwandte UNABHÄNGIGE MENGE sowie [[Knotenüberdeckungsproblem|KNOTENÜBERDECKUNG]] in [[Linearzeit]] lösen.

== Definition ==
[[Datei:Cograph example 1.png|miniatur|Abbildung eines Co-Graphen. Wie man sieht, ist kein induzierter<math>P_{4}</math> enthalten.]]
[[Datei:Cograph example 2.png|190px|miniatur|Dieser Graph ist kein Co-Graph, da ein induzierter<math>P_{4}</math> enthalten ist.]]
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 [[Induzierter Teilgraph|induzierten <math>P_{4}</math>]], wobei <math>P_{4}</math> den [[ungerichteter Weg|ungerichteten Weg]] mit vier Knoten bezeichnet.
* Der [[Komplementgraph]] jedes [[Zusammenhang von Graphen|zusammenhängenden]] [[Induzierter Teilgraph|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ärbaum|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>:

{| class="wikitable centered" style="text-align:center"
|-
! 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|60px]] || <math>T_{1}</math>
|-
| <math>G_{2} = G_{1} \cup G_{1}</math> || [[Datei:Cograph g2.png]] || [[Datei:Cotree t2.png|100px]] || <math>T_{2}</math>
|-
| <math>G_{3} = G_{1} \times G_{2}</math> || [[Datei:Cograph g3.png]] || [[Datei:Cotree t3.png|140px]] || <math>T_{3}</math>
|-
| <math>G_{4} = G_{3} \cup G_{3}</math> || [[Datei:Cograph g4.png]] || [[Datei:Cotree t4.png|180px]] || <math>T_{4}</math>
|-
| <math>G_{5} = G_{1} \times G_{4}</math> || [[Datei:Cograph g5.png]] || [[Datei:Cotree t5.png|220px]] || <math>T_{5}</math>
|}

Weitere Beispiele für Co-Graphen sind [[Vollständiger Graph|vollständige Graphen]] und [[Vollständig unzusammenhängender Graph|vollständig unzusammenhängende Graphen]].

== Eigenschaften von Co-Graphen ==
Es ist leicht einzusehen, dass Co-Graphen unter [[Komplementgraph|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 Teilgraph]]en 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, [[Cliquenproblem|CLIQUE]] und [[Knotenüberdeckungsproblem|KNOTENÜBERDECKUNG]].

Mithilfe von [[Dynamische Programmierung|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
[[Kategorie:Graph]]
[[Kategorie:Graphentheorie]]

Co-Graph - Versionsgeschichte

imported>Invisigoth67: form