Tamil Nadu Open University (TNOU) 2009-2nd Year M.Sc Mathematics Tamilnadu open university Maths Graph theory and data structures - Question Paper
M.Sc. DEGREE exam – JUNE 2009.
Second Year
(AY 2005–06 and CY – 2006 batches only)
Mathematics
GRAPH THEORY AND DATA STRUCTURES
Time : three hours Maximum marks : 75
PART A — (5 x five = 25 marks)
ans any 5 ques..
every ques. carries five marks.
1.Define graph and show that the number of vertices of odd degree in a graph is always even.
2.Define a connected graph. Show that a graph G is disconnected if its vertex set V can be partitioned into 2 non-empty disjoint subsets and such that there exists no edge in G whose 1 end vertex is in and the other in .
3.(a)Prove that a closed walk of odd length contains a cycle.
(b)If G is not connected then prove that is connected.
4.Define center of a tree and prove that every tree has either 1 or 2 centers.
5.Prove that an edge of is a cut edge of G if and only if e is contained in no circuit of G.
6.Define a planar graph and prove that and are not planar.
7.Write down the chromatic polynomial for the graph .
8.Give a procedure for the breadth 1st traversal algorithm.
PART B — (5 x 10 = 50 marks)
ans any 5 ques..
every ques. carries 10 marks.
9.Define bipartite graph and show that a graph G with atleast 2 vertices is bipartite if and only if all its cycles are of even length.
10.Define Eulerian graph and prove that a connected graph G is Eulerian if and only if every vertex of G has even degree.
11.Define the operations (a) ring sum (b) decomposition (c) edge deletion (d) vertex deletion and (e) fusion and discuss every 1 with example.
12.For any graph , prove that .
13.Prove that the graphs and cannot have dual.
14.Prove that has a perfect matching if and only if for all .
15.State and prove the Vizing’s theorem.
16.Let be a 2-tree with k leaves. Then the height of satisfies and the external path length satisfies . The minimum values for and occur when all the leaves of T are on the identical level or on 2 adjacent levels.
————————
M.Sc. DEGREE EXAMINATION JUNE 2009.
Second Year
(AY 200506 and CY 2006 batches only)
Mathematics
GRAPH THEORY AND DATA STRUCTURES
Time : 3 hours Maximum marks : 75
PART A (5 5 = 25 marks)
Answer any FIVE questions.
Each question carries 5 marks.
1. Define graph and show that the number of vertices of odd degree in a graph is always even.
2.
Define a connected graph. Show that a graph G is disconnected if
its vertex set V can be partitioned into two non-empty disjoint subsets 
and 
such that there exists no
edge in G whose one end vertex is in and
the other in .
3. (a) Prove that a closed walk of odd length contains a cycle.
(b) If G is not connected then prove that 
is connected.
4. Define center of a tree and prove that every tree has either one or two centers.
5.
Prove that an edge 
of 
is a cut edge of G if
and only if e is contained in no circuit of G.
6.
Define a planar graph and prove that 
and
are not planar.
7.
Write down the chromatic polynomial for the graph 
.
8. Give a procedure for the breadth first traversal algorithm.
PART B (5 10 = 50 marks)
Answer any FIVE questions.
Each question carries 10 marks.
9. Define bipartite graph and show that a graph G with atleast two vertices is bipartite if and only if all its cycles are of even length.
10. Define Eulerian graph and prove that a connected graph G is Eulerian if and only if each vertex of G has even degree.
11. Define the operations (a) ring sum (b) decomposition (c) edge deletion (d) vertex deletion and (e) fusion and explain each one with example.
12. For
any graph , prove that 
.
13. Prove
that the graphs 
and cannot have dual.
14. Prove
that has a perfect matching if and
only if 
for all 
.
15. State and prove the Vizings theorem.
16. Let
be a 2-tree with k
leaves. Then the height 
of satisfies 
and the external path length 
satisfies 
. The minimum values for and 
occur when all the leaves of T
are on the same level or on two adjacent levels.
| Earning: Approval pending. |
