Супердерево максимального соответствия: различия между версиями

Пусть T – дерево, листья которого уникальным образом снабжены метками из набора таксонов S. Под уникальным образом мы понимаем то обстоятельство, что в T нет двух листьев с одинаковыми метками. Если дано подмножество S' множества S, то топологическое ограничение T согласно S' (обозначается T|S') представляет собой дерево, полученное в результате удаления из T всех вершин, не лежащих ни на одном пути из корня к листу из подмножества S', вместе с инцидентными им ребрами, и последующего сжатия каждого ребра между вершиной, имеющей только одного потомка, и самим этим потомком (см. рисунок). Для любого дерева T обозначим множество меток его листьев как <math>\Lambda (T) \;</math>.

Пусть T – исходное дерево с левой стороны. Тогда дерево справа T|{a, c, d} – это топологическое ограничение дерева T.