graph - 独特的拓扑排序意味着哈密尔顿路径存在

Question

在 DAG 中，要找到哈密顿路径，首先要找到拓扑排序，然后从拓扑排序中找到哈密顿路径。

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

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

Answer 1

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