Uttar Pradesh Technical University (UPTU) 2007 M.C.A Combinatorics & Graph Theory - Question Paper
Printed Pages : 4 MCA- 124
PAPER ID: 1452
(Following Paper ID and Roll No. to be filled in your Answer Book)
Roll No.
(SEM. II) EXAMINATION, 2006-07 COMBINATORICS & GRAPH THEORY
Time : 3 Hours] [Total Marks : 100
Note : Attempt all the questions.
1. Answer any four parts of the following:- 5x4=20
(a) Determine the number of positive integers n where: 1< n < 100 and n is not divisible by
2, 3, or 5?
(b) Find the sequence corresponding to the generating function f(x) = (1 + x)"n, where n is positive integer.
(c) Solve the recurrence relation
an"4an-l + 4an-2 = (n+l)2n.
(d) Show that no simple graph can have the degrees of all its vertices distinct.
(e) Define Euterian and Hamilton graph. Draw a graph with six vertices which is
(i) Hamiltonian and non-eulerian
(ii) Eulerian and non-hamiltonian
(1) Discuss the traveling salesman problem.
Define central tree, rooted and binary tree. Prove that a simple graph G is a tree if and only if there is one path between every pair of vertices.
Prove that a tree having n vertices has exactly (n-1) edges.
(a)
(b)
(c)
Let G be a graph having V vertices and E edges and K components, where each component is a tree. Obtain a formula in terms of V, E and K.
|
Define spanning tree and minimal spanning tree.Draw three spanning trees of the graph. |
 |
|
Represent the algebraic expression by a binary rooted tree. |
(e)
(7+a)% 8 x (a-b)3-
Write short note on connectivity and seperativity. Network flow Nin-cut theory.
(f)
3. Answer any two of the following: (a)
10x2=20
Prove that for any connected planar graph G, V-e+r=2. Where v, e and r are the number of vertices, edges and regions of the graph respectively.
Define the dual of a graph G. Prove that a graph G has a dual G if and only if it is planar. Write properties of Graph and dual graph. Define incidence and adjancy matrices of a graph. Find incidence and adjancy matrics of the following graph.
 |
|
4. Answer any two of the following |
10x2=20
(c)
(a) Define chromatic polynomial. Find the chromatic polynomial and chromatic number of the following graphs.
|
(i) |  |
(b) Explain the four colour problem. Show that vertices of a planar graph with less than 30 edges is 4-colourable.
(c) Explain connectivity and seperability of a graph. What is the maximum vertex connectivity and edge connectivity for the graph shown in the following figure.
5. Answer any two of the following:- 10x2=20
(a) Define abborescence graph. Write down the procedure to obtain the expression in polish notation.
(b) State and prove Cayleys theorem.
(c) In how many distinct ways can we 4 colour vertices of a regular hexagon which is free to move in space.
|
Attachment: |
| Earning: Approval pending. |
