Transitive Hülle
Als Transitive Hülle bzw. transitiver Abschluss einer Relation bezeichnet man eine Erweiterung dieser Relation, die vereinfacht gesagt zusätzlich alle indirekt erreichbaren Paare enthält.
Beispiel
Gegeben sei eine Relation "Direkter-Vorgesetzer" mit folgenden Beziehungen:
- A ist direkter Vorgesetzer von B und C
- D ist direkter Vorgesetzer von A
- E ist direkter Vorgesetzer von D
Die Transitive Hülle dieser Relation enthält nun auch die indirekten Vorgesetzen:
- E ist Vorgesetzer von A, B, C, D
- D ist Vorgesetzer von A, B, C
- A ist Vorgesetzer von B und C
Mathematische Definition
Für die transitive Hülle R + zu einer Relation R über einer Menge M gilt nun
Sei beispielsweise R gegeben durch die Tupel (a,b),(b,c). Dann ist das Tupel (a,c) auch in R + .
Die transitive Hülle einer Relation R ist immer die kleinste transitive Relation, die R enthält.
Mit R * bezeichnet man nun noch die reflexiv transitive Hülle. Diese ist gerade die kleinste transitive Hülle, die zusätzlich reflexiv ist. Eine transitive Hülle, welche die Eigenschaft erfüllt irreflexiv zu sein, bezeichnet man auch als irreflexive transitive Hülle. Dies ist genau dann der Fall, wenn R selbst irreflexiv ist.