CODEWITHSUNDEEP
graphdirected-acyclic-graphstopological-sorthamiltonian-cycle
codd
codd

Reputation: 55

Unique Topological sorting implies hamiltonian path exists

In a DAG ,to find a hamiltonian path ,first topologocal sorting is found out and then hamiltonian path is found from the topological sort.

Hamiltonian path in a DAG exists if and only if there is unique topological sorting.

How do we justify this statement?

Upvotes: 3

Views: 4333

Answers (1)

user3553836
user3553836

Reputation: 95

Suppose there is a dag,We first topologically sort it.For this dag to have a hamiltonian path every vertex must be connected to next vertex in topological order,because if it is not connected that way it won't have a hamiltonian path(we can't visit every vertex starting from anywhere). and if every vertex is connected to next vertex in topological order than there can't exist any other topological ordering.I hope it helps.

Upvotes: 3

Related Questions