Veer Narmad South Gujarat University 2011-2nd Sem Certification MS-CIT SB-3808 - 201 : Mathematics - 2 M.sc ( IT ) ( ) - Question Paper

Time : 3 Hours]    [Total Marks : 70

M. Sc. (I.T.) (Sem. II) Examination

March / April - 2011

Paper - 201 : Mathematics - II

SB-3808

Instructions

(1)

6silq<3i Puunkiufl [qaim SuwiA u* qsq d-onql. Fillup strictly the details of signs on your answer book.

Name of the Examination :

M. SC. (I.T.) (SEM. 2)

Name of the Subject:

PAPER - 201 : MATHEMATICS - 2

-Subject Code No.

3 l l l l l l

-Section No. (1,2,.....)

(2)    Attempt all questions.

(3)    Use of non-programmable calculator is allowed.

(4)    Figures to the right indicate full marks.

(5)    Follow usual notations.

1 (a) Determine the maximum number of edges in a    5

simple graph with n vertices and k components.

OR

(a) Prove that the sum of degrees of vertices in a finite 5 graph is twice the number of edges in it. Hence show that the number of vertices of odd degree in the graph is always even.

(b) Answer any three of the following :    9

(i)    In a simple graph with n vertices, prove that the maximum degree of any vertex is (n-1)

(ii)    Show that an infinite graph with a finite number of vertices must have at least one pair of vertices joined by an infinite number of parallel edges.

(iii)    Define the following terms and give a suitable illustration in each case :

(a)    Isomorphic graphs

(b)    Ring sum of two graphs

(c)    Regular graph.

(iv)    Give a brief account of a history of graph theory.

(v)    Find the number of vertices in a graph with 16 edges if each vertex is of degree 4.

2 (a) Let G be a complete graph with n vertices (where n 5 is an odd number >3). Determine the number of edge disjoint Hamiltonian circuits in G.

OR

(a) In a complete graph with 2k odd vertices, prove    5

that there exists k edge disjoint sub-graphs such that they together contain all edges of G and that each is a unicursal graph.

(b) Answer any three of the following :    9

(i)    If a connected graph G is an Euler graph then prove that all vertices of G are of even degree.

(ii)    Describe briefly the travelling salesman problem. Using graph theory discuss the solution of it.

(iii)    Define the following terms and give a suitable illustration in each case.

(a)    Walk in graph

(b)    Unicursal graph

(c)    Fusion of two graphs

(iv)    Let G be a connected graph with at least two vertices. If the number of edges in G is less than the number of vertices then prove that G has a vertex of degree one.

(v)    Prove that a connected graph G remains connected after removing an edge e from G if and only if e is in some circuit in G.

(a) Define :

(i)    Vertex connectivity

(ii)    Separable graph

(iii)    Spanning Tree

(iv)    Path Matrix of a graph

OR

(a) Define the incidence matrix of a graph with illustration and state properties of it.

(b) Using the Kruskals algorithm OR the Prims algorithm, 5 find a minimal spanning tree for the connected weighted graph G = (V, E) given below.

4 (a) Prove that every tree has either one or two centers. 5 Determine the radius and the diameter of a regular graph with 6 vertices.

OR

(a)    Define a connected graph. Prove that a graph G with 5 n vertices, (n-1) edges and no circuits is connected.

(b)    Answer any three of the following :    9

(i)    Prove that a tree with n vertices has (n-1) edges.

(ii)    In a binary tree with n vertices prove that (i) max I_max ⁼ (n-l)/2. (ii) The number of pendant vertices is (n+l)/2.

(iii)    Define the following terms with illustrations :

(a)    Level of a vertex in a Binary tree

(b)    Minimally connected graph

(c)    Eccentricity of a vertex.

(iv)    Find the rank and nullity of a complete graph with n vertices.

(v)    Prove that a connected graph with n vertices and (n-1) edges is a tree.

5 (a) State and prove Eulers formula.    5

OR

(a)    Show that a complete graph with five vertices is    5

non-planar.

(b)    Answer any three of the following :    9

(i)    Prove that a graph can be embedded in the surface of the sphere if and only if it can be embedded in a plane.

(ii)    If the intersection of two paths in a graph is disconnected then prove that their union has at least one circuit.

(iii)    Using Eulers formula, show that the Petersens Graph is non-planar.

(iv)    Let G be a connected planar graph with 6 vertices each of degree 4. Find the number of regions in G.

(v)    List all possible cut-sets consisting of 3 edges in the following graph. Justify your answer.

SB-3808]    4    [ 300 ]

Attachment: veer-narmad-south-gujarat-university-2011-certification-ms-cit-27838-1.pdf

Earning:   Approval pending.