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

Отметим, что дерево T, должным образом уточняющее дерево T', согласуется со всей эволюционной историей T', но при этом содержит дополнительную информацию, отсутствующую в T': по меньшей мере одна вершина высокой степени из T заменяется в T несколькими вершинами меньших степеней, следовательно, T содержит больше событий видообразования, чем T'. Пусть имеется набор <math>\mathcal{T} = {T_1, T_2, ..., T_k} \;</math> входных деревьев с идентичными множествами листьев L. Мы говорим, что дерево T с листьями из L ''совместимо'' с <math>\mathcal{T} \;</math> в том и только том случае, если <math>\forall \mathcal{T}_i \in \mathcal{T}, T \trianglerighteq T_i|L(T) \;</math>. Если существует дерево T, совместимое с T, такое, что L(T) = L, то набор T называется совместимым. Для решения вопроса, является ли набор деревьев совместимым, давно известны линейные алгоритмы (см., например, в [8]). Задача нахождения дерева максимальной совместимости представляет собой вариант естественной оптимизации данной задачи, позволяющий обрабатывать наборы несовместимых деревьев.

Задача 1. Дерево максимальной совместимости (MCT)

Дано: набор деревьев T с идентичными множествами листьев. Требуется: найти дерево, совместимое с T, с наибольшим числом листьев. Такое дерево обозначается MCT(T),

его пример приведен на рис. 2. Заметим, что 8T ; jMCT(T)j > jMAST(T)j, и MCT эквивалентно MAST в случае, если входные деревья являются бинарными. Также стоит отметить, что задачи MCT и MAST имеют несколько оптимальных решений.