Adv Discrete Mathematics-I

Course: M.A.M.Sc. Code: MN-445 Branch: Maths Year: 2023

Download Original PDF

Get the official Barkatullah University print version scanned document.

Download/Print

🤝 Help Your Juniors!

Have previous year question papers that aren't on our website? Help the next batch of students by sending them to us! With your consent, we will proudly feature your name as a Top Contributor on our platform.

Submit Papers 📩

Roll No. .....................................

1.
Choose the correct answer :

Total No. of Questions : 11

[Total No. of Printed Pages : 10

(i) (R− {1}, *), Where binary operation * is defined by

a * b = a + b − ab is on :

  1. Cyclic group
  2. Monoid
  3. Abelian group
  4. None of these

(ii) In Boolean Algebra (B, +, *, 0, 1) the dual of a (b + 1)

is:

  1. a . (a + b-1)
  2. a (a + b + 1)
  3. a (a + b . 0)
  4. None of these

MN-445

M.A./M.Sc. Ist Semester (Reg./Pvt./ATKT)

Examination, 2023-24

Maths

Paper - V (i)

Adv. Discrete Mathematics-I

(iii) A homomorphism g from (G, *) onto (G', ∆) with kernel

k is an isomorphism iff:

  1. k ≠ {e}
  2. k = {e}

Time : 3 Hours]

[Maximum Marks : Reg. 85

Pvt. 100

Note :- Attempt all questions. All questions are compulsory.

SECTION - 'A'

Objective Type Questions

MN-445

(1)

P.T.O.

MN-445

(2)

  1. k = 0
  2. k = 1

(iv) If (T, *, ⊕) is lattice and if S ⊆ T, then (S, *, ⊕) is

sublattice of (T, *, ⊕) iff:

  1. S is associative under the operation (*)
  2. S is closed under operation (*) and ⊕
  3. S is closed under the operation ⊕
  4. None of these

(v) "Every function without constant of a Boolean algebra

is equal to a function in disjunctive mormal form" is

statement of:

  1. Expression Theorem
  2. Bool's Expansion Theorem
  3. Kuratowski's Theorem
  4. None of these

(vii) Two graphs are called isomorphic if :

  1. They have same number of edges
  2. They have same number of vertex
  3. They have equal no. of vertices with given degree
  4. All of above

(viii) Every cut set in connected graph G contains atleast

.............. branch of every spanning tree of G

  1. one
  2. two
  3. three
  4. four

(vi) Total degrees of an isolated vertex is :

  1. 1

(ix) A graph is a tree iff it is...............

  1. Strongly Connect
  2. Not Connect

MN-445

(3)

P.T.O.

MN-445

(4)

  1. Minimally Connect
  2. None of these

(x) The maximum height of Binary Tree is :

  1. max lmax = (n+1)/2
  2. max lmax = (n-2)/2
  3. max lmax = (n-1)/2
  4. None of these

that gof : S → V is a semigroup homomorphism from <S, *>

to <V, ∆>.

SECTION - 'B'

Short Answer Type Questions

2.
Let (M, *, e) and <T, ∆, e> be two monoids with identities e and e'. If f is an onto mapping from M to T, i.e f : M → T is an isomorphism, then prove that f(e) = e'.

OR

Support <S, ⊗>, <T, ∆> and <V, ∆> be semi groups f : S → T and g : T → V be semi group homomorphism, then show
3.
Show that dual of a lattie is a Lattice.

OR

Let (L, ≤) be a Lattice and let ∧ and ∨ denote the operations of meet and join in L, then show that for any a, b ∈ L.
  1. a ≤ b ⇔ a ∧ b = a
  2. a ≤ b ⇔ a ∨ b = b
4.
Replace the following switching circuit by a simpler one.
Diagram for Question

OR

Express the following function in to disjunctive normal form. f(x, y, z) = (x + y + z) . (xy + x'z')
5.
Prove that A graph is a tree iff there is one and only one path between every pair of vertices.

MN-445

(5)

P.T.O.

MN-445

(6)

OR

Explain Bipartite graph with example. Show that the graph in following figure is complete bipartite graph.
Diagram for Question
7.
Let g be a homomorphism of <G, *> onto <G', ∆> with kernel k, then show that <G/k> is isomorphic to <G', ∆>.

OR

Show that the semi group (E, *) and (Z, *) are isomorphic where E = collection of Even integer and z = collection of odd integer.
8.
Define bounded lattice and if (L, ≤) is a lattice and a, b ∈ L, then prove that.
  1. a ∧ (b ∨ c) ≥ (a ∧ b) ∨ (a ∧ c)
  2. a ∨ (b ∧ c) ≤ (a ∨ b) ∧ (a ∨ c)

OR

Prove that in a distributive lattice. If an element has a complement, then this complement then this complement is unique.
6.
Define Binary and spanning tree with example.

OR

Prove that every connected graph has at least one spanning tree.

SECTION - 'C'

Long Answer Type Questions

9.
Let B = {1, 2, 5, 7, 10, 14, 35, 70} for any a, b in B define +, * and' as follows

a + b = lcm (a, b), a * b = gcd (a, b) & then a' = 70/a then show

MN-445

(7)

P.T.O.

MN-445

(8)

that B is boolean algebra with 1 as zero element and 70 as unit element.

OR

Prove that, the order relation ≤ is partial order relation in a boolean algebra.
  1. Cut set and its properties
  2. Euler graph and path
  3. Planar graph
10.
Prove that the maximum number of edges in a simple graph

with n vertices is n(n-1)/2

OR

Explain dijekstra Algorithm and its application.
11.
Let G be a connected planner graph with V vertices and edges and let r be the number of regions in a planar representation of • G, then show that

V = e + r = 2

OR

Explain the following with example and also draw if needed.
  1. Isolated vertex and pandant vertex

MN-445

(9)

P.T.O.