Transitive closure

Uses your system voice; voice and rate in settings.

Snapshot

≈ 5 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

In mathematics, the transitive closure of a homogeneous binary relation on a set is the smallest relation on that contains and is transitive. For finite sets, "smallest" can be taken in its usual sense, of having the fewest related pairs; for infinite sets is the unique minimal transitive superset of . For example, if is a set of airports and means "there is a direct flight from airport to airport " (for and in ), then the transitive closure of on is the relation such that means "it is possible to fly from to in one or more flights". More formally, the transitive closure of a binary relation on a set is the smallest (w.r.t. ⊆) transitive relation on such that ⊆ ; see . We have = if, and only if, itself is transitive. Conversely, transitive reduction reduces a minimal relation from a given relation such that they have the same closure, that is, ; however, many different with this property may exist. Both transitive closure and transitive reduction are also used in the closely related area of graph theory.

In mathematics, the transitive closure of a homogeneous binary relation on a set is the smallest relation on that contains and is transitive. For finite sets, "smallest" can be taken in its usual sense, of having the fewest related pairs; for infinite sets is the unique minimal transitive superset of . For example, if is a set of airports and means "there is a direct flight from airport to airport " (for and in ), then the transitive closure of on is the relation such that means "it is possible to fly from to in one or more flights". More formally, the transitive closure of a binary relation on a set is the smallest (w.r.t. ⊆) transitive relation on such that ⊆ ; see . We have = if, and only if, itself is transitive. Conversely, transitive reduction reduces a minimal relation from a given relation such that they have the same closure, that is, ; however, many different with this property may exist. Both transitive closure and transitive reduction are also used in the closely related area of graph theory. R^{+}=\bigcup_{i = 1}^{\infty} R^i. where R^i is the i-th power of R, defined inductively by R^1 = R and, for i>0 , R^{i+1} = R \circ R^i where \circ denotes composition of relations. To show that the above definition of R + is the least transitive relation containing R, we show that it contains R, that it is transitive, and that it is the smallest set with both of those characteristics. R \subseteq R^{+} : R^+ contains all of the R^i , so in particular R^+ contains R . R^{+} is transitive: If (s_1, s_2), (s_2, s_3)\in R^+ , then (s_1, s_2)\in R^j and (s_2, s_3)\in R^k for some j,k by definition of R^+ . Since composition is associative, R^{j+k} = R^j \circ R^k ; hence (s_1, s_3)\in R^{j+k} \subseteq R^+ by definition of \circ and R^+ . R^{+} is minimal, that is, if T is any transitive relation containing R , then R^{+} \subseteq T : Given any such T , induction on i can be used to show R^i\subseteq T for all i as follows: Base: R^1 = R \subseteq T by assumption. Step: If R^i\subseteq T holds, and (s_1, s_3)\in R^{i+1} = R \circ R^i , then (s_1, s_2) \in R and (s_2, s_3)\in R^i for some s_2 , by definition of \circ . Hence, (s_1, s_2), (s_2, s_3)\in T by assumption and by induction hypothesis. Hence (s_1, s_3)\in T by transitivity of T ; this completes the induction. Finally, R^i\subseteq T for all i implies R^{+} \subseteq T by definition of R^{+} . In computer science, the concept of transitive closure can be thought of as constructing a data structure that makes it possible to answer reachability questions. That is, can one get from node a to node d in one or more hops? A binary relation tells you only that node a is connected to node b, and that node b is connected to node c, etc. After the transitive closure is constructed, as depicted in the following figure, in an O(1)-time operation one may determine that node d is reachable from node a. The data structure is typically stored as a Boolean matrix, so if matrix[1][4] = true, then it is the case that node 1 can reach node 4 through one or more hops. The transitive closure of the adjacency relation of a directed acyclic graph (DAG) is the reachability relation of the DAG and a strict partial order. , the transitive closure of an undirected graph The transitive closure of an undirected graph produces a cluster graph, a disjoint union of cliques. Constructing the transitive closure is an equivalent formulation of the problem of finding the components of the graph. Keller, U., 2004, Some Remarks on the Definability of Transitive Closure in First-order Logic and Datalog (unpublished manuscript) Appendix C (online only)

Text derived from https://en.wikipedia.org/w/index.php?oldid=1365947310 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

4 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.