Schwach chordaler GraphIn der Graphentheorie heißt ein Graph schwach chordal (englisch weakly chordal), falls weder der Graph noch sein Komplementgraph induzierte Kreise mit mehr als 4 Knoten haben.[1] Alternative CharakterisierungEin 2-Paar von Knoten eines Graph sind Knoten x,y, sodass alle induzierten Pfade von zwischen x und y genau 2 Kanten haben. Ein Graph ist schwach chordal genau dann wenn jeder zusammenhängender induzierter Teilgraph entweder ein 2-Paar enthält oder ein vollständiger Graph ist.[2] EigenschaftenDie Menge der schwach chordalen Graphen ist unter Komplementbildung abgeschlossen. Das Komplement eines schwach chordalen Graphen ist selbst ein schwach chordaler Graph. Beziehungen zu anderen GraphklassenAlle schwach chordalen Graphen sind perfekte Graphen.[1] Unterklassen der schwach chordalen Graphen sind chordale Graphen und chordal bipartiten Graphen, wobei chordal bipartite Graphen keine Unterklasse der chordalen Graphen sind. Weblinks
Einzelnachweise
|
Portal di Ensiklopedia Dunia