Transitiver Abschluss

Transitiver Abschluss

Die transitive Hülle bzw. der transitive Abschluss einer (zweistelligen) Relation ist eine Erweiterung dieser Relation, die – vereinfacht gesagt – zusätzlich alle indirekt erreichbaren Paare enthält (und damit transitiv ist).

Die reflexiv-transitive Hülle bzw. den reflexiv-transitiven Abschluss der Relation erhält man dann, indem die für die Reflexivität notwendigen Paare noch hinzugefügt werden.

Inhaltsverzeichnis

Anschauliches Beispiel

Gegeben sei eine Relation „Direkter-Vorgesetzter“ mit folgenden Beziehungen:

  • C ist direkter Vorgesetzter von D und E
  • B ist direkter Vorgesetzter von C
  • A ist direkter Vorgesetzter von B

Die transitive Hülle dieser Relation enthält nun zusätzlich auch die indirekten Vorgesetzten:

  • A ist Vorgesetzter von B, C, D, E
  • B ist Vorgesetzter von C, D, E
  • C ist Vorgesetzter von D und E

Mathematische Definition

Die transitive Hülle R + einer zweistelligen Relation R auf einer Menge M ist gegeben durch:

x \ R^{+} \ y : \Leftrightarrow \exists n \geq 0 \ \exists x_1,\dots ,x_n \in M: x \,R \,x_1 \,R \,x_2 \,R \dots \,R \,x_n \,R \,y

Die reflexiv-transitive Hülle R * ergibt sich dann durch

x \ R^{*} \ y : \Leftrightarrow x = y \or x \ R^{+} \ y

Beispiele

  • Ist R gegeben durch die zwei Paare (a,b) und (b,c), dann enthält R + zusätzlich das Paar (a,c). Für R * kommen die weiteren Paare (a,a), (b,b) und (c,c) dazu.
  • Ist R die Nachfolgerrelation auf der Menge der natürlichen Zahlen (also a \,R \,b : \Longleftrightarrow a = b + 1), dann ergibt sich als transitive Hülle von R die Größer-Relation >\ . Die reflexiv-transitive Hülle ist die Größer-Gleich-Relation \ge .
  • Die Relation R auf der Menge der 26 Buchstaben des lateinischen Alphabets sei gegeben durch \alpha \,R \,\beta : \Longleftrightarrow \alpha\ und \beta\ sind (in der gewöhnlichen Anordnung des Alphabets) direkt benachbart. Als transitive Hülle von R ergibt sich die Allrelation, also die Relation, die alle Paare über der Grundmenge enthält (denn durch mehrfachen Übergang zu einem Nachbarn kann man von einem Buchstaben jeden beliebigen anderen Buchstaben erreichen). Da R + bereits reflexiv ist, gilt hier R * = R + .

Eigenschaften

  • R + ist die kleinste transitive Relation, die R enthält.
  • R * ist die kleinste reflexive und transitive Relation, die R enthält.
  • Mit Hilfe der Potenzen bezüglich der Verkettung \circ von Relationen lassen sich die beiden Hüllen einer Relation R auch als (unendliche) Vereinigung schreiben:
    R^{+} = R^1 \cup R^2 \cup R^3 \cup \dots
    R^{*} = R^0 \cup R^1 \cup R^2 \cup \dots
  • Die transitive Hülle einer Relation R auf einer Menge M ist die Schnittmenge aller transitiven Obermengen von R, also
    R^{+} = \bigcap\{S \subseteq M \times M | S \ \mathrm{ist \ transitiv}, R \subseteq S \}.
Die Menge, über die hier der Durchschnitt gebildet wird, ist nicht leer, da sie ja immer die Allrelation (also M \times M) enthält.
  • Die analoge Aussage gilt für die reflexiv-transitive Hülle.
  • Der Übergang zur transitiven Hülle ist ein Hüllenoperator im abstrakten Sinne (was ja auch der Name schon nahelegt). Das gleiche gilt für die reflexiv-transitive Hülle.
  • Für reflexive Relationen R gilt R * = R + . Allerdings kann es auch für irreflexive Relationen vorkommen, dass der transitive Abschluss bereits reflexiv ist.
  • Für beliebige Relationen R ist R * eine Quasiordnung.

