+1 vote
in Data Structures & Algorithms I by (88.2k points)
If there are more than 1 topological sorting of a DAG is possible, which of the following is true.

(a) Many Hamiltonian paths are possible

(b) No Hamiltonian path is possible

(c) Exactly 1 Hamiltonian path is possible

(d) Given information is insufficient to comment anything

The above asked question is from Directed Acyclic Graph topic in portion Graph of Data Structures & Algorithms I

This question was addressed to me in my homework.

1 Answer

+1 vote
by (737k points)
selected by
 
Best answer
Correct answer is (b) No Hamiltonian path is possible

The best explanation: For a Hamiltonian path to exist all the vertices must be connected with a path, had that happened there would have been a unique topological sort.

Related questions

Welcome to TalkJarvis QnA, a question-answer community website for the people by the people. On TalkJarvis QnA you can ask your doubts, curiosity, questions and whatever going in your mind either related to studies or others. Experts and people from different fields will answer.

Categories

...