On This Page
This set of Discrete Mathematics Multiple Choice Questions & Answers (MCQs) focuses on Discrete Mathematics Set 8
Q1 | Every Isomorphic graph must have representation.
- cyclic
- adjacency list
- tree
- adjacency matrix
Q2 | A cycle on n vertices is isomorphic to its complement. What is the value of n?
- 5
- 32
- 17
- 8
Q3 | A complete n-node graph Kn is planar if and only if
- n ≥ 6
- n2 = n + 1
- n ≤ 4
- n + 3
Q4 | A graph is if and only if it does not contain a subgraph homeomorphic to k5 or k3,3.
- bipartite graph
- planar graph
- line graph
- euler subgraph
Q5 | An isomorphism of graphs G and H is a bijection f the vertex sets of G and H. Such that any two vertices u and v of G are adjacent in G if and only if
- f(u) and f(v) are contained in g but not contained in h
- f(u) and f(v) are adjacent in h
- f(u * v) = f(u) + f(v) d) f(u) = f(u)2 + f(v
- 2
Q6 | What is the grade of a planar graph consisting of 8 vertices and 15 edges?
- 30
- 15
- 45 d
- 106
Q7 | A is a graph with no homomorphism to any proper subgraph.
- poset
- core
- walk
- trail
Q8 | Which of the following algorithm can be used to solve the Hamiltonian path problem efficiently?
- branch and bound
- iterative improvement
- divide and conquer
- greedy algorithm
Q9 | The problem of finding a path in a graph that visits every vertex exactly once is called?
- hamiltonian path problem
- hamiltonian cycle problem
- subset sum problem
- turnpike reconstruction problem
Q10 | Hamiltonian path problem is
- np problem
- n class problem
- p class problem
- np complete problem
Q11 | Which of the following problems is similar to that of a Hamiltonian path problem?
- knapsack problem
- closest pair problem
- travelling salesman problem
- assignment problem
Q12 | Who formulated the first ever algorithm for solving the Hamiltonian path problem?
- martello
- monte carlo
- leonard
- bellman
Q13 | In what time can the Hamiltonian path problem can be solved using dynamic programming?
- o(n)
- o(n log n)
- o(n2)
- o(n2 2n)
Q14 | Who invented the inclusion-exclusion principle to solve the Hamiltonian path problem?
- karp
- leonard adleman
- andreas bjorklund
- martello
Q15 | For a graph of degree three, in what time can a Hamiltonian path be found?
- o(0.251n)
- o(0.401n)
- o(0.167n)
- o(0.151n)
Q16 | What is the time complexity for finding a Hamiltonian path for a graph having N vertices (using permutation)?
- o(n!)
- o(n! * n)
- o(log n)
- o(n)
Q17 | How many Hamiltonian paths does the following graph have?
- 1
- 2
- 3
- 4
Q18 | How many Hamiltonian paths does the following graph have?
- 1
- 2
- 3
Q19 | If set C is {1, 2, 3, 4} and C – D = Φ then set D can be
- {1, 2, 4, 5}
- {1, 2, 3}
- {1, 2, 3, 4, 5}
- none of the mentioned
Q20 | Let C and D be two sets then C – D is equivalent to
- c’ ∩ d
- c‘∩ d’
- c ∩ d’
- none of the mentioned
Q21 | For two sets C and D the set (C – D) ∩ D will be
- c
- d
- Φ
- none of the mentioned
Q22 | Which of the following statement regarding sets is false?
- a ∩ a = a
- a u a = a
- a – (b ∩ c) = (a – b) u (a –c)
- (a u b)’ = a’ u b’
Q23 | Let C = {1,2,3,4} and D = {1, 2, 3, 4} thenwhich of the following hold not true in this case?
- c – d = d – c
- c u d = c ∩ d
- c ∩ d = c – d
- c – d = Φ
Q24 | Let Universal set U is {1, 2, 3, 4, 5, 6, 7, 8}, (Complement of A) A’ is {2, 5, 6, 7}, A ∩ B is {1, 3, 4} then the set B’ will surely have of which of the element?
- 8
- 7
- 1
- 3
Q25 | Let a set be A then A ∩ φ and A U φ are
- φ, φ
- φ, a
- a, φ
- none of the mentioned