North Maharashtra University 2008 B.Sc Mathematics S.YBSc MTH – 212 (B) (Computational Algebra) -university question paper

only if a and b belong to identical set in P”. Prove that R is an equivalence
relation on A.
7) discuss Warshall’s algoritham. Using Warshall’s algoritham obtain the
transitive closure of a relation R whose matrix is MR =
? ? ? ?
?
? ? ?
?
?
0 one 0
1 one 0
1 0 0
.
8) Using Warshall’s algoritham obtain the transitive closure of a relation R
whose matrix is MR =
? ? ? ?
?
?
? ? ? ?
?
?
1 0 0 1
0 one 1 0
0 one 1 0
1 0 0 1
9) Using Warshall’s algoritham obtain the transitive closure of a relation R
whose matrix is MR =
? ? ? ?
?
?
? ? ? ?
?
?
1 one 0 1
0 one 1 0
0 one 1 0
1 0 0 1
10) calculate W1, W2, W3 as in Warshall’s algoritham for the relation R on
a set A = {1, 2, 3, 4, 5}and matrix of R is MR =
? ? ? ? ? ?
?
?
? ? ? ? ? ?
?
?
0 one 0 0 1
1 0 0 0 0
0 0 0 one 1
0 one 0 0 0
1 0 0 one 0
=
W0.
6
11) Let A = {1, 2, 3} and R = {(1 , 1) , (1 , 2) , (2 , 3) , (1 , 3) , (3 , 1) , (3 ,
2)}. obtain the matrix R8
M using the formula R8
M = MR ? (MR)2
? (MR)3.
12) Let A = {a, b, c} and R = {(a , a) , (b , b) , (b , c) , (c , b) , (c , c)}.
obtain the matrix R8
M using the formula R8
M = MR ? (MR)2 ?
(MR)3.
13) Let A = {1, 2, 3} and B = {a, b, c, d, e, f}and R = {(1 , a) , (1 , c) , (2 ,
d) , (2 , e) , (2 , f) , (3 , b)}. Let X = {1, 2} , Y = {2, 3}. Show that
R(X ? Y) = R(X) ? R(Y) and R(X n Y) = R(X) n R(Y).
14) Let A = {1, 2, 3, 4, 5} and R = {(1 , 1) , (1 , 2) , (2 , 3) , (3 , 5) , (3 , 4)
, (4 , 5)}. calculate R2 , R8 and draw diagraph for R2.
15) Let A = {x, y, z, w, t} and R = {(x , y) , (x , w) , (y , t) , (z , x) , (z , t) ,
(t , w)}. calculate R2 , R8 and draw diagraph for R2.
16) Let A = {1, 2, 3, 4, 5, 6, 7} and R = {(1 , 2) , (1 , 4) , (2 , 3) , (2 , 5) ,
(3 , 6) , (4 , 7)} be a relation on A. obtain i) R-relative set of four ii) Rrelative
set of two iii) restriction of R to B, where B = {2, 3, 4, 5}.
17) Determine the partitions A/R for the subsequent equivalence relations
on A
i) A = {1, 2, 3, 4} and R = {(1 , 1) , (1 , 2) , (2 , 1) , (2 , 2) ,
(1 , 3) , (3 , 1) , (3 , 3) , (4 , 1) , (4 , 4)}.
ii) S = {1, 2, 3, 4}and A = S × S and R be a relation on A
described by (a , b)R(c , d) ? ad = bc.
18) Let A = {1, 2, 3, 4}and R be a relation on A whose matrix is MR =
? ? ? ?
?
?
? ? ? ?
?
?
0 one 0 0
0 one 1 0
1 one 1 0
0 0 0 0
. obtain the reflexive closure of R and symmetric closure
of R.
7
19) Let A = {1, 2, 3, 4}and R be a relation on A whose matrix is MR =
? ? ? ?
?
?
? ? ? ?
?
?
1 0 one 1
1 0 0 1
0 0 0 1
1 one 1 1
. obtain the reflexive closure of R and symmetric closure
of R.
20) Let R, S be relations from A = {1, 2, 3} to B = {1, 2, 3, 4} whose
matrices are MR =
? ? ?
?
?
? ? ?
?
?
1 one 1 0
0 0 0 1
1 one 0 1
and MS =
? ? ?
?
?
? ? ?
?
?
1 one 0 0
1 0 0 1
0 one 1 0
. obtain
i)
R
M ii)
S
M iii) R S M ?
21) Let R, S be relations from A = {1, 2, 3, 4} to B = {1, 2, 3} whose
matrices are MR =
? ? ? ?
?
?
? ? ? ?
?
?
1 0 1
0 one 0
0 one 1
1 0 1
and MS =
? ? ? ?
?
?
? ? ? ?
?
?
1 one 1
1 0 1
1 0 1
0 one 0
. obtain
i) R 1
M - ii) S 1
M - iii) (R S) 1
M ? -
.
22) Using Warshall’s algoritham , obtain the transitive closure of relation R
on a set A = {1, 2, 3, 4} provided by diagraph :
23) Using Warshall’s algoritham , obtain the transitive closure of relation R
on a set A = {a, b, c, d} provided by diagraph :
1 2
4 3
8
24) Let R be a relation whose diagraph is provided beneath :
i) List all paths of length two starting from vertex 2.
ii) obtain a cycle starting at vertex 2.
iii) Draw diagraph of R2.
25) Let R be a relation whose diagraph is provided beneath :
2 3
1
4
5
6
a b
d c
9
iv) List all paths of length three starting from vertex 3.
v) obtain a cycle starting at vertex 6.
vi) obtain R3

Earning:   Approval pending.