为什么有向无环图 (DAG) 中汉密尔顿路径的存在表明存在对 DAG 进行拓扑排序的单一方法？
Why does the existence of a Hamilton path in a Directed Acyclic Graph (DAG) show there is single way to topologically order the DAG?
这是我的理解 - 我们可以通过对 DAG 进行拓扑排序并检查按此排序顺序在每个顶点之间是否存在边来找到汉密尔顿路径。不知何故，这表明这种拓扑顺序是唯一可以存在的。显示拓扑顺序中每个顶点之间有一条边如何表明这可能是唯一的拓扑顺序？
哈密顿路径是一种拓扑排序T；假设存在不同的拓扑排序 T'，这是矛盾的。然后，看第一个T和T'不一致的地方：假设T中的i'th节点是x，i'th中的节点T' 是 y，对于一些 i >= 0 和 x != y。
然后 x 在第一个排序 T 中出现在 y 之前，但是 y 在第二个排序 x 之前出现 T' .由于T也是哈密顿路径，所以在原始DAG中存在从x到y的边的子路径。这些边中的至少一个必须是 T' 中的 backwards-edge，因为整个子路径从 x 向后引导到 y。这与拓扑排序的定义相矛盾，因此 T' 不可能存在。
这是我的理解 - 我们可以通过对 DAG 进行拓扑排序并检查按此排序顺序在每个顶点之间是否存在边来找到汉密尔顿路径。不知何故，这表明这种拓扑顺序是唯一可以存在的。显示拓扑顺序中每个顶点之间有一条边如何表明这可能是唯一的拓扑顺序？
哈密顿路径是一种拓扑排序T；假设存在不同的拓扑排序 T'，这是矛盾的。然后，看第一个T和T'不一致的地方：假设T中的i'th节点是x，i'th中的节点T' 是 y，对于一些 i >= 0 和 x != y。
然后 x 在第一个排序 T 中出现在 y 之前，但是 y 在第二个排序 x 之前出现 T' .由于T也是哈密顿路径，所以在原始DAG中存在从x到y的边的子路径。这些边中的至少一个必须是 T' 中的 backwards-edge，因为整个子路径从 x 向后引导到 y。这与拓扑排序的定义相矛盾，因此 T' 不可能存在。