Знаем, че ако имаме хамилтонова пътека в DAG, че топологичното сортиране ще бъде уникално, но какво ще стане, ако имаме множество хамилтонови пътеки, няма ли това да означава, че може да има множество топологични сортирания: различно за всяко от тях пътеки?
Множество хамилтонови пътища и топологично сортиране
comment
Това само математически въпрос ли е?
- person BSMP schedule 24.08.2015
comment
Четох за топологично сортиране и се обърках относно връзката, която има с хамилтоновите пътища.
- person Edmeral schedule 24.08.2015
Отговори (1)
Всеки DAG има или нула хамилтонова пътека, или една хамилтонова пътека. Ето един начин да видите това. Да предположим, че има две или повече. Погледнете първите възли на тези хамилтонови пътища, които се различават един от друг; нека ги наречем x и y. Това означава, че в единия път x идва преди y, а в другия път y идва преди x. Но това означава, че има цикъл в графиката: можем да преминем от x към y, използвайки подпът на първия хамилтонов път и след това можем да отидем от y до x, използвайки подпът на втория хамилтонов път. Това обаче е невъзможно, защото DAG не могат да имат цикли.
Това означава, че твърдението, което правите, е безсмислено вярно - "ако една графика има две различни хамилтонови пътеки, тогава тя има две различни топологични подреждания" е вярно, защото антецедентът винаги е неверен.
person
templatetypedef
schedule
24.08.2015
Разбирам, така че топологично сортиране не е възможно на графика, която има цикъл, нали?
- person Edmeral; 24.08.2015
@Edmeral Да, точно така.
- person templatetypedef; 24.08.2015
