Page 1 of 4
QP CODE: 21103330 Reg No : .....................
Name : .....................
B.Sc/BCA DEGREE (CBCS) REGULAR / REAPPEARANCE EXAMINATIONS,
DECEMBER 2021
Second Semester
Complementary Course - MM2CMT03 - MATHEMATICS - DISCRETE MATHEMATICS
(II)
(Common for B.Sc Computer Science Model III, B.Sc Cyber Forensic Model III, Bachelor of
Computer Applications)
2017 ADMISSION ONWARDS
4FD925EA
Time: 3 Hours Max. Marks : 80
Part A
Answer any ten questions.
Each question carries 2 marks.
1. Show that the following graphs G and H are isomorphic
2. Define weakly connected graph.
3. Define Hamilton circuit.
4. Draw the subtrees with vertex 'b' as the root.
21103330
Page 1/4 Turn Over
Page 2 of 4
5. Find a Binary search tree for ' coconut , papaya , jackfruit , grapes ,orange
6. What is a ' Postorder ' traversal of a rooted tree ?
7. What is the value of Prefix expression ^ - * 3 3 * 4 2 5
8. Write the Distributive laws .
9. Check whether the following matrix is symmetric or not.
10. Define rank of a matrix.
11. Write the congugate of the matrix
12. Find the characteristic equation of the matrix
(10×2=20)
Part B
Answer any six questions.
Each question carries 5 marks.
13. Find the number of vertices, number of edges and the degree of each vertex in the given
graph and identify all isolated and pendant vertices.
14. Draw an undirected graph represented by the adjacency matricx
(a) (b)
15. Suppose that someone starts a chain letter .Each person who receives the letter is asked
to send it on to four other people . Some people do this , but others do not send any
letters .How many people have seen the letter including the first person , if no one
receives more than one letter and if the chain letter ends after there have been 100
people who read it but did not send it out ? how many people sent out the letter ?
⎛
⎝
⎜
1
5
4
5
3
2
4
2
7
⎞
⎠
⎟
( )
3i
2 + 5i
2
1 − i
( )
3
9
2
6
⎡
⎣
⎢
⎢
⎢
1
2
0
1
2
0
3
0
0
3
1
1
1
0
1
0
⎤
⎦
⎥
⎥
⎥
⎡
⎣
⎢
⎢
⎢
0
0
1
1
0
0
1
1
1
1
0
1
1
0
1
0
⎤
⎦
⎥
⎥
⎥
Page 2/4
Page 3 of 4
16. Define spanning tree of a connected graph. Find the spanning tree of the following graph
by explaining the procedure.
17. Find DFS spanning tree for the following graph starting from the vertex ' a '.
18. Use a table to express the following boolean functions
1 ) F ( x , y , z ) =
2 ) F ( x , y , z ) =
19. Find the sum of products expansion for the function F ( x , y , z ) =
20. Explain row canonical form and normal form of a matrix.
21. Check whether the following system is consistent or not.
(6×5=30)
Part C
Answer any two questions.
Each question carries 15 marks.
22. Draw graph models, stating the type of graph used, to represent airline routes where
every day there are four flights from Boston to Newark, two flights from Newark to Boston,
three flights from Newark to Miami, two flights from Miami to Newark, one flight from
Newark to Detroit, two flights from Detroit to Newark,three flights from Newark to
Washington, two flights from Washington to Newark, and one flight from Washington to
Miami, with (a) an edge between vertices representing cities that have a flight between
them.. (b) an edge between vertices representing cities for each flight that operates
between them.. (c) an edge between vertices representing cities for each flights that
operates between them plus a loop for a specal sightseeing trip that takes off and lands in
Miami.
x ̄y + y ̄z
(x + y)z ̄
(x + y)z ̄
x + 2y + 3z = 2
2x − 3y + 5z = 1
−x + y + 5z = 7
Page 3/4 Turn Over
Page 4 of 4
23. (a) Explain BFS spanning tree of a connected graph.
(b) Find BFS spanning tree of the following graph starting from the vertex ' a ' by
explaining steps.
24. Construct circuits that produce the following outputs 1 ) 2 )
25.
Find rank by row canonical form
(2×15=30)
(x + y)z ̄
(x + y + z)(x ̄y ̄z ̄)
⎛
⎝
⎜⎜⎜
1
4
6
8
2
3
9
5
3
5
1
0
4
4
0
2
⎞
⎠
⎟⎟⎟
Page 4/4