Discrete Mathematics
Q41.
Let A and B be sets with cardinalities m and n respectively. The number of one-one mappings from A to B, when m \lt n, isQ42.
How many onto (or surjective) functions are there from an n-element ( n \geq 2 ) set to a 2-element set?Q43.
Let f be a function from a set A to a set B, g a function from B to C, and h a function from A to C, such that h(a) = g(f(a)) for all a \in A. Which of the following statements is always true for all such functions f and g?Q44.
Let S denote the set of all functions f:{\{0,1\}}^{4} \rightarrow \{0,1\}. Denote by N the number of functions from S to the set {0,1}. The value of log_{2} log_{2}N is______.Q45.
Let : A\rightarrowB be injective (one-to-one) function. Define g:2^{A}\rightarrow 2^{B} as: g(C) = {f (x)| x \inC), for all subsets C of A. Defineg:2^{B}\rightarrow 2^{A} as : h(D) = {x | x \in A, f (x) \in D}, for all subsets D of B. Which of the following statements is always true?Q46.
Graph G is obtained by adding vertex s to K_{3,4} and making s adjacent to every vertex of K_{3,4}. The minimum number of colours required to edge-colour G is _______Q47.
In a directed acyclic graph with a source vertex s, the quality-score of a directed path is defined to be the product of the weights of the edges on the path. Further, for a vertex v other than s, the quality-score of v is defined to be the maximum among the quality-scores of all the paths from s to v. The quality-score of s is assumed to be 1. The sum of the quality-scores of all vertices on the graph shown above is ______Q48.
Let G be a graph with 100! vertices, with each vertex labelled by a distinct permutation of the numbers 1,2,...,100. There is an edge between vertices u and v if and only if the label of u can be obtained by swapping two adjacent numbers in the label of v. Let y denote the degree of a vertex in G, and z denote the number of connected components in G. Then, y+ 10z = _____.Q49.
Consider the set of all functions f:{0,1,...,2014}\rightarrow{0,1...,2014} such that f(f(i))=i, for 0\leqi\leq2014 . Consider the following statements. P. For each such function it must be the case that for every i, f(i) = i, Q. For each such function it must be the case that for some i,f(i) = i, R. Each such function must be onto. Which one of the following is CORRECT?Q50.
An articulation point in a connected graph is a vertex such that removing the vertex and its incident edges disconnects the graph into two or more connected components. Let T be a DFS tree obtained by doing DFS in a connected undirected graph G. Which of the following options is/are correct?