多哈密顿路径和拓扑排序
Multiple hamiltonian paths and topological sorting
我们知道，如果我们在 DAG 中有一条哈密顿路径，那么拓扑排序将是唯一的，但是如果我们有多个哈密顿路径，那岂不是意味着可以有多个拓扑排序：一个不同的对于这些路径中的每一个？
每个 DAG 要么有零个哈密顿路径，要么有一个哈密顿路径。这是一种查看方式。假设有两个或更多。查看那些彼此不同的哈密顿路径上的第一个节点；我们称它们为 x 和 y。这意味着在一条路径中，x 在 y 之前，而在另一条路径中，y 在 x 之前。但这意味着图中有一个循环：我们可以使用第一条哈密顿路径的子路径从 x 到 y，然后我们可以使用第二条哈密顿路径的子路径从 y 到 x。但是，这是不可能的，因为 DAG 不能有循环。
这意味着您所做的声明是空洞的真实 - "if a graph has two different Hamiltonian paths, then it has two different topological orderings" 是真实的，因为前提总是错误的。
我们知道，如果我们在 DAG 中有一条哈密顿路径，那么拓扑排序将是唯一的，但是如果我们有多个哈密顿路径，那岂不是意味着可以有多个拓扑排序：一个不同的对于这些路径中的每一个？
每个 DAG 要么有零个哈密顿路径，要么有一个哈密顿路径。这是一种查看方式。假设有两个或更多。查看那些彼此不同的哈密顿路径上的第一个节点；我们称它们为 x 和 y。这意味着在一条路径中，x 在 y 之前，而在另一条路径中，y 在 x 之前。但这意味着图中有一个循环：我们可以使用第一条哈密顿路径的子路径从 x 到 y，然后我们可以使用第二条哈密顿路径的子路径从 y 到 x。但是，这是不可能的，因为 DAG 不能有循环。
这意味着您所做的声明是空洞的真实 - "if a graph has two different Hamiltonian paths, then it has two different topological orderings" 是真实的，因为前提总是错误的。