5E

C
81

4
67
Paper / Subject Code: 49372 / Discrete Structures & Graph Theory

62
7A
4A
25

DF

42
5E
92

C
81

67

62
7A
1T01873 - S.E. Computer Science & Engineering (Artificial Intelligence & Machine Learning) (R-2019)

1D

4A
25

DF

42
SEMESTER - III / 49372 - Discrete Structures & Graph Theory

5E
92
62

81

67
7A
1D

4A
42

5
QP CODE:10011566 DATE: 23/11/2022

22

F
5E
8D

AD
2

81
9
26

4A
25
04

E7
4

1
D
(3 Hours) [Total Marks : 80

92
CD

D
2

81

A5
6
8

A
1D
42

25
4
62

E7
0

14
8D

92
D

62
42

A5
8
C

1D
42

5
04
67

62
N.B.

14
D

92
CD

62
DF

2
1) Q.1 is compulsory.

58
8
4

1D
42
4
7

62
7A

22
0
2) Solve any 3 questions out of remaining 5 questions.

8D
D

62
DF

42

D9
5E

8
2C
3) Assumptions made should be clearly stated.

5
4
67
A

D4

22
D0
4A

21
26

om
4) Draw the figures wherever required.

D9
6
5E

8
D

C
81

74

2
4
62
7A

4
D0
A

21
25

8D
DF
4

42
Q.1 Solve any four of the following questions.

26
E
92

2C
81

4
A5

67
A
a) Prove using Mathematical Induction that n3+2n is divisible by 3 for all

D4
n >=1 5
1D

D0
5

26
7
2

F
4

6
E
2

48
D
62

2C
1

74

42
.c
9

A5
8

7A
D

D0
42

F6
b) Explain the following terms with suitable example: 5

26

8D
2
1

5E
8D

92

AD
2

2C
81

74
i) Partition set

04
6

A
42

25

F6
04

26
ns

CD
E7
ii) Power set.
1

14
D

2
CD

D
62

74
D9

A5
8
8

62
7A
2

F6
4
62

2
0

42
c) State the Pigeonhole principle and show that if any five numbers from 1 to 8 are chosen,

5E
D

2
CD

D
2

81
42

D9
6

67
8

7A
then two of them will add to 9. 5

4A
2

25
4
67

tio
62

DF
0

5E
8D

92
D

62

1
DF

58
C

7A
74

4A
42
04

d) Consider the function f(x) = 2x-3. Find a formula for the composition functions 5
62
7A

22
21
6

5E
D
CD

81
i) f2 = f o f
DF

D9
6
5E

8
4

4A
2

25
4

i
7

ii) f3 = f o f o f
62
A

D4
D0
4A

1
6

92
ttu
62
7

81
F

42
5E

48
AD

C
81

1D
42

25
67

0
4A

e) Explain the bipartite graph with suitable example. 5

25

26

8D

92
D

2
E7

26
92

2C
81

1D
4
A5

7
7A

D4
1D

D0
5

26

Q.2
62
22

F
en
14

48
AD
62

C
74

42
9

A5
8

2
1D

0
42

F6

8D

a) What is a transitive closure? Find the transitive closure of R using Warshall’s algorithm
D
E7
2

14

2
8D

92

D
2

2C
4

04
5
6

58

where A={1, 2, 3, 4, 5 } & R={(x,y) | x-y = ±1} 10

A
1D

A
2

6
04

26

CD
E7
4

22

DF
om 4
8D
CD

62

74
D9

5
58

62
7A
A

b) What is a ring? Let A= {0, 1, 2, 3, 4, 5, 6, 7}. Determine whether a set A with addition
42

F6
04

2
21

14

42
5E
D

2
CD

modulo 8 & multiplication modulo 8 is a commutative ring? Justify your answer. 10

D9
6

58

67
8

7A
4A
2
4
62

22

DF
0

21

5E
8D
D

81
42

Q.3
D9
26
C

7A
m

4A
5
4
67

D4

22
D0

1
6

5E
2

81
DF

9
26
8

a) A survey in 1986 asked households whether they had a VCR, a CD player or cable TV. 40 had
C
4

4A
25
4
67

62

4
D0

21

a VCR. 60 had a CD player; and 50 had cable TV. 25 owned VCR and CD player. 30 owned
D

92
st

81
DF

42

26
8
2C

1D

a CD player and had cable TV. 35 owned a VCR and had cable TV. 10 households had all
25
4
67
A

D4
0
26

92
CD

62
E7

three. How many households had at least one of the three? How many of them had only CD
F

48
AD

la 74

1D
42
A5

player? 8
2

0
F6

26

D
D

62
E7
14

8
AD

2C
74

