Top 350+ Solved Discrete Mathematics MCQ Questions Answer
Q. Every Isomorphic graph must have representation.
a. cyclic
b. adjacency list
c. tree
d. adjacency matrix
Q. A cycle on n vertices is isomorphic to its complement. What is the value of n?
a. 5
b. 32
c. 17
d. 8
Q. A graph is if and only if it does not contain a subgraph homeomorphic to k5 or k3,3.
a. bipartite graph
b. planar graph
c. line graph
d. euler subgraph
Q. 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
a. f(u) and f(v) are contained in g but not contained in h
b. f(u) and f(v) are adjacent in h
c. f(u * v) = f(u) + f(v) d) f(u) = f(u)2 + f(v
d. 2
Q. What is the grade of a planar graph consisting of 8 vertices and 15 edges?
a. 30
b. 15
c. 45 d
d. 106
Q. Which of the following algorithm can be used to solve the Hamiltonian path problem efficiently?
a. branch and bound
b. iterative improvement
c. divide and conquer
d. greedy algorithm
Q. The problem of finding a path in a graph that visits every vertex exactly once is called?
a. hamiltonian path problem
b. hamiltonian cycle problem
c. subset sum problem
d. turnpike reconstruction problem
Q. Hamiltonian path problem is
a. np problem
b. n class problem
c. p class problem
d. np complete problem
Q. Which of the following problems is similar to that of a Hamiltonian path problem?
a. knapsack problem
b. closest pair problem
c. travelling salesman problem
d. assignment problem
Q. Who formulated the first ever algorithm for solving the Hamiltonian path problem?
a. martello
b. monte carlo
c. leonard
d. bellman
Q. In what time can the Hamiltonian path problem can be solved using dynamic programming?
a. o(n)
b. o(n log n)
c. o(n2)
d. o(n2 2n)
Q. Who invented the inclusion-exclusion principle to solve the Hamiltonian path problem?
a. karp
b. leonard adleman
c. andreas bjorklund
d. martello
Q. For a graph of degree three, in what time can a Hamiltonian path be found?
a. o(0.251n)
b. o(0.401n)
c. o(0.167n)
d. o(0.151n)
Q. What is the time complexity for finding a Hamiltonian path for a graph having N vertices (using permutation)?
a. o(n!)
b. o(n! * n)
c. o(log n)
d. o(n)