Das Kefk Network Wiki befindet sich im Testbetrieb.
Chordal bipartiter Graph
Aus Kefk.
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. Hierbei handelt es sich um eine in letzter Zeit viel beachtete Graphenklasse, auf der einige NP-schwere Probleme effizient lösbar sind.
Vorsicht: Chordal bipartite Graphen sind nicht chordal! Genauer wäre die Bezeichnung schwach chordal bipartit, da diese Graphen schwach chordal und bipartit sind.
