imported>Redrobsche: Link und Grammatik

2021-11-18T19:52:09Z

Link und Grammatik

Neue Seite

In der [[Graphentheorie]] heißt ein Graph '''<math>G</math> ''schwach chordal''''' (englisch ''weakly chordal''), falls weder der Graph <math>G</math> noch sein [[Komplementgraph]] <math>\bar{G}</math> induzierte Kreise mit mehr als 4 Knoten haben.<ref name="Hayward1985">{{Literatur| Autor=Ryan B. Hayward| Titel=Weakly triangulated graphs| Sammelwerk=J. Comb. Theory (B)| Band=39| Seiten=200--208 | Jahr=1985 | DOI = 10.1016/0095-8956(85)90050-4}}</ref>

== Alternative Charakterisierung ==
Ein 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 [[Zusammenhang (Graphentheorie)|zusammenhängender]] [[Teilgraph|induzierter Teilgraph]] entweder ein
2-Paar enthält oder ein [[vollständiger Graph]] ist.<ref>{{Literatur| Autor=Ryan Hayward, Chính Hoàng, Frédéric Maffray| Titel=Optimizing weakly triangulated graphs| Sammelwerk=Graphs and Combinatorics| Band=5| Seiten=339–349| DOI=10.1007/BF01788689}}</ref>

== Eigenschaften ==

Die Menge der schwach chordalen Graphen ist unter Komplementbildung abgeschlossen. Das Komplement eines schwach chordalen Graphen ist selbst ein schwach chordaler Graph.

=== Beziehungen zu anderen Graphklassen ===
Alle schwach chordalen Graphen sind [[Perfekter Graph|perfekte Graphen]].<ref name="Hayward1985" />

Unterklassen der schwach chordalen Graphen sind [[chordale Graphen]] und [[chordal bipartiter Graph|chordal bipartiten Graphen]], wobei chordal bipartite Graphen keine Unterklasse der chordalen Graphen sind.

== Weblinks ==
* [https://www.graphclasses.org/classes/gc_14.html ''weakly chordal''] – Eintrag im Information System on Graph Classes and their Inclusions

== Einzelnachweise ==
<references />

[[Kategorie:Graphenklasse]]

Schwach chordaler Graph - Versionsgeschichte

imported>Redrobsche: Link und Grammatik