Chordal bipartiter Graph

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

In der Graphentheorie heißt ein endlicher Graph G chordal bipartit (englisch chordal bipartite), falls jeder induzierte Kreis in G genau die Länge 4 hat. Auf dieser Graphenklasse lassen sich einige NP-schwere Probleme effizient lösen.

Ein bipartiter Graph mit bipartiter Zerlegung heißt chordal bipartit, wenn er eine (und damit alle) der folgenden äquivalenten Definitionen erfüllt:

  • jeder Kreis der Länge mindestens 6 hat eine Sehne (englisch: "chord"), d. h. es gibt im Graphen eine Kante zwischen zwei im Kreis nicht benachbarten Knoten.
  • der aus durch Hinzufügen aller Kanten zwischen Knoten in entstehende Graph ist stark chordal.
  • es existiert eine Anordnung der Kanten, so dass (für die durch definierte Folge) die Vereinigung der Nachbarschaften der beiden Knoten von ein vollständig bipartiter Teilgraph in ist, d. h. jeder Knoten in ist mit jedem Knoten in durch eine Kante in verbunden.

Man beachte, dass chordal bipartite Graphen nicht chordal sein müssen. Genauer wäre eigentlich die Bezeichnung schwach chordal bipartit, da diese Graphen schwach chordal und bipartit sind, andererseits sind Verwechslungen nicht zu befürchten, da Kreise in bipartiten Graphen stets eine gerade Länge haben müssen.

Ein Graph ist genau dann stark chordal, wenn sein assoziierter bipartiter Graph chordal bipartit ist.[1]

  • Mihály Bakonyi, Aaron Bono: Several Results on Chordal Bipartite Graphs. Czechoslovak Mathematical Journal, Volume 47 - Number 4 - Dezember 1997, ISSN 0011-4642, S. 577–583 PDF
  • Brandstädt, Andreas; Le, Van Bang; Spinrad, Jeremy (1999), Graph Classes: A Survey, SIAM Monographs on Discrete Mathematics and Applications, ISBN 0-89871-432-X.
  • Jorge L. Ramírez Alfonsín, Bruce A. Reed: Perfect Graphs. Wiley 2001, ISBN 978-0-471-48970-2, S. 141 (eingeschränkte Vorschau in der Google-Buchsuche)
  • Golumbic, Martin Charles; Goss, Clinton F.: Perfect elimination and chordal bipartite graphs. J. Graph Theory 2 (1978), no. 2, 155–163. PDF
  • chordal bipartite - Eintrag im Information System on Graph Classes and their Inclusions

Einzelnachweise

[Bearbeiten | Quelltext bearbeiten]
  1. Theorem 2.3 in: Brandstädt, Andreas: Classes of bipartite graphs related to chordal graphs. Discrete Applied Mathematics 32 (1991) 51–60