B.Sc. (Computer Science) Sem 3 Combinatorics and Graph Theory 2017-18 ATKT Question Paper - Mumbai University | munotes

Questions asked in this paper

• 2) Figures to the right indicate marks

1. Q3 Illustrations, in-depth answers and diagrams will be appreciated
2. Q4 Mixing of sub-questions is not allowed
3. Q1 Attempt All (Each of 5Marks) (15M)
   • (a) Select correct answer from the following:
4. Q1 The product of two consecutive natural number is always divisible
5. Q2 String is the of characters or symbols
6. Q3 with degree one is called
   • (a) Pendant (b) isolated (c), incident. (d) none of the above
7. Q4 A graph with no parallel edges and no loops is called a graph
   • (a) simple pseudo (c) multiple (d) none of the above
8. Q5 Augmenting path is used to the value of a network flow
   • (a) increase (b) decrease (d) none of the above
   • (b) Fill in the blanks
9. Q1 The is used to find the coefficients in binomial
10. Q3 The walk in which no edges is repeated more than one is called
11. Q4 Chromatic number of complete graph with n vertices is
12. Q5 In network the amount of leaving the source to the amount arriving at the sink
    • (c) Short Answers
13. Q3 Regular graph
14. Q5 Augmenting path
15. Q2 Attempt the following (Any THREE) (15M)
    • (a) For the binary strings of length 10, how many of them
    • (a) Begins with 1
    • (b) Begins with 1 and ends with 0
    • (b) Determine the coefficient of in the expansion of (x + y+
    • Q. P. Code: 19835
    • (c) For any positive integer n, the sum of the first n positive integers Prove by first principle of mathematical induction
    • (d) How many integer- valued solutions are there for the equation
    • (e) How Combinatorics is useful in graph theory?
    • (f) For each n >0, prove that
16. Q3 Attempt the following (Any THREE) (15M)
    • (a) Show that following graphs are isomorphic
    • (b) Draw a tree whose prufer(T) = 6643143 with vertex set {1, 2, 3, 4, 5, 6, 7, 8,
    • (c) Explain the colouring of vertices in a graph
    • (d) State pigeon hole principle and Show that if any five numbers from the set 4, 5, 6, 7, 8} are chosen, then two of them will add up to 9
    • (e) Define adjacency matrix in a graph also find the adjacency matrix of the
    • (f) Give an example of graph which is both Eulerian and Hamiltonian and justify it
17. Q4 Attempt the following (Any THREE) 15 marks
    • (a) Explain Matching in Bipartite graphs
    • Q. P. Code: 19835
    • (b) Explain Ford- Fulkerson’s labelling algorithm
    • (c) Find maximum flow of the following network
    • (d) Suppose we are colouring the vertices of the square using black and white Draw all the possible pattern of colouring also find the different transformations for fixed colouring
    • (e) Write permutations shown below in cycle notation of 7,and 1 also compute 7,7 (product of two permutations)
    • (f) State Burnside’s theorem
18. Q5 Attempt the following (Any THREE) 15 marks
    • (a) In how many ways can we arrange the letters in TALLAHASSEE? How many of these arrangements have no adjacent A’s?
    • (b) Define Chromatic number with example
    • (c) Explain flows and cuts
    • (d) Find the minimum spanning tree using Kruskal’s algorithm for the given
    • (e) State first principle and second principle of mathematical induction

Read from the scan above, so a character or two may differ. The scan is the original.