Madurai Kamraj University (MKU) 2006 M.Sc Mathematics "OPTIONAL- Graph Theory And Data structure" - Question Paper
This Is for the MK DDU - "MSC Maths In in MKU", and please Refer to the Attached File,
Keep Visit and post the ques. and answers you are looking for,
Happy Studying in our isc.com,Dont forget to re-visit and Post your Collection of ques.
It's For "Msc in MATHS in MKU", It'a Course in "Madurai Kamaraj University" or %MK University%
The paper Name Is "OPTIONAL- Graph Theory And Data structure"
6563/KAB OCTOBER 2007
Optional GRAPH THEORY AND DATA STRUCTURES
(For those who joined in July 2003 and after)
Time : Three hours Maximum : 100 marks
SECTION A (4 x 10 = 40 marks)
Answer any FOUR questions.
1. Prove that in a connected graph G with exactly 2k odd vertices, there exists k-edge disjoint subgraphs such that they together contain all edges of G and that each is a unicursal graph.
2. Prove that a graph G is a tree if and only if there is one and only path between every pair of vertices of G.
3. Describe Prims algorithm for shortest spanning tree.
4. Prove that every circuit has an even number of edges in common with any cutset.
J
5. Prove that the maximum vertex connectivity in a graph with n vertices and e edges is [2e / n\.
6. Define chromatic polynomial of a graph. Illustrate it.
7. Prove that a covering g of a graph is minimal if and only if I contains no paths of length three or more.
8. State and prove the path-length theore.
SECTION B (3 x 20 = 60 marks)
Answer any THREE questions
9. Prove that a connected graph G is an Euler graph if and only if all vertices of G are of even degree.
10. (a) Explain traveling salesman problem.
(
i
(b) Prove that a tree with n vertices has n-1 edges.
11. (a) Prove that the ring sum of twp cutsets m a graph is either a third cutset or an edge-disjoint union of cutsets.
(b) Illustrate the result.
12. (a) State and prove Eulers formula for connected graphs.
(b) Deduce that Ks and K.3,3 are nonplanar.
13. State and prove five colour theorem.
\ - n *
14. (a) If T is a 2-tree with k leaves, iov that the minimum values for h and E(T) occur whip all the leaves of T are on the same level or on two adjacent leaves.
(b) Explain the method of sequential search.
|
Attachment: |
| Earning: Approval pending. |
