Clever Geek Handbook

Unique topological sorting implies the existence of a Hamiltonian path

In DAG, to find the Hamiltonian trajectory, the first topological-analytical sort is found, and then the 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 claim?

+3


source to share


1 answer


Suppose there is a dag. We first sort it topologically. This dag needs a Hamiltonian path; each vertex must be connected to the next vertex in topological order, because if it is not connected in this way, it will not have a Hamiltonian path (we cannot visit every vertex from anywhere). and if each vertex is connected to the next vertex in a topological order, then there can be no other topological ordering. Hope this helps.



+2


source






More articles:


All Articles