В DAG, чтобы найти гамильтонов путь, сначала обнаруживается топологическая сортировка, а затем находится гамильтонов путь из топологической сортировки.
Hamiltonian path in a DAG exists if and only if there is unique topological sorting.
Как мы можем обосновать это утверждение?
Предположим, что существует даг. Сначала мы топологически сортируем его. Чтобы этот даг имел гамильтонов путь, каждая вершина должна быть соединена со следующей вершиной в топологическом порядке, потому что, если он не связан таким образом, у него не будет гамильтонова пути (мы не может посетить каждую вершину, начиная с любого места). и если каждая вершина соединена со следующей вершиной в топологическом порядке, то не может существовать никакого другого топологического порядка. Надеюсь, это поможет.
