Chordal bipartiter Graph

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.

Definitionen

Ein bipartiter Graph $G=(V,E)$ mit bipartiter Zerlegung $V=A\cup B$ 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 $G$ durch Hinzufügen aller Kanten zwischen Knoten in $A$ entstehende Graph ist stark chordal.
es existiert eine Anordnung der Kanten, so dass (für die durch $G_{0}=G,G_{i}=G_{i-1}-e_{i}$ definierte Folge) die Vereinigung der Nachbarschaften der beiden Knoten von $e_{i}=\left\{x_{i},y_{i}\right\}$ ein vollständig bipartiter Teilgraph in $G_{i-1}$ ist, d. h. jeder Knoten in $N(x_{i})$ ist mit jedem Knoten in $N(y_{i})$ durch eine Kante in $G_{i-1}$ 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]

Literatur

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 9780471489702, S. 141 (eingeschränkte Online-Version in der Google-Buchsuche-USA)
Golumbic, Martin Charles; Goss, Clinton F.: Perfect elimination and chordal bipartite graphs. J. Graph Theory 2 (1978), no. 2, 155–163. PDF

Weblinks

chordal bipartite - Eintrag im Information System on Graph Classes and their Inclusions

Einzelnachweise

Theorem 2.3 in: Brandstädt, Andreas: Classes of bipartite graphs related to chordal graphs. Discrete Applied Mathematics 32 (1991) 51–60

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.

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