Transitive closure

Given that $R$ is a relation on a set $A$. The transitive closure of $R$ is the smallest transitive relation on $A$ containing $R$. We denote the transitive closure of $R$ by $\boxed {R^*}$.

If $R$ is already transitive, then $R^{\ast }=R$.

For example, given the following definition of $R$, we find $R^{\ast }$:

digraph A {
	label="R"
	x->y
	y->z
	z->w
	x->z
}
digraph B {
	label="R*"
	x->y
	y->z
	z->w
	x->z
	x->w
	y->w
}

Given $R$, we can define the transitive closure, $R^{\ast }$, recursively: ?

• Basis step: $R\subseteq R^{\ast }$ The pairs in $R$ are all in $R^{\ast }$.
• Recursive step: If $(a,b)\in R^{\ast }$ and $(b,c)\in R^{\ast }$ then $(a,c)\in R^{\ast }$. We add the missing pairs step by step.

Warshall’s algorithm

Warshall's algorithm

Algorithm

An algorithm is a finite sequence of precise step-by-step instructions.

Link to original

Warshall’s algorithm computes the matrix of the transitive closure $R^{\ast }$ of $R$. ?

• Given a relation $R$ on a set $A$ with $n$ elements, we begin with its $n\times n$ matrix. $\boxed{M_0}$
• There are $n$ rounds. For each, we mutate the matrix. $$M_0\stackrel{\text{round 1}}{⇝}{M}_1\stackrel{\text{round 2}}{⇝}{M}_2\stackrel{\text{round 3}}{⇝}...\stackrel{\text{round n}}{⇝}{M}_n$$ $\boxed{M_n}$ is the matrix of the transitive closure $R^{\ast }$ of $R$.
  • 1st rule: never change $1$ to $0$
  • 2nd rule: for the $k$ round, we select the $k$th row and the $k$th column, we look at all of the $0$ values not in this row or column. From the position of the $0$ value we are looking at, we check to see if the corresponding cells in the $k$th row and column are $1$, if they are, we change $0$ to $1$ otherwise we don’t do anything. $$\begin{array}{cc}& jk\text{th column}\\ \begin{array}{c}i\\ \\ k\text{th row}\end{array}& \left[\begin{array}{ccc}0& \to & 1\\ \downarrow & & \\ 1& & \end{array}\right]\end{array}\stackrel{\text{round }k}{⇝}\begin{array}{cc}& \begin{array}{ccc}j& & k\end{array}\\ \begin{array}{c}i\\ \\ k\end{array}& \left[\begin{array}{ccc}\text{1}& & 1\\ & & \\ 1& & \end{array}\right]\end{array}$$

Link to original

Example

Let $R$ be a relation on $\{a,b,d,d\}$. $R=\{(a,d),(b,a),(b,c),(c,a),(c,d),(d,c)\}$

We first construct our starting matrix.

$$M_0=\begin{array}{cc}& \begin{array}{cccc}a& b& c& d\end{array}\\ \begin{array}{c}a\\ b\\ c\\ d\end{array}& \left[\begin{array}{cccc}0& 0& 0& 1\\ 1& 0& 1& 0\\ 1& 0& 0& 1\\ 0& 0& 1& 0\end{array}\right]\end{array}$$

Round 1.

$$M_1=\begin{array}{cc}& \begin{array}{cccc}a& b& c& d\end{array}\\ \begin{array}{c}a\\ b\\ c\\ d\end{array}& \left[\begin{array}{cccc}0& 0& 0& 1\\ 1& 0& 1& \boxed{1}\\ 1& 0& 0& 1\\ 0& 0& 1& 0\end{array}\right]\end{array}$$

Round 2.

$$M_2=\begin{array}{cc}& \begin{array}{cccc}a& b& c& d\end{array}\\ \begin{array}{c}a\\ b\\ c\\ d\end{array}& \left[\begin{array}{cccc}0& 0& 0& 1\\ 1& 0& 1& 1\\ 1& 0& 0& 1\\ 0& 0& 1& 0\end{array}\right]\end{array}$$

Round 3.

$$M_3=\begin{array}{cc}& \begin{array}{cccc}a& b& c& d\end{array}\\ \begin{array}{c}a\\ b\\ c\\ d\end{array}& \left[\begin{array}{cccc}0& 0& 0& 1\\ 1& 0& 1& 1\\ 1& 0& 0& 1\\ \boxed{1}& 0& 1& \boxed{1}\end{array}\right]\end{array}$$

Round 4.

$$M_4=\begin{array}{cc}& \begin{array}{cccc}a& b& c& d\end{array}\\ \begin{array}{c}a\\ b\\ c\\ d\end{array}& \left[\begin{array}{cccc}\boxed{1}& 0& \boxed{1}& 1\\ 1& 0& 1& 1\\ 1& 0& \boxed{1}& 1\\ 1& 0& 1& 1\end{array}\right]\end{array}$$

Hence this is our final relation.

$$R^{\ast }=\{(a,a),(a,c),(a,d),(b,a),(b,c),(b,d),(c,a),(c,c),(c,d),(d,a),(d,c),(d,d)\}$$

digraph A {
	label = "R"
	a->d
	b->a
	b->c
	c->a
	c->d
	d->c
}
 
digraph B {
	label = "R*"
	a->a
	a->c
	a->d
	b->a
	b->c
	b->d
	c->a
	c->c
	c->d
	d->a
	d->c
	d->d
}