Anwendungen

In der Theoretischen Informatik werden Ableitungen in einer formalen Grammatik als Folgen von Ableitungsschritten v \Rightarrow w definiert. Die Ableitbarkeit ist also der reflexiv-transitive Abschluss \Rightarrow^{*} der Transitionsrelation \Rightarrow.


Wikimedia Foundation.

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

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

  • Reflexiv-transitiver Abschluss — Die transitive Hülle bzw. der transitive Abschluss einer (zweistelligen) Relation ist eine Erweiterung dieser Relation, die – vereinfacht gesagt – zusätzlich alle indirekt erreichbaren Paare enthält (und damit transitiv ist). Die reflexiv… …   Deutsch Wikipedia

  • Topologische Ordnung — Topologische Sortierung bezeichnet eine Reihenfolge von Dingen, bei der vorgegebene Abhängigkeiten erfüllt sind. Der Name „topologische Sortierung“ leitet sich von den griechischen Wörtern τόπος (tópos = „Ort“/„Platz“) und λόγος (lógos =… …   Deutsch Wikipedia

  • Topologisches Sortieren — Topologische Sortierung bezeichnet eine Reihenfolge von Dingen, bei der vorgegebene Abhängigkeiten erfüllt sind. Der Name „topologische Sortierung“ leitet sich von den griechischen Wörtern τόπος (tópos = „Ort“/„Platz“) und λόγος (lógos =… …   Deutsch Wikipedia

  • Sino-Tibetisch — Die sinotibetischen Sprachen bilden mit rund 1300 Mio. Sprechern die zweitgrößte Sprachfamilie der Erde. Die insgesamt etwa 340 Sprachen werden in China, dem Himalaya Gebiet und Südostasien gesprochen. Sie teilen sich nach Meinung der meisten… …   Deutsch Wikipedia

  • Sino-Tibetische Sprache — Die sinotibetischen Sprachen bilden mit rund 1300 Mio. Sprechern die zweitgrößte Sprachfamilie der Erde. Die insgesamt etwa 340 Sprachen werden in China, dem Himalaya Gebiet und Südostasien gesprochen. Sie teilen sich nach Meinung der meisten… …   Deutsch Wikipedia

  • Sino-Tibetische Sprachen — Die sinotibetischen Sprachen bilden mit rund 1300 Mio. Sprechern die zweitgrößte Sprachfamilie der Erde. Die insgesamt etwa 340 Sprachen werden in China, dem Himalaya Gebiet und Südostasien gesprochen. Sie teilen sich nach Meinung der meisten… …   Deutsch Wikipedia

  • Sino-tibetische Sprachen — Die sinotibetischen Sprachen bilden mit rund 1300 Mio. Sprechern die zweitgrößte Sprachfamilie der Erde. Die insgesamt etwa 340 Sprachen werden in China, dem Himalaya Gebiet und Südostasien gesprochen. Sie teilen sich nach Meinung der meisten… …   Deutsch Wikipedia

  • Sino-tibetische Sprachfamilie — Die sinotibetischen Sprachen bilden mit rund 1300 Mio. Sprechern die zweitgrößte Sprachfamilie der Erde. Die insgesamt etwa 340 Sprachen werden in China, dem Himalaya Gebiet und Südostasien gesprochen. Sie teilen sich nach Meinung der meisten… …   Deutsch Wikipedia

  • Sinotibetisch — Die sinotibetischen Sprachen bilden mit rund 1300 Mio. Sprechern die zweitgrößte Sprachfamilie der Erde. Die insgesamt etwa 340 Sprachen werden in China, dem Himalaya Gebiet und Südostasien gesprochen. Sie teilen sich nach Meinung der meisten… …   Deutsch Wikipedia

  • Sinotibetische Sprachen — Die sinotibetischen Sprachen bilden mit rund 1,3 Milliarden Sprechern die zweitgrößte Sprachfamilie der Erde. Die insgesamt etwa 340 Sprachen werden in China, dem Himalaya Gebiet und Südostasien gesprochen. Sie teilen sich nach Meinung der… …   Deutsch Wikipedia

Share the article and excerpts

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