4446
правок
Дерево максимальной совместимости: различия между версиями
Материал из WEGA
Дерево максимальной совместимости (посмотреть исходный код)
Версия от 15:26, 5 декабря 2015
, 5 декабря 2015→Нотация
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 имеют несколько оптимальных решений. | ||
