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. UNABHÄNGIGE MENGE, CLIQUE und KNOTENÜBERDECKUNG in Linearzeit lösen.

Inhaltsverzeichnis

Definition

Abbildung eines Co-Graphen. Wie man sieht, ist kein induzierter  P_{4}\,  enthalten.
Dieser Graph ist kein Co-Graph, da ein induzierter  P_{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

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

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

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

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 sind 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

Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Graph pebbling — is a mathematical game and area of interest played on a graph with pebbles on the vertices. Game play is composed of a series of pebbling moves. A pebbling move on a graph consists of taking two pebbles off one vertex and placing one on an… …   Wikipedia

  • Graph paper — Regular graphing paper (upper); Logarithmic graphing paper (lower). Graph paper, graphing paper, grid paper or millimeter paper is writing paper that is printed with fine lines making up a …   Wikipedia

  • Graph transformation — Graph transformation, or Graph rewriting, concerns the technique to create a new graph out of an original graph using some automatic machine. It has numerous applications, ranging from software verification to layout algorithms.Graph… …   Wikipedia

  • Graph — (gr[.a]f), n. [See { graph}.] (Math.) 1. A curve or surface, the locus of a point whose co[ o]rdinates are the variables in the equation of the locus; as, a graph of the exponential function. [Webster 1913 Suppl.] 2. A diagram symbolizing a… …   The Collaborative International Dictionary of English

  • Graph — may refer to:* A graphic (such as a chart or diagram) depicting the relationship between two or more variables used, for instance, in visualising scientific data.In mathematics:* Graph (mathematics), a set of vertices connected with edges * Graph …   Wikipedia

  • Graph Modelling Language — (GML) is a hierarchical ASCII based file format for describing graphs. Applications supporting GML * Cytoscape, an open source bioinformatics software platform for visualizing molecular interaction networks, loads and save previously constructed… …   Wikipedia

  • graph´ic|ness — graph|ic «GRAF ihk», adjective, noun. –adj. 1. producing by words the effect of a picture; lifelike; vivid: »The returned soldier gave a graphic account of a battle. 2. of or about diagrams and their use; working by means of graphs rather than… …   Useful english dictionary

  • graph´ic|ly — graph|ic «GRAF ihk», adjective, noun. –adj. 1. producing by words the effect of a picture; lifelike; vivid: »The returned soldier gave a graphic account of a battle. 2. of or about diagrams and their use; working by means of graphs rather than… …   Useful english dictionary

  • graph´i|cal|ly — graph|ic «GRAF ihk», adjective, noun. –adj. 1. producing by words the effect of a picture; lifelike; vivid: »The returned soldier gave a graphic account of a battle. 2. of or about diagrams and their use; working by means of graphs rather than… …   Useful english dictionary

  • graph|ic — «GRAF ihk», adjective, noun. –adj. 1. producing by words the effect of a picture; lifelike; vivid: »The returned soldier gave a graphic account of a battle. 2. of or about diagrams and their use; working by means of graphs rather than… …   Useful english dictionary

  • Graph — 〈m. 16; Math.〉 = Graf2 * * * 1Graph , Graf , der; en, en [zu griech. gráphein = schreiben] (bes. Math., Naturwiss.): grafische Darstellung (z. B. von Relationen) in Form von [markierten] Knoten[punkten] u. verbindenden Linien (Kanten). 2Graph,… …   Universal-Lexikon

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”