唯一拓撲排序意味着存在哈密頓路徑

Question

在DAG中，爲了找到哈密爾頓路徑，首先找到拓撲排序，然後從拓撲排序中找到哈密爾頓路徑。

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

我們如何證明這一說法？

Answer 1

假設有一個dag，我們首先對它進行拓撲排序。對於這個dag有一個哈密爾頓路徑 每個頂點必須以拓撲順序連接到下一個頂點，因爲如果它沒有以這種方式連接，它不會有一條哈密爾頓路徑（我們無法訪問從任何地方開始的每個頂點）。 如果每個頂點都按照拓撲順序連接到下一個頂點，那麼就不會存在任何其他的拓撲排序。我希望它有幫助。