imported>Crazy1880: Vorlagen-fix (GoogleBuch)

2022-11-19T19:31:02Z

Vorlagen-fix (GoogleBuch)

Neue Seite

In der [[Graphentheorie]] heißt ein endlicher [[Graph (Graphentheorie)|Graph]] ''G'' '''chordal bipartit''' (englisch ''chordal bipartite''), falls jeder induzierte [[Zyklus (Graphentheorie)#Kreis|Kreis]] in ''G'' genau die Länge 4 hat. Auf dieser Graphenklasse lassen sich einige [[NP-schwer]]e Probleme effizient lösen.

== Definitionen ==

Ein [[bipartiter Graph]] <math>G=(V,E)</math> mit bipartiter Zerlegung <math>V=A\cup B</math> 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 <math>G</math> durch Hinzufügen aller Kanten zwischen Knoten in <math>A</math> entstehende Graph ist [[stark chordal]].
* es existiert eine Anordnung der Kanten, so dass (für die durch <math>G_0=G, G_i=G_{i-1}-e_i</math> definierte Folge) die Vereinigung der [[Nachbarschaft (Graphentheorie)|Nachbarschaften]] der beiden Knoten von <math>e_i=\left\{x_i,y_i\right\}</math> ein vollständig bipartiter Teilgraph in <math>G_{i-1}</math> ist, d. h. jeder Knoten in <math>N(x_i)</math> ist mit jedem Knoten in <math>N(y_i)</math> durch eine Kante in <math>G_{i-1}</math> verbunden.

Man beachte, dass chordal bipartite Graphen nicht [[Chordale Graphen|chordal]] sein müssen. Genauer wäre eigentlich die Bezeichnung ''schwach chordal bipartit'', da diese Graphen [[Schwach chordaler Graph|schwach chordal]] und [[Bipartiter Graph|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.<ref>Theorem 2.3 in: Brandstädt, Andreas: ''Classes of bipartite graphs related to chordal graphs.'' [[Discrete Applied Mathematics]] 32 (1991) 51–60</ref>

== 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 [https://dml.cz/bitstream/handle/10338.dmlcz/127379/CzechMathJ_47-1997-4_1.pdf PDF]
* Brandstädt, Andreas; Le, Van Bang; Spinrad, Jeremy (1999), ''Graph Classes: A Survey'', SIAM Monographs on Discrete Mathematics and Applications, ISBN 0-89871-432-X.
* Jorge L. Ramírez Alfonsín, Bruce A. Reed: ''Perfect Graphs''. Wiley 2001, ISBN 978-0-471-48970-2, S. 141 ({{Google Buch |BuchID=k74UcKNYeF4C |Seite=141}})
* Golumbic, Martin Charles; Goss, Clinton F.: ''Perfect elimination and chordal bipartite graphs.'' J. Graph Theory 2 (1978), no. 2, 155–163. [https://onlinelibrary.wiley.com/doi/pdf/10.1002/jgt.3190020209 PDF]

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

== Einzelnachweise ==
<references />

[[Kategorie:Bipartiter Graph]]

Chordal bipartiter Graph - Versionsgeschichte

imported>Crazy1880: Vorlagen-fix (GoogleBuch)