Chordaler Graph
In der Graphentheorie nennt man einen Graphen <math>G</math> 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
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 <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 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.
Literatur
- Jorge L. Ramírez Alfonsín, Bruce A. Reed: Perfect Graphs. Wiley 2001, ISBN 978-0-471-48970-2, S. 14 ({{#if: k74UcKNYeF4C
| {{#if: {{#if: ||1}} {{#if: k74UcKNYeF4C ||1}}
| <0|&pg={{#if:|RA{{{Band}}}-}}PA14|&pg=14}}{{#if:|&q=}}#v=onepage|{{#if:|&pg=|}}{{#if:|&q=}}}}{{#if:|q=%7B%7B%7BSuchbegriff%7D%7D%7D}}|{{#if:|q=%7B%7B%7BSuchbegriff%7D%7D%7D}}}} {{#if:eingeschränkte Online-Version|{{#invoke:WLink|getEscapedTitle|eingeschränkte Online-Version}}|eingeschränkte Vorschau}}{{#if:|| in der Google-Buchsuche}}{{#ifeq:US|US|-USA}}{{#if: k74UcKNYeF4C |{{#invoke: Vorlage:GoogleBook|fine |id=k74UcKNYeF4C |errN=Parameter „BuchID“ hat falsche Länge |errC=Parameter „BuchID“ enthält ungültige Zeichen |errH=# in der „BuchID“ |errP=Parameterzuweisungen in der „BuchID“ |class=editoronly |cat={{#ifeq: 0 | 0 | Wikipedia:Vorlagenfehler/Vorlage:Google Buch}} |template= Vorlage:Google Buch}}
}}
| Es darf nur genau einer der beiden Parameter „Suchbegriff“ oder „BuchID“ ausgefüllt werden. Bitte beachte die in der Vorlage:Google Buch befindliche Dokumentation und prüfe die verwendeten Parameter.{{#ifeq: 0 | 0 | }}}}
| Es muss mindestens einer der beiden Parameter „Suchbegriff“ oder „BuchID“ ausgefüllt werden. Bitte beachte die in der Vorlage:Google Buch befindliche Dokumentation und prüfe die verwendeten Parameter.{{#ifeq: 0 | 0 | }}}}{{#invoke:TemplatePar|check
|all=
|opt= Suchbegriff= BuchID= Seite= Band= SeitenID= Hervorhebung= Linktext= Land= KeinText=
|cat= {{#ifeq: 0 | 0 | Wikipedia:Vorlagenfehler/Vorlage:Google Buch}}
|template= Vorlage:Google Buch
|format=
}}{{#if:eingeschränkte Online-Version|{{#if:{{#invoke:WLink|isBracketedLink|eingeschränkte Online-Version}}|}}}})
- Sven Oliver Krumke und Hartmut Noltemeier: Graphentheoretische Konzepte und Algorithmen. 2. Auflage. Vieweg-Teubner 2009. ISBN 978-3-8348-0629-1. S. 61
Weblinks
- {{#if: | {{{author}}} | Eric W. Weisstein }}: Chordal Graph. In: MathWorld (englisch). {{#if: ChordalGraph | {{#ifeq: {{#property:P2812}} | ChordalGraph | | {{#if: {{#property:P2812}} | {{#ifeq: 0 | 0 | }} | {{#ifeq: 0 | 0 | }} }} }} }}