- Chordal bipartiter Graph
-
Dieser Artikel wurde auf der Qualitätssicherungsseite des Portals Mathematik eingetragen. Dies geschieht, um die Qualität der Artikel aus dem Themengebiet Mathematik auf ein akzeptables Niveau zu bringen. Bitte hilf mit, die Mängel dieses Artikels zu beseitigen, und beteilige dich bitte an der Diskussion!
In der Graphentheorie heißt ein Graph G chordal bipartit (engl. 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.
Chordal bipartite Graphen sind nicht chordal! Genauer wäre 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.
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
- 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)
Weblinks
- chordal bipartite - Eintrag im Information System on Graph Classes and their Inclusions der Uni Rostock
Wikimedia Foundation.