4446
правок
Дерево максимальной совместимости: различия между версиями
Материал из WEGA
Дерево максимальной совместимости (посмотреть исходный код)
Версия от 15:28, 5 декабря 2015
, 5 декабря 2015→Нотация
Irina (обсуждение | вклад) м (→Нотация) |
Irina (обсуждение | вклад) м (→Нотация) |
||
| Строка 24: | Строка 24: | ||
Дано: набор деревьев <math>\mathcal{T} \;</math> с идентичными множествами листьев. | Дано: набор деревьев <math>\mathcal{T} \;</math> с идентичными множествами листьев. | ||
Требуется: найти дерево, совместимое с <math>\mathcal{T} \;</math>, с наибольшим числом листьев. Такое дерево обозначается MCT(T), его пример приведен на рис. 2. | Требуется: найти дерево, совместимое с <math>\mathcal{T} \;</math>, с наибольшим числом листьев. Такое дерево обозначается <math>MCT(\mathcal{T}) \;</math>, его пример приведен на рис. 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 имеют несколько оптимальных решений. | ||