42
4
A5

b) Find the complete solution of a recurrence relation 6

0
F6

26

8D
CD
E7
14

an +2an-1 = n+ 3 for n≥1 and with a0 =3

D

74

04
A5
8

62
7A
5

CD
22

DF
14

2
5E

c) Obtain CNF & DNF for the following expression: 6

D9

58

62
7A
4A

p ‹—› ( ̴ p V ̴ q)
22

DF
21

42
5E
1
D9

58

67
7A
4A
22

DF
21

5E
81
D9
6

7A
4A
2

25
D4

21

5E
92

81
26
48

1D

4A
25
D4
D0

11566 Page 1 of 3
92
62

81
48

1D
42

25
D0

D048D42621D9225814A5E7ADF674262C
8D

92
62
 5E

C
81

4
67
Paper / Subject Code: 49372 / Discrete Structures & Graph Theory

62
7A
4A
25

DF

42
5E
92

C
81

67

62
7A
QP CODE:10011566

1D

4A
25

DF

42
5E
92
62

81
Q.4

67
7A
1D

4A
42

5
22

F
5E
8D

AD
2

81
9
26
a) What is a group? Let A={3, 6 ,9, 12} 10

4A
25
04

E7
4

1
D
i) Prepare the composition table w.r.t. the operation of multiplication modulo 15.

92
CD

D
2

81

A5
6
8

A
1D
42

25
ii) Whether it is an abelian group? Justify your answer.

4
62

E7
0

14
8D

92
D

62
iii) Find the inverses of all the elements.

42

A5
8
C

1D
42

5
04
67

62
iv) Whether it is a cyclic group?

14
D

92
CD

62
DF

58
8
4

1D
42
4
7

62
7A

22
0
b) What are the isomorphic graphs? Determine whether following graphs are isomorphic. 10

8D
D

62
DF

42

D9
5E

8
2C

5
4
67
A

D4

22
D0
4A

21
26

om
7

D9
6
5E

8
D

C
81

74

2
4
62
7A

4
D0
A

21
25

8D
DF
4

42

26
E
92

2C
81

4
A5

67
A

D4
1D

D0
5

26
7
2

F
4

6
E
2

48
D
62

2C
1

74

42
.c
9

A5
8

7A
D

D0
42

F6

26

8D
2
1

5E
8D

92

AD
2

2C
81

74

04
6

A
Q.5
42

25

F6
04

26
ns

CD
E7
1

14
D

2
CD

D
62

74
D9

A5
8
8

62
7A
2

a) Let X={1, 2, 3, 6, 24, 36} & R ={(x,y) ∈ R | x divides y}

5

F6
4
62

10
4

2
0

42
5E
D

2
CD

D
2

81
42

D9
6

i) Write the pairs in a relation set R.

67
8

7A
4A
2

25
4
67

tio
62

DF
0

ii) Construct the Hasse diagram.

5E
8D

92
D

62

1
DF

58
C

7A
74

iii) What are the Maximal and Minimal elements?

D

4A
42
04
62
7A

22
21
6

5E
D

iv) Mention Chains and Ant chains from above set.

CD

81
DF

D9
6
5E

8
4

4A
2

25
4

v) Is this poset a lattice?

i
7

62
A

D4
D0
4A

1
6

92
ttu
62
7

81
F

42
5E

48
AD

C
81

1D
42

25
67

b) Define the term bijective function. 5

0
4A
25

26

8D

92
D

2
E7

26
92

2C
81

1D
4
A5

7
7A

D4
1D

D0
5

26

62
22

F
en
14

48

Whether a function is bijective? Justify your answer.

AD
62

C
74

42
9

A5
8

2
1D

0
42

F6

8D
D
E7
2

14

2
8D

92

D
2

2C
4

c) Define minimum hamming distance. Consider e : B3→B6. Find the code words generated by
04
5
6

58

7
A
1D

A
2

6
04

26

CD
E7

the parity check matrix H given below. 5

4

22

DF
om 4
8D
CD

62

74
D9

5
58

62
7A
A
42

F6
04

2
21

14

42

111
5E
D

2
CD

D
D9
6

58

67
8

7A

110
4A
2
4
62

22

DF
0

21

5E
8D

H= 0 1 1
D

81
42

D9
26
C

7A
m

4A
5
4

100
67

D4

22
D0

1
6

5E
2

81
DF

010
9
26
8
C
4

4A
25
4
67

62

001
4
D0

21
D

92
st

81
DF

42

26
8
2C

1D

25
4
67
A

D4
0

Q.6
26

92
CD

62
E7

48
AD

la 74

1D
42
A5

0
F6

26

