BSc CS Sem 3 BSc CS Semester 3 (2020 2021) 2021 Combinatorics And Graph Theory Question Paper - Mumbai University | munotes

Questions asked in this paper

1. Q1 The relation between permutation and combination
2. Q2 Which of the following statement is true?
   • b) (x 4 (") xi
3. Q3 The coefficient of in the expansion of (x +
4. Q4 Number of solution to the equation x, + x2 where x; > Ois,
5. Q5 The value of |AUB
6. Q6 Which of the following statement is true?
   • a) Every non-empty subset of positive integers has least element
   • b) Every non-empty subset of positive integers has greatest element
   • c) Every subset of positive integers has least element
   • d) Every subset of positive integers has greatest element
7. Q7 is not true for which of the following statement
   • a) n(n-1) is divisible by 3
   • b) n(n+1) (n+2) is divisible by 6
   • c) 8" — divisible by 5
   • d) n(n+1) is divisible by 2
8. Q9 Total number of subsets of X= {1} are
   • d) Subsets are not exist
9. Q10 In a graph If two vertices are connected by atmost one line , then the graph is
   • a) Simple
   • b) Multigraph
   • c) Loop
   • d) Digraph
10. Q11 In a graph If two vertices are connected by more than one line , then the graph is
    • a) Simple
    • b) Multigraph
    • c) Loop
    • d) Digraph
11. Q12 A graph in which an edge from vertex to itself, is
    • a) Simple graph
    • b) Loop graph
    • c) Cycle
    • d) Wheels
12. Q13 If be a graph and be a subgraph, then
13. Q14 A vertex with degree zero is called
    • a) Odd vertex
    • b) Pendent vertex
    • c) Isolated vertex
    • d) Zero vertex
14. Q15 A graph is complete
    • a) There is a path between every pair of vertices
    • b) Every vertex is connected to each and every other vertices
    • c) There is a path from a to b and b to a, for every pair of vertices
    • d) There is a path from a to b but not from b to a, for every air of vertices
15. Q16 If G is Planar connected graph with ‘e’ edges and ‘v’ vertices, then no. of regions in planar representation is
16. Q17 Following graph is not planar
    • a) Complete graph K3
    • b) Cycle
17. Q18 Chromatic number of complete bipartite graph
18. Q19 Number of edges in graph with 10 vertices each of degree
19. Q20 Prim’s algorithm is used to find
    • a) Spanning tree
    • c) Spanning subgraph
    • d) Induced subgraph
20. Q21 In a network flow,
    • a) Inflow (v) = outflow (v), for all V-{s,t}
    • b) Inflow (v) = outflow (v), for all V
    • c) Inflow (v) = outflow (v), for all V — {s}
    • d) Inflow (v) = outflow (v), for all V-{t}
21. Q22 What is the sink?
    • a) A vertex with no leaving edges
    • b) A vertex with no coming edges
    • c) Centre vertex
    • d) A vertex with least weight
22. Q23 What is the value of maximum flow in the following network?
23. Q24 Relation between flow and capacity
    • a) Flow f(x, y) = Capacity c(x, y)
    • b) Flow f(x, y) < Capacity c(x, y)
    • c) Flow f(x, y) > Capacity c(x, y)
    • d) Flow f(x, y) < Capacity c(x, y)
24. Q25 The value of flow in a network flow
    • a) Inflow (S)
    • b) Inflow(t)
    • c) Inflow(v) where v# s
    • d) Inflow(v) where t

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