В корневом дереве у u и v есть общий потомок. Обязательно ли одна вершина предок другой? Верно ли это для…
Quant ResearchУровень: ПрактикаAncestor comparability
В корневом дереве у u и v есть общий потомок. Обязательно ли одна вершина предок другой? Верно ли это для произвольного DAG?
Подсказки
- Используйте единственность пути от корня.
- Для контрпримера DAG разрешите слияние путей.
Ответ
В дереве да: обе лежат на единственном пути от корня к потомку и упорядочены на нём. В DAG нет: ромб с ветвлением в u,v и слиянием в w даёт двух несравнимых предков w.
Источник и лицензия: Oscar Levin — Discrete Mathematics: An Open Introduction, 3rd edition · CC-BY-SA-4.0 · ответ: редакция Quantoros · перевод: Quantoros