**DOWNLOAD FREE PDF** **<<CLICK HERE>>**

## Hamiltonian Path Problem Multiple choice Questions and Answers (MCQs)

Question 1 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER] |

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 |

Question 1 Explanation:

The Hamiltonian path problem can be solved efficiently using branch and bound approach. It can also be solved using a backtracking approach.

Question 2 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER] |

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 |

Question 2 Explanation:

Hamiltonian path problem is a problem of finding a path in a graph that visits every node exactly once whereas Hamiltonian cycle problem is finding a cycle in a graph.

Question 3 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER] |

Hamiltonian path problem is .....

NP problem | |

N class problem | |

P class problem | |

NP complete problem |

Question 3 Explanation:

Hamiltonian path problem is found to be NP complete. Hamiltonian cycle problem is also an NP- complete problem.

Question 4 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER] |

There is no existing relationship between a Hamiltonian path problem and Hamiltonian circuit problem.

true | |

false |

Question 4 Explanation:

There is a relationship between Hamiltonian path problem and Hamiltonian circuit problem. The Hamiltonian path in graph G is equal to Hamiltonian cycle in graph H under certain conditions.

Question 5 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER] |

Which of the following problems is similar to that of a Hamiltonian path problem?

knapsack problem | |

closest pair problem | |

travelling salesman problem | |

assignment problem |

Question 5 Explanation:

Hamiltonian path problem is similar to that of a travelling salesman problem since both the problem traverses all the nodes in a graph exactly once.

There are 5 questions to complete.