**IGNOU MCA MCS-033 3rd semester term-end examination (**

**ADVANCED DISCRETE**

**MATHEMATICS) books/block,term-end exam notes,upcoming guess paper,important questions,study materials,previous year papers download.**

**IGNOU BCA/MCA all semester new revised (1st semester,2nd semester,3rd semester,4th**

**semester,5th semester and 6th semester) solved assignments,term-end exam notes,study materials,important**

**questions,books/blocks (June-December) free download.**

**Notes-1**

they are homogeneous or non-homogeneous.

(b) Define :

(i) Simple graph

(ii) Finite and infinite graph

(iii) Isolated vertex

(iv) Subgraph

(c) Solve the recurrence relation.

(d) Find the generating function of the following

(e) Find the chromatic number of the given graph.

(f) How many edges are there in a graph with 10 vertices each of degree 6 ?

2. (a) Solve the recurrence relation

3. (a) Find the solution to the recurrence relation

(b) Define Isomorphism of two graphs. Find whether the given graphs are isomorphic or not.

4. (a) Find Euler's path in the graph given below :

(b) Show that k4 is planar graph.

(c) Solve the recurrence relation

5. (a) Solve the recurrence relation

the method of generating function.

(b) State and prove Hand Shaking Theorem.

**Notes-2**

1. (a) Explain divide and conquer relations with an example.

(b) Find the order and degree of each of the following recurrences :

(c) Explain generating functions with suitable examples.

(d) Define Graph and Subgraph. Give an example of a subgraph H of a graph G with

𝛅(G) < 𝛅(H) and ∆(H) < ∆(G).

(e) Define Tree and Bipartite graph. Is tree a bipartite graph ? Justify your answer.

2. (a) What are Hamiltonian graphs ? Construct a non-Hamiltonian graph on 5-vertices.

(b) Show that K5 is not planar.

3. (a) What is the chromatic number of the following :

(i) A tree with at least two vertices

(ii) An even cycle C2n, n ≥ 2

(iii) An odd cycle C2n+1, n ≥ 1

(b) State and prove Euler's formula.

4. (a) Find the sum of the series given as,

using exponential generating functions.

(b) How many integer solutions are there to a1 + a2 + a3 + a4 + a5 = 28, where ak > k for each k, where 1 < k < 5 ?

5. (a) Solve the recurrence an = 4an-2, where

(b) Using an appropriate substitution, solve the recurrence given by,

**Notes-3**

1. (a) Define regular graph. Find the number of edges of a 4-regular graph with 6 vertices.

(b) Find the order of the following recurrences and state whether they are homogeneous or non-homogeneous :

(c) Solve the recurrence relation xn+1 - 8xn + 15xn -1 = 0, where Xo = 5 and xl = 21.

(d) Find the generating function for the sequence 0, 1, - 2, 3, - 4.

(e) Determine whether the sequence {an) is a solution of the recurrence relation

(f) Is a Hamiltonian graph Eulerian ? Is a Eulerian graph Hamiltonian ? Show with the help of a suitable example.

2. (a) Solve an+1 = 5an for n ≥ 0, a0 = 2 by Substitution method.

(b) Solve the recurrence an - 7an-1 + 10an-2 = 0, n ≥ 2 by Characteristic root method.

3. (a) Solve the recurrence by using iterative approach :

(c) Define isomorphic graph. Give an example of the same.

4. (a) State Euler's formula for the graph.

(b) For the following graph G,

draw subgraphs

(i) G - e

(ii) G - a

(c) Is a subgraph of a planar graph, planar ? Justify your answer.

5. (a)

(b) For which value of m and n is Km,n a tree ?

(c) Show that C6 is a bipartite graph.

IGNOU MCA MCS-033 3rd semester term-end examination (ADVANCED DISCRETE

MATHEMATICS) term-end exam notes

**Download**

**Also available:-**

**BCA/MCA asp.net project**

**Download**