www.wikidata.de-de.nina.az

Chordaler Graph In der Graphentheorie nennt man einen Graphen G displaystyle G chordal oder trianguliert genau dann wenn

Chordaler Graph

In der Graphentheorie nennt man einen Graphen chordal oder trianguliert, genau dann wenn er einer der folgenden äquivalenten Bedingungen genügt:

  • Jeder induzierte Kreis ist ein Dreieck. Ein Kreis ist dabei induziert, genau dann wenn zwischen seinen Knoten keine weiteren Kanten im Ursprungsgraphen existieren.
  • Jeder minimale a-b-Trenner zu zwei Ecken a und b ist eine Clique.
  • Jeder induzierte Teilgraph enthält eine simpliziale Ecke (Rose, 1970), also eine Ecke, deren Nachbarn eine Clique bilden.
  • G ist Schnittgraph einer Menge von Teilbäumen eines Baums (Gavril, 1974).

Eigenschaften Bearbeiten

In chordalen Graphen lässt sich die Berechnung der Parameter Cliquenzahl, chromatische Zahl, Unabhängigkeitszahl und Cliquenüberdeckungszahl – für beliebige Graphen NP-schwere Probleme – in Linearzeit durchführen. Die Charakterisierung über simpliziale Ecken ermöglicht einen Chordalitätstest in Linearzeit. Als perfekte Eliminationsordnung bezeichnet man dabei eine Knotenreihenfolge des Graphen , sodass für jeden Graphen mit der (durch Eliminierung der Knoten bis ) eingeschränkten Knotenmenge gilt: ist simplizial in . Jeder (in Bezug auf die gewählte Ordnung) „kleinste“ Knoten in bildet also mit seinen Nachbarn eine Clique.

Literatur Bearbeiten

  • Jorge L. Ramírez Alfonsín, Bruce A. Reed: Perfect Graphs. Wiley 2001, ISBN 978-0-471-48970-2, S. 14 (eingeschränkte Online-Version in der Google-Buchsuche-USA)
  • Sven Oliver Krumke und Hartmut Noltemeier: Graphentheoretische Konzepte und Algorithmen. 2. Auflage. Vieweg-Teubner 2009. ISBN 978-3-8348-0629-1. S. 61

Weblinks Bearbeiten

wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
In der Graphentheorie nennt man einen Graphen G displaystyle G chordal oder trianguliert genau dann wenn er einer der folgenden aquivalenten Bedingungen genugt Jeder induzierte Kreis ist ein Dreieck Ein Kreis ist dabei induziert genau dann wenn zwischen seinen Knoten keine weiteren Kanten im Ursprungsgraphen existieren Jeder minimale a b Trenner zu zwei Ecken a und b ist eine Clique Jeder induzierte Teilgraph enthalt eine simpliziale Ecke Rose 1970 also eine Ecke deren Nachbarn eine Clique bilden G ist Schnittgraph einer Menge von Teilbaumen eines Baums Gavril 1974 Eigenschaften BearbeitenIn chordalen Graphen lasst sich die Berechnung der Parameter Cliquenzahl chromatische Zahl Unabhangigkeitszahl und Cliquenuberdeckungszahl fur beliebige Graphen NP schwere Probleme in Linearzeit durchfuhren Die Charakterisierung uber simpliziale Ecken ermoglicht einen Chordalitatstest in Linearzeit Als perfekte Eliminationsordnung bezeichnet man dabei eine Knotenreihenfolge v 1 v 2 v n V v 1 v 2 v n displaystyle v 1 v 2 ldots v n V v 1 v 2 ldots v n nbsp des Graphen G V E displaystyle G V E nbsp sodass fur jeden Graphen mit der durch Eliminierung der Knoten v 1 displaystyle v 1 nbsp bis v i 1 displaystyle v i 1 nbsp eingeschrankten Knotenmenge G i v i v n E i displaystyle G i v i ldots v n E i nbsp gilt v i displaystyle v i nbsp ist simplizial in G i displaystyle G i nbsp Jeder in Bezug auf die gewahlte Ordnung kleinste Knoten in G i displaystyle G i nbsp bildet also mit seinen Nachbarn eine Clique Literatur BearbeitenJorge L Ramirez Alfonsin Bruce A Reed Perfect Graphs Wiley 2001 ISBN 978 0 471 48970 2 S 14 eingeschrankte Online Version in der Google Buchsuche USA Sven Oliver Krumke und Hartmut Noltemeier Graphentheoretische Konzepte und Algorithmen 2 Auflage Vieweg Teubner 2009 ISBN 978 3 8348 0629 1 S 61Weblinks BearbeitenEric W Weisstein Chordal Graph In MathWorld englisch Abgerufen von https de wikipedia org w index php title Chordaler Graph amp oldid 222735888