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

Questions asked in this paper

1. Q1 Attempt All (Each of marks) 15 marks
   • a) Select correct answer from the following
   • 1) matrix is symmetric
   • 2) If terminal vertices are same in walk
   • 3) A vertex with degree one is called
   • 4) For all positive integers is divisible by
   • 5) The ford is used for finding flow in a network
   • b) Fill in the blanks
   • 1) Any two paths with the same number of vertices are If X is set of numbers then the string are called
   • 3) give coefficient of in expansion of (x + y)"
   • 4) An Undirected graph has even number of
   • 5) V, and Vn are called terminal vertices and remaining are called vertices
   • c) Short answers
   • 1) Connected graph
   • 2) Permutation
   • 3) Pascal’s Identity
   • 4) Hamilton circuit
   • 5) Augmenting path
2. Q2 Attempt the following (Any three) 15 marks
   • a) Give combinatorial proves that =
   • b) find the coefficient of x*y*z in the expansion of (2x — 3y + also find no. of terms and sum of all coefficient
   • c) Find all non-negative integer solution to the equation < 40
   • d) Show that for all positive integers n, is divisible by 8
   • e) How many integers solutions are there for a equation all and x2< 13
   • f) Let an be the recursive relation defined by an=2an-1+an-2, n> 2 with intial condition ao=1, al=2 prove that (3)"
3. Q3 Attempt the following (Any three) (15, a} Determine if the following graphs are isomorphic Draw a tree whose (T)= 23134
   • c) Write incidence and adjacency matrix of the following graph
   • d) Define spanning subgraph. Draw any two non-isomorphic spanning sub graph of the A connected planner simple graph has 20 vertices each of degree 3. How many regions thus planner representation of this planner graph split the plan
   • f) If G is complete graph on 10 vertices then find the number of cycle in G
4. Q4 Attempt the following (Any three) 15 marks
   • a) Find flow of below
   • b) Explain matching in bipartite graphs Write Permutation shown below in cycle notation compute (product) permutation and inverse of : Ik
   • d) Explain flows and cuts What is complete matching? Explain with an example?
   • f) Explain Augmenting path with examples
5. Q5 Attempt the following (Any three) 15 marks
   • a) In how many ways we can arrange the letters in WORD TELECOMMUNICATION? How many of these arrangements have no adjacent
   • b) kind priffer (T) of the following tree
   • c) Using kruskal’s Algorithm, find shortest spanning tree of the following graph, also find weight of the shortest spanning tree
   • d) What is a combination? Prove that. a For the following graph find
   • 1. Any two path from ul to u5
   • 2. Any two walk from ul to u5
   • 3. Any two cycles containing u3
   • 4. Path of length 6 from ul to u4
   • 5. Vertex of distance 3 from u4

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