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

Деревья, которые здесь рассматриваются, представляют собой эволюционные (филогенетические) деревья. Такое дерево T имеет множество листьев L(T), находящихся во взаимно-однозначном соответствии с множеством меток, и является либо корневым (в этом случае все внутренние вершины имеют не менее двух потомков), либо некорневым (в этом случае внутренние вершины имеют степень не ниже трех). Размером |T| дерева T является число его листьев. Пусть дано множество меток L и дерево T; ограничение T согласно L, обозначаемое T|L, представляет собой дерево, полученное следующим образом: взять наименьший порожденный подграф T, соединяющий листья с метками из L \ L(T), а затем удалить две некорневых вершины любой степени, чтобы дерево стало гомеоморфно неприводимым. Два дерева T и T0 являются изоморфными (T = T0) в том и только том случае, если существует изоморфизм графов T 7! T0, сохраняющий метки листьев (и корень, если оба дерева были корневыми). Дерево T уточняет дерево T0 (T D T0), если T может быть преобразовано в T путем коллапсирования некоторых его внутренних ребер (под коллапсированием ребра понимается его удаление и слияние его конечных точек). На рис. 1 приведены примеры таких отношений между деревьями.