К содержанию
Quantoros

В корневом дереве у 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

Похожие вопросы