Hauptmenü öffnen

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 transitive Hülle 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.

Inhaltsverzeichnis

Anschauliches BeispielBearbeiten

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

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 DefinitionBearbeiten

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.

BeispieleBearbeiten

  • 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  .

EigenschaftenBearbeiten

  •   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 (was ja auch der Name schon nahelegt). 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 ja immer die Allrelation (also  ) 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:  .

AnwendungenBearbeiten

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 ReduktionBearbeiten

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 auchBearbeiten

WeblinksBearbeiten

EinzelnachweiseBearbeiten

  1. a b c Kenneth H. Rosen: Closure of Binary Relation, 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-2016, §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: Wofram MathWorld 1999-2018
  7. Siehe Transitive reduction (englisch)
  8. Eric Weisstein: Reflexive Reduction, Wolfram Research: Wofram MathWorld 1999-2018
  9. Notation folgt [1], auf: ProofWiki vom 21. Februar 2018
  10. Symmetric Closure §Notes, auf: ProofWiki vom 12. September 2016