Die transitive Hülle bzw. der transitive Abschluss einer (zweistelligen) Relation ist die kleinste Erweiterung dieser Relation, die transitiv ist. Sie kann mit dem Floyd-Warshall-Algorithmus berechnet werden.

Die reflexiv-transitive Hülle bzw. den reflexiv-transitiven Abschluss der Relation erhält man, indem man zur transitiven Hülle die für Reflexivität noch fehlenden Paare auf der Diagonalen hinzufügt.

Anschauliches Beispiel

Bearbeiten
 
Illustration des Beispiels: durchgezogene Pfeile zeigen direkte Beziehungen an, gestrichelte Pfeile die in der transitiven Hülle dazu kommenden Beziehungen

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

Bearbeiten

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

 [1]

Die reflexive Hülle   ist einfach die Vereinigung mit der Diagonalen (Identität), wodurch die Reflexivität erreicht wird:

 [2][1]   d. h.   (siehe Identitätsrelation).

Die reflexiv-transitive Hülle   ergibt sich dann durch

 

Ergänzung: Eine weitere Hüllenbildung dieser Art ist die symmetrische Hülle:

 , äquivalent zur Definition  [3][4][1] (siehe inverse Relation).

Zur Äquivalenzhülle siehe: Äquivalenzrelation §Äquivalenzhülle.

Beispiele

Bearbeiten
  • Ist   gegeben durch die zwei Paare   und  , dann enthält   zusätzlich das Paar  . Für   kommen die weiteren Paare  ,   und   dazu.
  • Ist   die Nachfolgerrelation auf der Menge der natürlichen Zahlen (also  ), dann ergibt sich als transitive Hülle von   die Größer-Relation  . Die reflexiv-transitive Hülle ist die Größer-Gleich-Relation  .
  • Die Relation   auf der Menge der 26 Buchstaben des lateinischen Alphabets sei gegeben durch     und   sind (in der gewöhnlichen Anordnung des Alphabets) direkt benachbart. Als transitive Hülle von   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   bereits reflexiv ist, gilt hier  .

Eigenschaften

Bearbeiten
  •   ist die kleinste transitive Relation, die   enthält.
  •   ist die kleinste reflexive und transitive Relation, die   enthält.
  • Der Übergang zur transitiven Hülle ist ein Hüllenoperator im abstrakten Sinne. Das Gleiche gilt für die reflexiv-transitive Hülle.
  • Die transitive Hülle einer Relation   auf einer Menge   ist die Schnittmenge aller transitiven Obermengen von  , also
     .
Die Menge, über die hier der Durchschnitt gebildet wird, ist nicht leer, da sie stets die Allrelation   enthält.
  • Die analoge Aussage gilt für die reflexiv-transitive Hülle.
  • Mit Hilfe der Potenzen bezüglich der Verkettung   von Relationen lassen sich die beiden Hüllen einer Relation   auch als (unendliche) Vereinigung schreiben:
     
     
  • Im Zusammenhang mit einer Relation   auf einer Menge   versteht man unter einem Weg eine endliche Sequenz   von Elementen aus   mit   für alle   mit  . Die um 1 verminderte Länge der Sequenz   ist die Länge des Wegs. Der Weg führt vom Anfangspunkt   zum Endpunkt  .
    Die durch   erzeugte reflexiv-transitive Hülle   kann als Relation dadurch beschrieben werden, dass   genau dann gilt, wenn es einen Weg von   nach   gibt.
    Analog gilt für die transitive Hülle  , dass   genau dann gilt, wenn es einen Weg von   nach   mit einer Länge größer 0 gibt.[5]
  • Es gibt endlich viele Elemente   mit  ,   und für   jeweils   oder  .
  • Für reflexive Relationen   gilt  . Allerdings kann es auch für irreflexive Relationen vorkommen, dass der transitive Abschluss bereits reflexiv ist.
  • Für beliebige Relationen   ist   eine Quasiordnung.
  • Idempotenz der Hülloperatoren:  .

Anwendungen

Bearbeiten

In der Theoretischen Informatik werden Ableitungen in einer formalen Grammatik als Folgen von Ableitungsschritten   definiert. Die Ableitbarkeit ist also der reflexiv-transitive Abschluss   der Transitionsrelation  .

Transitive Reduktion

Bearbeiten

Das Gegenstück zur transitiven Hülle ist die transitive Reduktion. Eine transitive Reduktion einer Relation   ist eine minimale Relation  , so dass  , also eine minimale Relation mit derselben transitiven Hülle.[6]

Es gibt sowohl Relationen, für die keine transitive Reduktion existiert, als auch solche, für die mehrere unterschiedliche transitive Reduktionen existieren. Für gerichtete endliche azyklische Graphen jedoch existiert die transitive Reduktion und ist eindeutig:  . Das folgende Bild zeigt für diesen Fall Graphen, die einer nichttransitiven binären Relation (links) und ihrer transitiven Reduktion (rechts) entsprechen:[7]

   


Verwandte Begriffe:

  • Reflexive Reduktion: Die reflexive Reduktion einer Relation   auf einer Menge   ist die minimale Relation  , mit derselben reflexiven Hülle. Das bedeutet, dass   äquivalent ist zu   oder  .[8][9]
  • Es gibt kein vergleichbares Konzept einer symmetrischen Reduktion von Relationen, etwa die (symmetrische) Relation  . [10]

Siehe auch

Bearbeiten
Bearbeiten

Einzelnachweise

Bearbeiten
  1. a b c Kenneth H. Rosen: Closure of Binary Relation (Memento vom 21. August 2018 im Internet Archive), in: CS381 Discrete Structures, Old Dominion University, Norfolk, Virginia, 1999. Der Autor benutzt die Notationen  ,  ,  .
  2. H. W. Lang: Mathematische Grundlagen: Menge, Relation, Abbildung, Hochschule Flensburg, 1997-2022, Abschnitt Relation
  3. Notation   wie in Symmetric Closure, auf: ProofWiki vom 12. September 2016
  4. Kenneth Rosen: Closures of Relations, Rutgers School of Arts and Sciences, Department of Computer Sciences (CS), Discrete Mathematics and Its Applications: Section 6.4, S. TP 2f. Die des Autors ist  .
  5. Siehe Metz 2010, S. 1. Im graphentheoretischen Sinn handelt es sich um einen gerichteten Weg (ohne Kantengewichte) der gegebenen Länge.
  6. Eric Weisstein: Transitive Reduction, Wolfram Research: Wolfram MathWorld 1999-2018
  7. Siehe Transitive reduction (englisch)
  8. Eric Weisstein: Reflexive Reduction, Wolfram Research: Wolfram MathWorld 1999-2018
  9. Notation folgt Definition:Reflexive Reduction, auf: ProofWiki vom 21. Februar 2018
  10. Symmetric Closure §Notes, auf: ProofWiki vom 12. September 2016