Transitive closure

The transitive closure and the transitive closure of a (two -digit ) relation is an extension of this relation, which - put simply - in addition contains all pairs indirectly accessible (and thus is transitive ). The transitive closure can be computed with the Warshall algorithm.

The reflexive - transitive closure and the reflexive - transitive closure of the relation obtained by adding to the transitive closure of reflexivity missing pairs on the diagonal.

Illustrative example

Given a relation " Direct - manager " with the following relations:

  • C is the immediate superior of D and E
  • B is the immediate superior of C
  • A is the immediate superior of B

The transitive closure of this relation now contains, in addition, the indirect superiors:

  • A supervisor of B, C, D, E
  • B is superior of C, D, E
  • C is superior of D and E

Mathematical definition

The transitive closure of a binary relation on a set is given by:

The reflexive - transitive closure is then given by itself

Examples

  • Is given by the two pairs, and then additionally includes the pair. For the other couples come and do so.
  • If the successor relation on the set of natural numbers (ie ), then results as a transitive closure of the greater- relation. The reflexive - transitive closure is the greater- equal relation.
  • The relation on the set of the 26 letters of the Latin alphabet is given by and are ( in the usual arrangement of the alphabet ) directly adjacent. As a transitive closure of results in the Allrelation, ie the relation that contains all pairs above the base amount ( because by multiple transition to a neighbor you can by a letter any other letters reach ). As already is reflexive, applies here.

Properties

  • Is the smallest transitive relation that contains.
  • Is the smallest reflexive and transitive relation that contains.
  • With the help of the powers concerning the concatenation of relations will allow the two cases of a relation written as (infinite ) union:
  • The transitive closure of a relation on a set is the intersection of all transitive supersets of, so.
  • The analogous statement is true for the reflexive - transitive closure.
  • The transition to the transitive closure is a closure operator in the abstract sense (which is also the name suggests ). The same is true for the reflexive - transitive closure.
  • For reflexive relations. However, it can also occur for irreflexive relations that the transitive closure is already reflexive.
  • For arbitrary relations is a quasi-ordering.

Applications

In theoretical computer science derivations in a formal grammar are defined as sequences of derivation steps. The derivability is thus the reflexive - transitive closure of the transition relation.

Transitive reduction

The counterpart of the transitive closure is the transitive reduction. A transitive reduction of a relation is a minimal relation such that, that is a minimal relation with the same transitive closure.

There are both relations, for which there is no transitive reduction, as well as those for which there are several different transitive reductions. For finite directed acyclic graphs, however, there is the transitive reduction and is unique.

Ordered pair Finitary relation
675848
de