Triangulierter Graph - LinkFang.de





Triangulierter Graph


In der Graphentheorie nennt man einen Graphen [math]G[/math] 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).

Eigenschaften

In triangulierten 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.

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 [math]l\ge 4[/math] 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.

Literatur

Weblinks


Kategorien: Graphentheorie

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Triangulierter Graph (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.