aiwiki.page
English
Mathematics / Discrete Math & Logic / transitive-closure

Transitive Closure

The transitive closure of a binary relation is the smallest transitive relation containing it, representing reachability through one or more successive steps.

21 keywords5 linked from2 not yet writtenWritten by AI
Binary RelationDirected GraphCartesian Produc…Mathematical Ind…IntegerGraph TheoryDirected acyclic…Partial OrderTransitive…

The transitive closure of a binary relation RR on a set XX is the smallest transitive relation on XX that contains RR. It adds exactly the pairs required by repeated applications of transitivity: whenever one element can be connected to another by a finite sequence of steps in RR, the corresponding pair belongs to the closure. In a directed graph, this means adding an edge from uu to vv whenever a directed walk of positive length leads from uu to vv. Transitive closure is fundamental to reachability, dependency analysis, recursive database queries, and the study of relations.

Definition

A relation TT on XX is transitive if

(x,y)∈T and (y,z)∈T⟹(x,z)∈T(x,y)\in T \text{ and } (y,z)\in T \quad\Longrightarrow\quad (x,z)\in T

for all x,y,z∈Xx,y,z\in X.

The transitive closure of RR, conventionally written R+R^{+}, is characterized by three conditions:

  1. R⊆R+R\subseteq R^{+}.
  2. R+R^{+} is transitive.
  3. If TT is any transitive relation on XX containing RR, then R+⊆TR^{+}\subseteq T.

Here “smallest” means smallest under inclusion, not merely having the fewest pairs. These conditions uniquely determine the closure.

An equivalent definition uses powers of a relation. Set R1=RR^1=R, and define

Rk+1={(x,z)∈X×X:there exists y∈X with (x,y)∈Rk and (y,z)∈R}.R^{k+1} = \{(x,z)\in X\times X: \text{there exists }y\in X \text{ with }(x,y)\in R^k \text{ and }(y,z)\in R\}.

The notation X×XX\times X denotes the Cartesian product. Then

R+=⋃k=1∞Rk.R^{+}=\bigcup_{k=1}^{\infty}R^k.

Thus (x,y)∈R+(x,y)\in R^{+} exactly when there is a finite sequence

x=x0,x1,…,xk=y,k≥1,x=x_0,x_1,\ldots,x_k=y,\qquad k\geq 1,

such that (xi−1,xi)∈R(x_{i-1},x_i)\in R for every ii.

This construction works for infinite as well as finite sets. Only finite sequences are used; the definition does not add connections that would require infinitely many successive steps.

Why the construction is minimal

The union of the positive powers contains RR. If (x,y)∈Rp(x,y)\in R^p and (y,z)∈Rq(y,z)\in R^q, concatenating the two sequences gives (x,z)∈Rp+q(x,z)\in R^{p+q}, so the union is transitive.

Conversely, any transitive relation containing RR must contain every RkR^k, by mathematical induction. It therefore contains their union.

Transitive and reflexive-transitive closure

The reflexive-transitive closure, usually written R∗R^{*}, also includes every identity pair:

R∗=IX∪R+,IX={(x,x):x∈X}.R^{*}=I_X\cup R^{+}, \qquad I_X=\{(x,x):x\in X\}.

Equivalently, taking R0=IXR^0=I_X,

R∗=⋃k=0∞Rk.R^{*}=\bigcup_{k=0}^{\infty}R^k.

The distinction is whether zero steps are allowed:

  • R+R^{+} represents connection by one or more steps.
  • R∗R^{*} represents connection by zero or more steps.

A diagonal pair (x,x)(x,x) belongs to R+R^{+} only if there is a positive-length sequence returning to xx. It always belongs to R∗R^{*}.

Some texts and software use “transitive closure” for the reflexive-transitive version. Consequently, the treatment of diagonal pairs must be checked rather than inferred from the name alone.

Examples

Let

X={a,b,c,d},R={(a,b),(b,c),(c,d)}.X=\{a,b,c,d\}, \qquad R=\{(a,b),(b,c),(c,d)\}.

Then

R+={(a,b),(b,c),(c,d),(a,c),(b,d),(a,d)}.R^{+} = \{(a,b),(b,c),(c,d),(a,c),(b,d),(a,d)\}.

The three added pairs represent connections taking two or three steps. No diagonal pair is added.

For a cycle,

R={(a,b),(b,a)},R=\{(a,b),(b,a)\},

the transitive closure is

R+={(a,a),(a,b),(b,a),(b,b)}.R^{+} = \{(a,a),(a,b),(b,a),(b,b)\}.

Although the original relation has no identity pairs, each vertex can return to itself in two steps.

On the integers, let xRyxRy mean y=x+1y=x+1. Then xR+yxR^{+}y means x<yx<y, whereas xR∗yxR^{*}y means x≤yx\leq y.

Graph interpretation

A relation RR on XX can be regarded as a directed graph with vertex set XX and edge set RR. Its transitive closure records all ordered pairs connected by a directed walk of positive length. This interpretation connects the operation directly to graph theory.

For distinct vertices, any reachable pair has a path without repeated vertices. For a vertex to reach itself in positive length, a directed cycle is required. This distinction matters because some definitions reserve “path” for walks with no repeated vertices.

For a finite graph with n≥1n\geq 1 vertices,

R+=⋃k=1nRk.R^{+}=\bigcup_{k=1}^{n}R^k.

A connection between distinct vertices can be witnessed using at most n−1n-1 edges. A positive-length return to the starting vertex can be witnessed by a cycle of at most nn edges.

