Tamil Nadu Open University (TNOU) 2008-2nd Year M.Sc Mathematics – - Question Paper

M.Sc. DEGREE exam – JUNE 2008.
(AY 2005-06 and CY–2006 only)
2nd Year Mathematics
GRAPH THEORY AND DATA STRUCTURE
Time : three hours Maximum marks : 75
ans for five marks ques. should not exceed two pages.
ans for 10/15 marks ques. should not exceed five pages.
PART A — (5 ´ five = 25 marks)
ans any 5 ques..
every ques. carries five marks.
1. describe a connected graph. Prove that if a graph G is not connected then , its complement is connected.

2. explain the travelling sales man issue.

3. describe a tree. Show that a graph with n vertices, edges and no circuits is connected.

4. Prove that the ring sum of any 2 cut sets in a graph is either a 3rd 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. describe adjacency vertices and discuss the adjacency table representation.

PART B — (5 ´ 10 = 50 marks)
ans any 5 ques..
every ques. 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 1 or 2 centres.

12. Show that a graph with number of vertices greater than or equal to three is 2-connected if and only if any
2 vertices of G are connected by atleast 2 internally disjoint paths.

13. (a) Prove that every face is an n -circuit.
(b) State and prove the necessary and sufficient condition for 2 planar graphs to be duals of every
other.

14. Show that the vertices of every planar graph can be properly coloured with 5 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. explain the issue of topological sorting and discuss the Depth-First algorithm for topological sorting.

————————

Earning:   Approval pending.