9.4 Closure Of Relations

Question 1

Closure of relation:

Answer 1

If R is a relation on a set A, then the closure of R with respect to P, if it exists, is the relation
S on A with property P that contains R and
is a subset of every subset of A × A containing R
with property P.

Question 2

Reflexive Closure:

Answer 2

given a relation R on a set A, the reflexive closure of R can be formed by adding to R all pairs of the form (a, a) with a ∈ A, not already in R.

The addition of these pairs produces a new relation that is reflexive, contains R, and is contained within
any reflexive relation containing R.

We see that the reflexive closure of R equals R ∪ Δ, where
Δ={(a, a) ∣ a ∈ A} is the diagonal relation on A.

Question 3

suppose that relations S and T both have property P and are subsets of
every relation with property P that contains R.
How are S and T related?

Answer 3

If there is a relation S that is a subset of every relation containing R with property P, it must
be unique. To see this, suppose that relations S and T both have property P and are subsets of
every relation with property P that contains R. Then, S and T are subsets of each other, and so
are equal. Such a relation, if it exists, is the smallest relation with property P that contains R
because it is a subset of every relation with property P that contains R.

Question 4

Symmetric Closure:

Answer 4

The symmetric closure of a relation R can be constructed by adding all ordered pairs of the form (b,a), where (a, b) is in the relation, that are not already
present in R.
Adding these pairs produces a relation that is symmetric, that contains R, and
that is contained in any symmetric relation that contains R.

The symmetric closure of a relation can be constructed by taking the union of a relation with its inverse i,e,
R ∪ R^−1 is the symmetric closure of R, where
R^−1 = {(b, a) ∣ (a, b) ∈ R}.

Question 5

Definition of path:
How to denote it?
What about its length?
Whats a circuit?
any rules?

DOUBT !!!!

We view the empty set of edges as a path of length zero from a to a.

Answer 5

A path from a to b in the directed graph G is a sequence of edges (x0, x1), (x1, x2),
(x2, x3), … , (xn−1, xn) in G, where n is a nonnegative integer, and x0 = a and xn = b, that
is, a sequence of edges where
the terminal vertex of an edge is the same as the initial vertex
in the next edge in the path.

This path is denoted by x0, x1, x2, … , xn−1, xn and has length n.
We view the empty set of edges as a path of length zero from a to a.

A path of length n ≥ 1
that begins and ends at the same vertex is called a circuit or cycle.

A path in a directed graph can pass through a vertex more than once. Moreover, an edge in
a directed graph can occur more than once in a path.

Question 6

Paths and relations.

The theorem.

Answer 6

The term path also applies to relations. Carrying over the definition from directed graphs to
relations, there is a path from a to b in R if there is a sequence of elements a, x1, x2, … , xn−1, b
with (a, x1) ∈ R, (x1, x2) ∈ R, … , and (xn−1, b) ∈ R.

THEOREM :Let R be a relation on a set A. There is a path of length n, where n is a positive integer, from
a to b if and only if (a, b) ∈ R^n.

Question 7

Connectivity Relation:

connectivity relation and powers of relation:

Answer 7

Let R be a relation on a set A. The connectivity relation R∗ consists of the pairs (a, b) such
that there is a path of length at least one from a to b in R.

Because R^n consists of the pairs (a, b) such that there is a path of length n from a to b, it follows
that R∗ is the union of all the sets R^n. In other words,
R∗ = ⋃(^∞)(v n=1) R^n

Question 8

Transitive Closure:

Answer 8

The transitive closure of a relation R equals the connectivity relation R∗.

prove it

Now note that if R ⊆ S, then R∗ ⊆ S∗, because any
path in R is also a path in S.

Question 9

Lemma:

If there’s a path in elements then comment about its length:

Answer 9

Let A be a set with n elements, and let R be a relation on A. If there is a path of length at least
one in R from a to b, then there is such a path with length not exceeding n. Moreover, when
a ≠ b, if there is a path of length at least one in R from a to b, then there is such a path with
length not exceeding n − 1.

prove it.

Question 10

Can transitive closure be shrunk?

Answer 10

From Lemma 1, we see that the transitive closure of R is the union of R, R2, R3, … , and Rn.

This follows because there is a path in R∗ between two vertices if and only if there is a path
between these vertices in Ri,
for some positive integer i with i ≤ n. Because

R∗ = R ∪ R2 ∪ R3 ∪ ⋯ ∪ Rn

Question 11

Matrix for transitive closure:

Answer 11

Let MR be the zero–one matrix of the relation R on a set with n elements. Then the zero–one
matrix of the transitive closure R∗ is

MR∗ = MR ∨ M[2]R ∨ M[3]R ∨ ⋯ ∨ M[n]R .

