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

Перейти к навигации Перейти к поиску
м
Строка 26: Строка 26:
Требуется: найти дерево, совместимое с <math>\mathcal{T} \;</math>, с наибольшим числом листьев. Такое дерево обозначается MCT(T), его пример приведен на рис. 2.
Требуется: найти дерево, совместимое с <math>\mathcal{T} \;</math>, с наибольшим числом листьев. Такое дерево обозначается MCT(T), его пример приведен на рис. 2.


Заметим, что <math>\forall \mathcal{T}, |MCT(mathcal{T})| \ge |MAST(mathcal{T})| \;</math>, и MCT эквивалентно MAST в случае, если входные деревья являются бинарными. Также стоит отметить, что задачи MCT и MAST имеют несколько оптимальных решений.
Заметим, что <math>\forall \mathcal{T}, |MCT(\mathcal{T})| \ge |MAST(\mathcal{T})| \;</math>, и MCT эквивалентно MAST в случае, если входные деревья являются бинарными. Также стоит отметить, что задачи MCT и MAST имеют несколько оптимальных решений.
   
   


4501

правка

Навигация