Chordal

Chordal
triangulierter Graph

allgemeiner:

Beispiele:

  • Intervallgraphen
  • Bäume
  • Dreiecksgraphen

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

  • Jeder induzierte Kreis ist ein Dreieck. Ein Kreis ist dabei induziert, wenn zwischen seinen Ecken keine weiteren Kanten im Ursprungsgraph 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).

In triangulierten Graphen lässt sich die Berechnung der Parameter α, θ, ω und χ – für beliebige Graphen ein NP-vollständiges Problem – in Linearzeit durchführen. Die Charakterisierung über simpliziale Ecken ermöglicht einen Chordalitätstest in Linearzeit.

Triangulierte Graphen sind nicht zu verwechseln mit den (maximal planaren) Dreiecksgraphen. Dreiecksgraphen sind nicht alle trianguliert, wie man sich an einem Graphen überlegen kann, welcher aus einem Kreis der Länge l\ge 4 besteht, in dessen Inneren und Äußeren je ein weiterer Knoten liegt, der mit allen Knoten des Kreises benachbart ist. Umgekehrt müssen triangulierte Graphen auch nicht unbedingt Dreiecksgraphen sein, wie ein nicht planarer vollständiger Graph zeigt.


Wikimedia Foundation.

Игры ⚽ Поможем решить контрольную работу

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Chordal — Chor dal, a. Of or pertaining to a chord. [1913 Webster] …   The Collaborative International Dictionary of English

  • Chordal — Chordal, baumartiges Gewächs, von welchem der Matth. 13 erwähnte Senf gewonnen wird …   Pierer's Universal-Lexikon

  • chordal — chordal, ale, aux [kɔʀdal, o] adj. ÉTYM. 1904, in Rev. gén. des sc., no 21, p. 974; cordal, 1897; de chorde. ❖ ♦ Didact. (embryol.). De la chorde dorsale, qui concerne la chorde (ou corde) dorsale. ❖ HOM. (Du plur.) Cordeau …   Encyclopédie Universelle

  • chordal — Ⅰ. chord [1] ► NOUN ▪ a group of three or more notes sounded together in harmony. DERIVATIVES chordal adjective. ORIGIN from ACCORD(Cf. ↑accord); the spelling was influenced by CHORD(Cf. ↑chordal) …   English terms dictionary

  • chordal — adjective relating to or consisting of or emphasizing chords chordal assonance in modern music chordal rather than contrapuntal music • Pertains to noun: ↑chord • Derivationally related forms: ↑chord …   Useful english dictionary

  • Chordal style — is a term describing the kind of musical texture where all the parts, in forming a series of chords, tend to keep rhythmically in step with each other and therefore lacking the rhythmic independence of the various parts in a polyphonic or… …   Wikipedia

  • Chordal graph — A cycle (black) with two chords (green). As for this part, the graph is chordal. However, removing one green edge would result in a non chordal graph. Indeed, the other green edge with three black edges would form a cycle of length four with no… …   Wikipedia

  • Chordal space — Music theorists have often used graphs, tilings, and geometrical spaces to represent the relationship between chords. We can describe these spaces as chord spaces or chordal spaces, though the terms are relatively recent in origin. Contents 1… …   Wikipedia

  • Chordal bipartiter Graph — Dieser Artikel wurde auf der Qualitätssicherungsseite des Portals Mathematik eingetragen. Dies geschieht, um die Qualität der Artikel aus dem Themengebiet Mathematik auf ein akzeptables Niveau zu bringen. Bitte hilf mit, die Mängel dieses… …   Deutsch Wikipedia

  • Chordal problem — In the book[1] there is a generalization of the equichordal point problem attributed to R. Gardner. A Curve and Its Chord We consider a point O inside a Jordan curve with the property that for any chord [X …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”