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

Question

假设所讨论的图是DAG(有向无环图).

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

换句话说,只有一个顶点没有必要(但不充分)的入射边缘来生成唯一的拓扑排序？

Answer 1

当且仅当在拓扑顺序中每对连续顶点之间存在有向边时(即,有向图具有哈密​​顿路径),拓扑排序才是唯一的. 资源

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

希望这可以帮助

Answer 2

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

在这种情况下，我认为你是对的，这是一个证明草图：

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

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