the zero-one matrix for the transitive closure is the join of the zero–one matrices
of the first n powers of the zero-one matrix of R.

Question 12

ALGORITHM 1 A Procedure for Computing the Transitive Closure.

Answer 12

procedure transitive closure (MR : zero–one n × n matrix)
A := MR
B := A
for i := 2 to n
A := A ⊙ MR
B := B ∨ A
return B{B is the zero–one matrix for R∗}

Question 13

The number of bit operation in prev card?

Doubt!!

Answer 13

Computing the Boolean powers requires that
n−1 Boolean products of n × n zero–one matrices be found.
Each of these Boolean products found using
(n^2)(2n−1) bit operations.
Hence, these products can be computed using
(n^2)(2n−1)(n−1) bit operations.

To find MR∗ from the n Boolean powers of MR, n−1 joins of zero–one matrices need
to be found. Computing each of these joins uses n2 bit operations. Hence, (n−1)n2 bit operations are used in this part of the computation. Therefore, when Algorithm 1 is used, the
matrix of the transitive closure of a relation on a set with n elements can be found using
(n^2)(2n−1)(n−1) + (n−1)(n^2) = 2(n^3)(n−1), which is
O(n^4) bit operations.

Question 14

Prove:
Let R be a relation on a set A. There is a path of length n, where n is a positive integer, from
a to b if and only if (a, b) ∈ R^n.

Answer 14

We will use mathematical induction. By definition, there is a path from a to b of length
one if and only if (a, b) ∈ R, so the theorem is true when n = 1.
Assume that the theorem is true for the positive integer n. This is the inductive hypothesis.
There is a path of length n + 1 from a to b if and only if there is an element c ∈ A such that
there is a path of length one from a to c, so (a, c) ∈ R, and a path of length n from c to b, that
is, (c, b) ∈ R^n. Consequently, by the inductive hypothesis, there is a path of length n + 1 from
a to b if and only if there is an element c with (a, c) ∈ R and (c, b) ∈ R^n. But there is such an
element if and only if (a, b) ∈ R^(n+1). Therefore, there is a path of length n + 1 from a to b if and
only if (a, b) ∈ Rn+1. This completes the proof.

Question 15

Interior Vertices:

Answer 15

The concept of the interior vertices of a path is used in Warshall’s
algorithm. If a, x1, x2, … , xm−1, b is a path, its interior vertices are x1, x2, … , xm−1, that is,
all the vertices of the path that occur somewhere other than as the first and last vertices
in the path.

Question 16

DOUBTTTT

WArshal’s Algo theory :

Answer 16

Warshall’s algorithm is based on the construction of a sequence of zero–one matrices. These
matrices are W0, W1, … , Wn, where W0 = MR is the zero–one matrix of this relation, and Wk =
[w(k)
ij ], where w(k)
ij = 1 if there is a path from vi to vj such that all the interior vertices of this path
are in the set {v1, v2, … , vk} (the first k vertices in the list) and is 0 otherwise. (The first and last
vertices in the path may be outside the set of the first k vertices in the list.) Note that Wn = MR∗ ,
because the (i, j)th entry of MR∗ is 1 if and only if there is a path from vi to vj
, with all interior vertices in the set {v1, v2, … , vn} (but these are the only vertices in the directed graph). Example
8 illustrates what the matrix Wk represents

Question 17

Lemma 2:

about getting Wk from Wki1

Answer 17

Let Wk = [w[k]
ij ] be the zero–one matrix that has a 1 in its (i, j)th position if and only if there
is a path from vi to vj with interior vertices from the set {v1, v2, … , vk}. Then
W[k]ij = W [k−1] ij ∨ (W [k−1] ik ∧ W [k−1] kj ),
whenever i, j, and k are positive integers not exceeding n.

Look at theory.

Question 18

ALGORITHM 2 Warshall Algorithm.

Answer 18

procedure Warshall (MR : n × n zero–one matrix)
W := MR
for k := 1 to n
    for i := 1 to n
        for j := 1 to n
            wij := wij ∨ (wik ∧ wkj)
return W{W = [wij] is MR∗ }

Question 19

Algo WArshall bit operations:

Answer 19

2n^3

The computational complexity of Warshall’s algorithm can easily be computed in terms of
bit operations. To find the entry w[k]
ij from the entries w[k−1]
ij , w[k−1]
ik , and w[k−1]
kj using Lemma
2 requires two bit operations. To find all n2 entries of Wk from those of Wk−1 requires 2n2
bit operations. Because Warshall’s algorithm begins with W0 = MR and computes the sequence of n zero–one matrices W1, W2, … , Wn = MR∗ , the total number of bit operations used
is n ⋅ 2n2 = 2n3.