Define Reflexive closure, Symmetric closure along with a suitable example. Let R be a relation on

Set S= {a, b, c, d, e), given as

R = {(a, a),(a, d), (b, b) , (c, d) , (c, e) , (d, a), (e, b), (e, e)}

Find transitive closure using Warshall's Algorithm.

Mumbai University > Computer Engineering > Sem 3 > Discrete Structures

Marks: 8 Marks

Year: May 2015

Reflexive closure:

The reflexive closure of a binary relation R on a set X is the smallest reflexive relation on X that contains R. For example, if X is a set of distinct numbers and x R y means "x is less than y", then the reflexive closure of R is the relation "x is less than or equal to y".

Symmetric closure:

The symmetric closure of a binary relation R on a set X is the smallest symmetric relation on X that contains R. For example, if X is a set of airports and xRy means "there is a direct flight from airport x to airport y", then the symmetric closure of R is the relation "there is a direct flight either from x to y or from y to x". Or, if X is the set of humans (alive or dead) and R is the relation 'parent of', then the symmetric closure of R is the relation "x is a parent or a child of y".

Let $M_R$ denotes the matrix representation of R. Take $W_0=M_R,$ We have

$W_0=M_R=\begin{pmatrix}1&0&0&1 \\ 0&1&1&0 \\ 0&1&1&0 \\ 1&0&0&1 \end{pmatrix}$ and $n=4$ (As $M_R$ is a $4 \times 4$ matrix)

We compute $W_4$ by using warshall's algorithm.

For k=1. In column 1 of $W_0$, ‘1’ is at position 1, 4. Hence $p_1=1, p_2=4$.

In row 1 of $W_0$ ‘1’ is at position 1, 4. Hence $q_1=1, q_2=4$.

Therefore, to obtain $W_1$, we put ‘1’ at the position:

$\{(p_1, q_1), (p_1, q_2), (p_2, q_1), (p_2, q_2)=(1, 1), (1, 4), (4, 1), (4 4)\}$. Thus,

$W_1=\begin{bmatrix}1&0&0&1 \\ 0&0&1&1 \\ 1&0&1&1 \\ 0&0&0&1 \end{bmatrix}$

For k=2. In column 2 of $W_1$, ‘1’ is at position 2, 3. Hence $p_1=2, p_2=3$.

In row 2 of $W_1$ ‘1’ is at position 2, 3. Hence $q_1=2, q_2=3$.

Therefore, to obtain $W_2$, we put ‘1’ at the position:

$\{(p_1, q_1), (p_1, q_2), (p_2, q_1), (p_2, q_2)=(2, 2), (2, 3), (3, 2), (3, 3)\}$. Thus,

$W_2=\begin{bmatrix}1&0&0&1 \\ 0&0&1&1 \\ 1&0&1&1 \\ 0&0&0&1 \end{bmatrix}$

For k=3. In column 3 of $W_2$, ‘1’ is at position 2, 3. Hence $p_1=2, p_2=3$.

In row 3 of $W_2$ ‘1’ is at position 2, 3. Hence $q_1=2, q_2=3$.

Therefore, to obtain $W_3$, we put ‘1’ at the position:

$\{(p_1, q_1), (p_1, q_2), (p_2, q_1), (p_2, q_2)=(2, 2), (2, 3), (3, 2), (3, 3)\}$. Thus,

$W_3=\begin{bmatrix}1&0&0&1 \\ 0&0&1&1 \\ 1&0&1&1 \\ 0&0&0&1\end{bmatrix}$

For k=4. In column 4 of $W_3$, ‘1’ is at position 1, 4. Hence $p_1=1, p_2=4$.

In row 4 of $W_3$ ‘1’ is at position 1, 4. Hence $q_1=1, q_2=4$.

Therefore, to obtain $W_3$, we put ‘1’ at the position:

$\{(p_1, q_1), (p_1, q_2), (p_2, q_1), (p_2, q_2)=(1, 1), (1, 4), (4, 1), (4 4)\}$. Thus,

$W_4=\begin{bmatrix}1&0&0&1 \\ 0&0&1&1 \\ 1&0&1&1 \\ 0&0&0&1 \end{bmatrix}$

Thus, the transitive clousure of R is given as

R= {(1, 1), (1, 4), (2, 2), (2, 3), (3, 2), (3, 3), (4, 1), (4, 4)}