graph - 唯一的拓扑排序意味着存在汉密尔顿路径

Question

在一个有向无环图中，要找到一条汉密尔顿路径，首先要找到拓扑排序，然后再从拓扑排序中找到汉密尔顿路径。

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

我们如何证明这一说法的合理性？

Answer 1

假设有一个 dag，我们首先对它进行拓扑排序。对于这个 dag 有一个哈密顿路径，每个顶点都必须按照拓扑顺序连接到下一个顶点，因为如果它不是这样连接的，它就没有哈密顿路径（我们不能从任何地方开始访问每个顶点）。如果每个顶点都以拓扑顺序连接到下一个顶点，那么就不存在任何其他拓扑顺序。我希望它有所帮助。