3
DAG에서 해밀턴 경로를 찾으려면 먼저 위상 토폴로지 정렬을 찾은 다음 위상 트리 정렬에서 해밀턴 경로를 찾습니다.고유 토폴로지 정렬은 해밀턴 경로가 있음을 의미합니다.
Hamiltonian path in a DAG exists if and only if there is unique topological sorting.
우리는 어떻게이 진술을 정당화합니까?
A
답변
2
dag가 있다고 가정하면 토폴로지별로 토폴로지를 정렬합니다.이 dag에 해밀턴 경로가 있습니다. 모든 버텍스는 토폴로지 순서에 따라 다음 버텍스에 연결되어야합니다. 연결되지 않으면 연결되지 않습니다. hamiltonian 경로 (어디에서 시작하든 모든 정점을 방문 할 수 없음). 그리고 모든 버텍스가 토폴로지 순서로 다음 버텍스에 연결되어 있다면 다른 토폴로지 주문이 존재할 수 없다. 도움이되기를 바랍니다.
이것은 좋은 질문입니다. 시험 문제입니까? –
아니에요, 아니에요. 책의 토폴로지 정렬 섹션에서이 진술을 발견했습니다. 나는 그것을 증명하려고했지만 couldnt했습니다. – codd