Ask Question / Post resume

Post a reply to the thread: MSc Mathematics Tamil Nadu Open University Model Question Paper : www.tnou.ac.in

Your Message

Your Username:

Notes:-
1) You can copy and paste your full resume in the box below.
2) Or you can ask your question. We try to answer, as far as possible.

Title:

[QUOTE=hemalathaijt;190754][B]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[/B]

Time : 3 hours  [B]Maximum  marks[/B] : 75

[URL]http://www.tnou.ac.in/index_files/QUES/PGMODEL2008.htm[/URL]
[URL]http://www.tnou.ac.in/index_files/QUES/MSc%20Maths/mms23.doc[/URL]

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.[/QUOTE]

All times are GMT +5.5. The time now is 03:20 PM.