graph - 具有唯一拓扑排序的图的先决条件

Question

让我们假设一个有问题的图是一个 DAG（有向无环图）。

问题：当且仅当只有一个顶点没有传入边时，我是否可以得出结论，这样的图将具有唯一的拓扑排序？

换句话说，只有一个没有传入边的顶点是必要的（但还不够）来生成唯一的拓扑排序吗？

Answer 1

当且仅当在拓扑顺序中的每对连续顶点之间存在有向边（即，有向图具有哈密顿路径）时，拓扑排序才是唯一的。 来源

哈密​​顿路径只是意味着两个顶点之间的路径只会访问每个顶点一次，并不意味着一个顶点必须没有传入边。你可以有一个哈密顿路径，它实际上是一个循环。这仍然会产生一个独特的拓扑排序（当然，如果这对你很重要，它也会是一个循环）。

希望这可以帮助

Answer 2

哈哈，好的。很抱歉对于这个误会。

在这种情况下，我假设您是对的，这是一个证明草图：

我们有一个独特的拓扑排序 => 我们只有一个合法的顶点放在第一位 => 对于每个顶点，除了一个，放在第一位是不合法的 => 对于每个顶点，除了一个，我们有传入的边。

希望现在我回答了你的问题......

Answer 3

不！下图只有一个没有传入边的顶点，并且有 2 种可能的解决方案。

1 -> 2
3 -> 4
3 -> 1
4 -> 2

两种解决方案是：

2 0 3 1
2 3 0 1

Answer 4

是的，您可以说作为一个必要条件，就好像有多个入度 = 0 的节点一样，那么就不会有哈密顿路径，因此没有唯一的拓扑顺序。仅对于图的起始节点（in-degree=0）将没有传入边，其余所有顶点必须具有来自其拓扑祖先的传入边，这意味着在拓扑排序中的当前节点之前的节点。如果拓扑排序中的每个连续节点都没有边，则 DAG 将没有唯一顺序。

Answer 5

有人给出了答案。这里我只想给你一个反例：G = {(1,2), (1,3)}。在这种情况下，有 2 个有效的拓扑排序：1,2,3 和 1,3,2