N階直接非循環圖可能的拓撲排序的最大數目是多少？

Question

我需要找到N階直接無環圖上拓撲排序的最大數目。我通過在各種直接非循環圖上運行深度優先搜索算法進行檢查，它看起來像是在圖上運行DFS後創建的深度優先搜索算法林的大小。或者，也許我完全錯了或錯過了什麼。我也需要證明這一點。任何幫助將不勝感激。謝謝。

Answer 1

如果總共有n個元素，那麼排列這n個元素的最大可能方法數是n！ （n個元素的排列數）。所以你當然不能做得比這更好。如果我們可以找到一個有n個節點的圖族可能的拓撲排序，那麼我們知道必須是最大可能數量的拓撲排序。

作爲一個提示，確實有可能找到n節點的DAG與n！可能的拓撲排序。試着想一下這些節點之間可能存在的邊緣意味着什麼。一旦你找到了這個圖表族，通過使用上面的參數很容易證明他們有最大可能數量的拓撲排序。

希望這會有所幫助！