MSc Mathematics Tamil Nadu Open University Model Question Paper : www.tnou.ac.in

[hemalathaijt]

M.Sc. DEGREE EXAMINATION –
JUNE 2008.
(AY 2005-06 and CY–2006 only)
Second Year
Mathematics
GRAPH THEORY AND DATA STRUCTURE
PG–513 MMS-23

Time : 3 hours Maximum marks : 75

http://www.tnou.ac.in/index_files/QUES/PGMODEL2008.htm
http://www.tnou.ac.in/index_files/QU...aths/mms23.doc

Answer for 5 marks question should not exceed 2 pages.
Answer for 10/15 marks questions should not exceed 5 pages.

PART A — (5 ? 5 = 25 marks)

Answer any FIVE questions.
Each question carries 5 marks.

1.Define a connected graph. Prove that if a graph G is not connected then , its complement is connected.
2.Discuss the travelling sales man problem.
3.Define a tree. Show that a graph with n vertices, edges and no circuits is connected.
4.Prove that the ring sum of any two cut sets in a graph is either a third cut or an edge disjoint union of cut sets.
5.Show that a graph can be embedded in a surface of a sphere if and only if it can be embedded in a plane.
6.Prove that a graph is 2-chromatic if and only if it is bipartite.
7.What is the comparison tree of an algorithm? Draw the comparison tree for sequential search.
8.Define adjacency vertices and explain the adjacency table representation.

PART B — (5 ? 10 = 50 marks)

Answer any FIVE questions.
Each question carries 10 marks.

9.Prove that a simple graph with vertices and k components can have at most edges.
10.State and prove Dirac’s theorem.
11.(a)Prove that a tree with n vertices has edges.
(b)Show that every tree has either one or two centres.
12.Show that a graph with number of vertices greater than or equal to 3 is 2-connected if and only if any two vertices of G are connected by atleast two internally disjoint paths.
13.(a)Prove that every face is an n -circuit.
(b) State and prove the necessary and sufficient condition for two planar graphs to be duals of each other.
14.Show that the vertices of every planar graph can be properly coloured with five colours.
15.If is any finite set of vertices, show that there is one-to-one correspondence f from the set of orchards whose set of vertices is S to the set of binary trees whose set of vertices is S.
16.Discuss the problem of topological sorting and explain the Depth-First algorithm for topological sorting.