N 차 직접 비주기 곡선의 가능한 토폴로지 종류의 최대 수는 얼마입니까?

Question

N-order의 Direct Acyclic Graph에서 토폴로지 정렬의 최대 개수를 찾아야합니다. 다양한 Direct Acyclic 그래프에서 Depth first 검색 알고리즘을 실행하여 검사 한 결과 그래프에서 DFS를 실행 한 후 생성 된 Depth first 검색 알고리즘 포리스트의 크기 인 것처럼 보입니다. 아니면 내가 완전히 잘못되었거나 뭔가를 놓친 것일 수도 있습니다. 나는 또한 그것을 증명할 필요가있다. 어떤 도움을 주시면 감사하겠습니다. 고맙습니다.

Answer 1

총 n 개의 요소가있는 경우 해당 n 개의 요소를 주문할 수있는 최대 방법은 n입니다. (n 개의 요소의 순열의 수). 그래서 당신은 확실히 그것보다 더 잘할 수 없습니다. n 개의 노드를 가진 그래프 군을 찾을 수 있다면 n! 가능한 토폴로지 순서 (topological orderings)가 있다면, 그 토폴로지 순서의 최대 가능한 수임을 알 수 있습니다.

힌트로 n 노드 DAG를 실제로 찾을 수 있습니다. 가능한 토폴로지 순서. 그 노드들 사이에 가능한 모서리가 무엇을 의미하는지 생각해보십시오. 일단이 그래프 군을 발견하면 위의 인수를 사용하여 가능한 최대 토폴로지 순서가 있음을 보여주는 것이 매우 쉽습니다.

희망이 도움이됩니다.