Каково максимальное количество возможных топологических видов прямого ациклического графа N-порядка?

Question

Мне нужно найти максимальное количество топологических сортов на прямом ациклическом графике N-порядка. Я проверил, выполнив первый алгоритм поиска Depth на разных прямых ациклических графах, и похоже, что это размер леса первого алгоритма поиска глубины, созданного после запуска DFS на графике. Или, может быть, я полностью ошибаюсь или что-то пропустил. Мне также нужно это доказать. Любая помощь будет оценена. Спасибо.

Answer 1

Если у вас есть n элементов, максимальное количество возможных способов заказа этих n элементов - n! (число перестановок n элементов). Поэтому вы, конечно, не можете сделать ничего лучше. Если мы найдем семейство графов с n узлами, которые имеют n! возможных топологических порядков, то мы знаем, что это должно быть максимально возможное число топологических порядков.

Как подсказка, действительно возможно найти n-node DAG с n! возможные топологические упорядочения. Попробуйте подумать о том, что это значит о возможных ребрах между этими узлами. Как только вы найдете это семейство графиков, очень легко показать, что они имеют максимально возможное количество топологических порядков, используя приведенный выше аргумент.

Надеюсь, это поможет!