3

我需要在 N 阶的直接无环图上找到最大拓扑排序数。我通过在各种直接无环图上运行深度优先搜索算法进行了检查，看起来它是在图上运行 DFS 后创建的深度优先搜索算法森林的大小。或者，也许我完全错了或错过了什么。我也需要证明。任何帮助将不胜感激。谢谢你。

4

1 回答 1

11

如果您总共有 n 个元素，那么对这 n 个元素进行排序的最大可能方式是 n! （n 个元素的排列数）。所以你当然不能做得比这更好。如果我们能找到一个有 n 个节点的图族，其中有 n! 可能的拓扑排序，那么我们知道它必须是最大可能的拓扑排序数。

作为提示，确实有可能找到 n 个节点的 DAG！可能的拓扑排序。试着想想这对这些节点之间可能的边意味着什么。一旦你找到了这个图族，就很容易通过使用上述参数来证明它们具有最大可能的拓扑排序数。

希望这可以帮助！

于 2013-05-19T21:22:43.473 回答