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

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