Andhra University 2005-1st Year B.Tech Computer Science and Engineering Forth Semester - COMBANATORICS AND GRAPH THEORY (ELECTIVE-I) - Question Paper

MODEL PAPER

B. Tech (CSE) Degree exam

Forth Year - 1st Semester

COMBANATORICS AND GRAPH THEORY (ELECTIVE-I)

Time: three hrs
Max Marks: 70

First ques. is Compulsory

ans any 4 from the remaining ques.

All ques. carry equal marks

ans all parts of any ques. at 1 place

1. a) State pigeonhole principle.
b) Prove that the product of 3 consecutive integers is divisible by 6.
c) Differentiate ranging from a combination and a permutation.
d) State multinomial theorem.
e) Write the generating function for the number of ways of selecting r balls from three red, five blue and seven black balls.
f) Prove or disprove If every vertex of a simple graph G has degree 2, then G is a cycle.
g) Check whether 5,5,5,3,2,2,1,1 is a graphic sequence or not

2. a) Prove that C(n,r) C(n,k) = C(n,k) C(n-k, r-k) for integers n = r = k = 0.
b) obtain the number of integral solutions of the formula x1 + x2 + x3 = 20 if two = x1 = 6,3=x2 = 7,5 = x3 = 8,1 = x4 9.

3. a) obtain and solve a recurrence relation for the number of n-digit binary sequences with no triple of consecutive 1'a.
b) Solve the recurrence relation an - 5n-1 + 6n-2 where ao = and a1=5.

4. a) State and prove Vandermonde’s Identity of combinatorics.
b) Determine the coefficient of x5 y10 z5 w5 in (x - 7y + 3z-w)25

5. a) discuss the terms: bipartite graph. connected component and cut-vertex of a graph
b) Prove that a digraph is strongly connected if and only for every partition of the vertex set into nonempty sets S and T, there is an edge from S to T.

6. a) describe the terms: Eccentricity, Center and Radius of Graph.
b) define an algorithm for finding the strong components of a provided digraph.

7. a) Model the issue of network flow as a graph theoretic issue.
b) define Ford-Fulkerson labeling Algorithm on network flows

8. a) discuss the terms: Clique of a Graph, Color critical Graphs and Complete multipartite graph.
b) obtain the minimum number of edges in a connected n-vertex graph with chromotic number k.

Earning:   Approval pending.