a) Define with example Euler path, Euler circuit, Hamiltonian path, and Hamiltonian circuit.
D

62
E7
14

8
AD

2C
74

42
4
A5

Determine if the following diagram has Euler circuit and Hamiltonian circuit. Mention the
0
F6

26

8D
CD
E7

path/circuit. 6
14

74

04
A5
8

62
7A
5

CD
22

DF
14

2
5E

4
D9

58

62
7A
4A

6
22

DF
21

42
5E
1
D9

58

67
7A
4A
22

DF
21

5E
81
D9
6

7A
4A
2

25
D4

21

5E
92

81
26
48

1D

4A
25
D4
D0

11566 Page 2 of 3
92
62

81
48

1D
42

25
D0

D048D42621D9225814A5E7ADF674262C
8D

92
62
 D0 21 14 DF CD
48 D9 A5 67 04
D4 22 E7 42 8D
2 6 5 8 A 62 42
D0 21 14 DF CD 62
48 D9 A5 67 04 1D
D4 22 E7 4 2 8D 92
26 58 6 2 4 25
21 14
AD
F C D 2 6 81
A5 67 0 2 1D 4A
D9 4

i)
8D 8

ii)
9

11566
42

iv)
22 D

iii)
42 E7 22 5E
58 AD 62 42 5 7A
62
1D 14A F6 C D0 62 81 DF
92 5E 74 4 1D 4A 67
25 7A 26 8D 92 5E 42
D 4 2 2 5 7 A
62
1D
81
4A F6
la 2C
D0 621 8 14 DF
62
CD
92 5E 74
26 4 8 D9 A5 6 74 04
25 7A 2 D4 22 E7 2 8D
81 DF CD 26 58 AD 62 42
4A
st
5E 674 0 4
m 21 14 F 6
CD
0
62
92
25 26 8 D
D9
2
A5
E 7 4 4 8
1D
81
7A 2C 426 258 7A 2 62 D 92
25
DF D 2 1 D C 42
4A 67 0 1 4 A F D 62 81
5E 4 2 48 D9 5 67 0 4 1 D 4A
7A 62 D4 22 E7 42 8 D 9 2 5E
om
DF CD 26
21
58
14
AD 62
CD 4 2 2 5 7A
67 04 D A F 6
62
1
81
4 DF
42
62 8 D 9 22 5 E7 7 4 04
8D D A 67
42 5 26 92 5E 42
CD 62 81 A D 2 C 4 2 2 5 7A 62
04 1D 4A F6 6 2 8 1
D0 1 4 DF CD
en
4 6
r denote the statement ‘The rating is 3 star.’

8D 92 5E 74 8 D9 A5 7 04
42 25 7A 26 D 2 E 4 2 8D
The food is good but service is not good.
b) Let p denote the statement ‘The food is good’,
q denote the statement ‘The service is good’ &

62 81 2C 42 25 7A 62 42
DF D 62 81 D C

Page 3 of 3
1D 4A 6 0 1 4 F D 62
7
c) Find out the incidence matrix of following graphs.

4 0
Write the following statements in a symbolic form-

92 5E 48 67
Either food is good or service is good or both.

A5 4 1D
ttu D9
25 7A 2 6 D4 2 2 E 42 8 D
81 D 2 C 2 5 7 A 62 4
92

_________________
4A F6 D0 i 6 21 8 14 DF CD 26 25
81
5E 74 4 8D D A 6 04 21D
7A 26 92 5E 74 8D 92
26
If both food & service are good then the rating is 3 star.

2C 42 25 7A
tio 42 25

D048D42621D9225814A5E7ADF674262C
DF D 0
62
1
81
4 D F
2C
D 6 81
67 48 67 0 2 1 4A
42 D9 A5
42 48 D9
62 D4
26
22
58
E7
62 D 22 5E
CD
2 1
AD C 42 5
ns
04 1D 4A F6 D0 62 81
8D 92 5E 74 4 1D 4A
42 25 7A
.c 26 8D 92 5E
62 81 D 2C 42 25 7A
D
It is not true that a 3 star rating always means good food & good service.

1D 4A F6 D0 62 81
Paper / Subject Code: 49372 / Discrete Structures & Graph Theory

5E 74 4 1D 4A
92
25 7A 26 8D4 92 5E
D 2C 2 25 7A
QP CODE:10011566

81
om 62 81
4A F6 D0 1D 4A DF
5E 74 48D 67
7A 26
4
92
2
5E 4
DF 2C 2 6 58
7A
6

D0 21 14 DF
8

67 48 D9 A5 67
42 D4 22 E7 42
62 58 62
CD 26 AD C
04 21 14 F
8D D9 A5 67
22 E7 42
42
6 5 8 A D
62
C