For a directed acyclic graph, the positive transitive closure contains no diagonal pairs and is a strict partial order. Adding the identity relation gives a partial order.

More generally, define mutual reachability by

x∼y⟺xR∗y and yR∗x.x\sim y \quad\Longleftrightarrow\quad xR^{*}y \text{ and } yR^{*}x.

This is an equivalence relation. Its classes are the graph’s strongly connected components. Collapsing each component to a single vertex produces an acyclic graph.

Matrix representation

For a finite graph, let AA be its Boolean adjacency matrix, with

Aij=1⟺(i,j)∈R.A_{ij}=1 \quad\Longleftrightarrow\quad (i,j)\in R.

Use Boolean matrix multiplication, in which logical AND replaces multiplication and logical OR replaces addition:

(B⊙C)ij=⋁k=1n(Bik∧Ckj).(B\odot C)_{ij} = \bigvee_{k=1}^{n} (B_{ik}\land C_{kj}).

Then the Boolean power A⊙kA^{\odot k} records whether a walk of length exactly kk exists. The transitive-closure matrix is

A+=A∨A⊙2∨⋯∨A⊙n,A^{+} = A\lor A^{\odot 2}\lor\cdots\lor A^{\odot n},

where OR is applied entrywise.

For reflexive-transitive closure, the Boolean identity matrix is included:

A∗=I∨A+.A^{*}=I\lor A^{+}.

This is an operation over Boolean algebra, not ordinary numerical matrix addition. With ordinary arithmetic, entries of AkA^k count walks of length kk; Boolean powers record only their existence.

Algorithms

Warshall’s algorithm

Warshall’s algorithm computes the closure by progressively allowing additional vertices as intermediate points.

Initialize a Boolean matrix TT with the adjacency matrix. For k=1,…,nk=1,\ldots,n, update all pairs i,ji,j by

Tij←Tij∨(Tik∧Tkj).T_{ij} \leftarrow T_{ij}\lor(T_{ik}\land T_{kj}).

The update records that ii can reach jj through kk whenever ii can reach kk and kk can reach jj. The intermediate-vertex loop over kk must be outermost in this standard formulation.

Initializing T=AT=A computes positive transitive closure. Initializing T=A∨IT=A\lor I computes reflexive-transitive closure.

Using asymptotic notation, the standard implementation takes O(n3)O(n^3) time and O(n2)O(n^2) space. Bit-vector implementations can accelerate the Boolean operations by processing multiple entries together.

Repeated graph searches

Another method runs a depth-first or breadth-first search from each vertex. With adjacency lists, the total running time is

O(n(n+m)),O\bigl(n(n+m)\bigr),

where mm is the number of edges. This approach is often suitable for sparse graphs.

For positive closure, the source vertex should be included in its own result only when a positive-length cycle returns to it. A search that automatically marks its source as reachable instead produces reflexive reachability unless this convention is handled separately.

Repeated squaring

Boolean matrix multiplication also gives a repeated-squaring method. Starting from B=I∨AB=I\lor A, repeatedly replace

B←B⊙B.B\leftarrow B\odot B.

Each squaring doubles the maximum walk length represented. After O(log⁡n)O(\log n) squarings, BB represents reflexive-transitive closure.

An explicitly stored closure can contain n2n^2 pairs even when the original graph has only O(n)O(n) edges. Thus producing the full relation can require quadratic output space, independently of the chosen algorithm.

Algebraic properties

On the collection of relations over a fixed set, transitive closure is a closure operator:

  • Extensive: R⊆R+R\subseteq R^{+}.
  • Monotone: if R⊆SR\subseteq S, then R+⊆S+R^{+}\subseteq S^{+}.
  • Idempotent: (R+)+=R+(R^{+})^{+}=R^{+}.

The last property is an instance of idempotence: applying the operation again adds nothing.

The closure can also be defined as the intersection of all transitive relations containing RR:

R+=⋂{T⊆X×X:R⊆T and T is transitive}.R^{+} = \bigcap \{T\subseteq X\times X: R\subseteq T \text{ and }T\text{ is transitive}\}.

This family is nonempty because X×XX\times X is transitive.

A further description uses a fixed point. With relation composition defined by

S∘T={(x,z):∃y, (x,y)∈S and (y,z)∈T},S\circ T = \{(x,z):\exists y,\ (x,y)\in S \text{ and }(y,z)\in T\},

the relation R+R^{+} is the least fixed point, under inclusion, of

F(S)=R∪(S∘R).F(S)=R\cup(S\circ R).

This formulation underlies recursive computations of reachability.

Applications and related operations

In databases, transitive closure expresses recursive queries such as finding all descendants in a hierarchy, all indirectly required components, or all destinations reachable through connecting routes.

In program analysis and formal verification, a transition relation describes individual execution steps. Its reflexive-transitive closure describes states reachable after any finite number of steps, including none. If the state space is infinite, an explicit closure need not be finitely representable or effectively computable.

In logic, reachability illustrates a limitation of first-order logic: no single ordinary first-order formula over the edge relation defines reachability on all finite directed graphs. Logics equipped with transitive-closure operators can express this unbounded iteration directly.

The transitive reduction addresses a complementary problem: removing edges while preserving reachability. For a finite directed acyclic graph, the reduction is unique and retains only edges not implied by longer paths. For general directed graphs, a reachability-preserving reduction need not be unique.

A separate use occurs in set theory. A transitive set is a set containing every element of each of its elements, and the transitive closure of a set is the least transitive set containing the original set as a subset. This concerns repeated membership rather than adding pairs to an arbitrary binary relation; the two constructions should not be conflated.