Aspire's Library
Study Stuff for MCA Examinations - NIMCET
Previous Year Question (PYQs)
In the context of a Hamiltonian problem, which of the following are correct?
A. Hamiltonian cycle problem is NP-Complete
B. If $G$ is an undirected Bipartite graph with an odd number of vertices, then $G$ is Hamiltonian.
C. Hamiltonian path problem cannot be solved in polynomial time on directed acyclic graph
D. If $G$ is a connected undirected graph with at least three vertices and $G^3$ is the graph obtained by connecting all pairs of vertices that are connected by a path in $G$ of length at most $3$.
E. If any NP complete problem is polynomial time solvable the $(P=NP)$.
Choose the most appropriate answer from the options given below:
Solution
Statement A is true.
Hamiltonian cycle problem is NP-Complete.
Statement B is false.
A bipartite graph with odd number of vertices cannot have a Hamiltonian cycle.
Statement C is false.
Hamiltonian path problem can be solved in polynomial time for directed acyclic graph.
Statement D is true.
In graph power concept, $G^3$ connects vertices having distance at most $3$ in $G$.
Statement E is true.
If any NP-Complete problem is solved in polynomial time, then $P=NP$.
So, correct statements are A, D and E.
Correct option is:
$\boxed{(c)\ \text{A, D, E only}}$
Online Test Series, Information About Examination,
Syllabus, Notification
and More.
View More
Online Test Series, Information About Examination,
Syllabus, Notification
and More.
View More
