imported>Girus: Abschnittlink korrigiert

2022-05-09T07:28:31Z

Abschnittlink korrigiert

Neue Seite

In der [[Graphentheorie]] nennt man einen [[Graph (Graphentheorie)|Graphen]] <math>G</math> '''chordal''' oder '''trianguliert''', genau dann wenn er einer der folgenden äquivalenten Bedingungen genügt:
* Jeder induzierte [[Kreis (Graphentheorie)|Kreis]] ist ein Dreieck. Ein Kreis ist dabei induziert, genau dann wenn zwischen seinen [[Knoten (Graphentheorie)|Knoten]] keine weiteren [[Kante (Graphentheorie)|Kanten]] im Ursprungsgraphen existieren.
* Jeder minimale a-b-Trenner zu zwei Ecken a und b ist eine Clique.
* Jeder [[Induzierter Teilgraph#Untergraph bzw. Induzierter Teilgraph|induzierte Teilgraph]] enthält eine simpliziale Ecke (Rose, 1970), also eine Ecke, deren Nachbarn eine [[Clique (Graphentheorie)|Clique]] bilden.
* ''G'' ist [[Schnittgraph]] einer Menge von Teilbäumen eines Baums (Gavril, 1974).

== Eigenschaften ==
In chordalen Graphen lässt sich die Berechnung der Parameter [[Cliquenzahl]], [[chromatische Zahl]], [[Unabhängigkeitszahl]] und [[Cliquenüberdeckungszahl]] – für beliebige Graphen [[NP-Schwere|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 <math>(v_1, v_2, \ldots, v_n), V = \{v_1, v_2, \ldots, v_n\}</math> des Graphen <math>G = (V, E)</math>, sodass für jeden Graphen mit der (durch Eliminierung der Knoten <math>v_1</math> bis <math>v_{i-1}</math>) eingeschränkten Knotenmenge <math>G_i = (\{v_i, \ldots, v_n\}, E_i)</math> gilt: <math>v_i</math> ist [[Knoten (Graphentheorie)#Spezielle Knoten|simplizial]] in <math>G_i</math>. Jeder (in Bezug auf die gewählte Ordnung) „kleinste“ Knoten in <math>G_i</math> bildet also mit seinen Nachbarn eine [[Clique (Graphentheorie)|Clique]].

== Literatur ==
* Jorge L. Ramírez Alfonsín, Bruce A. Reed: ''Perfect Graphs''. Wiley 2001, ISBN 978-0-471-48970-2, S. 14 ({{Google Buch|BuchID=k74UcKNYeF4C|Seite=14|Linktext=eingeschränkte Online-Version|Land=US}})
* Sven Oliver Krumke und Hartmut Noltemeier: ''Graphentheoretische Konzepte und Algorithmen''. 2. Auflage. Vieweg-Teubner 2009. ISBN 978-3-8348-0629-1. S. 61

== Weblinks ==
* {{MathWorld |id=ChordalGraph |title=Chordal Graph}}

[[Kategorie:Graphenklasse]]

Chordaler Graph - Versionsgeschichte

imported>Girus: Abschnittlink korrigiert