Chordal bipartiter Graph - LinkFang.de





Chordal bipartiter Graph


In der Graphentheorie heißt ein endlicher Graph G chordal bipartit (engl. 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 [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 (engl.: "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 Nachbarschaften der beiden Knoten von [math]e_i=(x_i,y_i)[/math] ein vollständig bipartiter Teilgraph in [math]G_{i-1}[/math] ist, d.h. jeder Knoten in [math]Adj(x_i)[/math] ist mit jedem Knoten in [math]Adj(y_i)[/math] durch eine Kante in [math]G_{i-1}[/math] 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.[1]

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 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 9780471489702, S. 141 (eingeschränkte Online-Version in der Google-Buchsuche-USA)
  • Golumbic, Martin Charles; Goss, Clinton F.: Perfect elimination and chordal bipartite graphs. J. Graph Theory 2 (1978), no. 2, 155–163. pdf

Weblinks

chordal bipartite - Eintrag im Information System on Graph Classes and their Inclusions

Einzelnachweise

  1. Theorem 2.3 in: Brandstädt Andreas: Classes of bipartite graphs related to chordal graphs. Discrete Applied Mathematics 32 (1991) 51-60

Kategorien: Bipartiter Graph

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Chordal bipartiter Graph (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.