Дерево максимальной совместимости: различия между версиями
Перейти к навигации
Перейти к поиску
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) м (→Нотация) |
||
| Строка 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 имеют несколько оптимальных решений. | ||