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
codd
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
user3553836
source
to share