Direkt zum Inhalt

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 = x0x1xrx0 ein Kreis des Graphen G mit r ≥ 3, so nennt man eine Kante xixjK(G) mit \begin{eqnarray}1\lt |i-j|\lt r\end{eqnarray} eine Sehne des Kreises C. Es ist leicht zu sehen, daß jeder induzierte Teilgraph eines chordalen Graphen wieder chordal ist.

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 \begin{eqnarray}{G}_{i}=G[\{{v}_{i},{v}_{i+1},\ldots, {v}_{n}\}]\end{eqnarray} der von den Ecken vi, vi+1,…,vn induzierte Teilgraph für i = 1,2,…,n. Man nennt (v1, v2,…, vn) ein perfektes Eckeneliminationsschema von G, wenn vi eine simpliziale Ecke von Gi für alle i = 1, 2…,n ist.

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.

  • Die Autoren
- Prof. Dr. Guido Walz

Schreiben Sie uns!

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.

Partnerinhalte

Bitte erlauben Sie Javascript, um die volle Funktionalität von Spektrum.de zu erhalten.