Мы знаем, что если у нас есть гамильтонов путь в DAG, то топологическая сортировка будет уникальной, но что, если бы у нас было несколько гамильтоновых путей, не означало бы это, что может быть несколько топологических сортировок: разные для каждого из этих пути?
Множественные гамильтоновы пути и топологическая сортировка
comment
Это просто математический вопрос?
- person BSMP schedule 24.08.2015
comment
Я читал о топологической сортировке и запутался в ее связи с гамильтоновыми путями.
- person Edmeral schedule 24.08.2015
Ответы (1)
Каждый DAG имеет либо нулевые гамильтоновы пути, либо один гамильтонов путь. Вот один из способов увидеть это. Предположим, что их два или более. Посмотрите на первые узлы на тех гамильтоновых путях, которые отличаются друг от друга; назовем их х и у. Это означает, что на одном пути x предшествует y, а на другом пути y предшествует x. Но это означает, что в графе есть цикл: мы можем перейти от x к y, используя подпуть первого гамильтонова пути, а затем мы можем перейти от y к x, используя подпуть второго гамильтонова пути. Однако это невозможно, потому что DAG не может иметь циклов.
Это означает, что утверждение, которое вы делаете, напрасно истинно: «если граф имеет два разных гамильтоновых пути, то он имеет два разных топологических порядка» верно, потому что антецедент всегда ложен.
person
templatetypedef
schedule
24.08.2015
Понятно, значит, топологическая сортировка невозможна на графе с циклом, верно?
- person Edmeral; 24.08.2015
@ Эдмерал Да, точно.
- person templatetypedef; 24.08.2015
