4446
правок
Дерево максимальной совместимости: различия между версиями
Материал из WEGA
Дерево максимальной совместимости (посмотреть исходный код)
Версия от 15:00, 5 декабря 2015
, 5 декабря 2015→Нотация
Irina (обсуждение | вклад) м (→Нотация) |
Irina (обсуждение | вклад) |
||
| Строка 20: | Строка 20: | ||
Задача 1. Дерево максимальной совместимости ( | Задача 1. Дерево максимальной совместимости (MCT) | ||
Дано: набор деревьев <math>\mathcal{T} \;</math> с идентичными множествами листьев. | Дано: набор деревьев <math>\mathcal{T} \;</math> с идентичными множествами листьев. | ||
| Строка 29: | Строка 29: | ||
[[Файл: | [[Файл:MCT2.jpg]] | ||
Дерево максимальной совместимости, рис. 2 | Дерево максимальной совместимости, рис. 2 | ||
Набор из двух несовместимых входных деревьев | Набор из двух несовместимых входных деревьев <math>{T_1, T_2} \;</math> и их дерево максимальной совместимости <math>T = MCT(T_1, T_2) \;</math>. Если удалить лист d, входные деревья станут совместимыми, поскольку L(Т) = {a, b, c, d}. Здесь дерево T строго уточняет <math>T_2\;</math> , ограниченное согласно L(T), что выражается тем обстоятельством, что потомки вершины дерева <math>T_2 \;</math> (изображенной серым цветом) распределены между несколькими связанными вершинами T (также серого цвета). Отметим также, что <math>|MCT(T_1, T_2)| > |MAST(T_1, T_2)| \;</math>. | ||
== Основные результаты == | == Основные результаты == | ||
