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

Деревья, которые здесь рассматриваются, представляют собой эволюционные (филогенетические) деревья. Такое дерево 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 ''уточняет'' дерево T' (<math>T \trianglerighteq T' \;</math>), если T может быть преобразовано в T путем коллапсирования некоторых его внутренних ребер (под коллапсированием ребра понимается его удаление и слияние его конечных точек). На рис. 1 приведены примеры таких отношений между деревьями.

Отметим, что дерево T, должным образом уточняющее дерево T0, согласуется со всей эволюционной историей T0, но при этом содержит дополнительную информацию, отсутствующую в T0: по меньшей мере одна вершина высокой степени из T заменяется в T несколькими вершинами меньших степеней, следовательно, T содержит больше событий видообразования, чем T0. Пусть имеется набор T = {T1, T2, ... : : Tk} входных деревьев с идентичными множествами листьев L. Мы говорим, что дерево T с листьями из L совместимо с T в том и только том случае, если 8Ti 2 T, T D TijL(T). Если существует дерево T, совместимое с T, такое, что L(T) = L, то набор T называется совместимым. Для решения вопроса, является ли набор деревьев совместимым, давно известны линейные алгоритмы (см., например, в [8]). Задача нахождения дерева максимальной совместимости представляет собой вариант естественной оптимизации данной задачи, позволяющий обрабатывать наборы несовместимых деревьев.