Chordal bipartiter Graph
# 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.

