Lexikon der Mathematik: chordaler Graph
triangulierter Graph, ein GraphG, der keinen induzierten Kreis der Länge größer oder gleich Vier enthält.
Gleichbedeutend damit ist die Aussage, daß in G jeder Kreis der Länge größer oder gleich Vier eine Sehne hat.
Ist C = x0x1…xrx0 ein Kreis des Graphen G mit r ≥ 3, so nennt man eine Kante xixj ∈ K(G) mit
Falls eine Ecke s eines Graphen G in genau einer gesättigten CliqueH von G enthalten ist, so bezeichnet man s als simpliziale Ecke und nennt dann H Simplex von G.
Im Zusammenhang mit den simplizialen Ecken fand A. Frank 1975 folgende interessante Charakterisierung der chordalen Graphen.
Ein Graph G ist genau dann chordal, wenn jeder induzierte Teilgraph von G entweder eine Clique ist oder zwei nicht adjazente simpliziale Ecken besitzt.
Insbesondere enthält jeder chordale Graph mindestens eine simpliziale Ecke.
Es sei (v1,v2,…,vn) eine Reihenfolge der Eckenmenge E(G) eines gegebenen Graphen G und
Mit Hilfe des obigen Satzes läßt sich eine weitere Charakterisierung der chordalen Graphen nachweisen.
Ein Graph ist genau dann chordal, wenn er ein perfektes Eckeneliminationsschema besitzt.
Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.