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.
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
Die transitive Hülle einer zweistelligen Relation auf einer Menge ist gegeben durch:
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 :\Longleftrightarrow }
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 .
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.
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]
Kenneth Rosen: Closures of Relations, Rutgers School of Arts and Sciences, Department of Computer Sciences (CS), Discrete Mathematics and Its Applications: Section6.4, S.TP2f. Die des Autors ist .