Поддерево максимального соответствия (для трех или более деревьев): различия между версиями

Задача нахождения поддерева максимального соответствия для k деревьев (k-MAST) представляет собой обобщение подобной же задачи для двух деревьев (Maximum Agreement Subtree, MAST). Рассмотрим кортеж из k корневых деревьев с помеченными листьями (T1; T2 : : : Tk). Пусть A = fa1; a2..: ang – множество меток листьев. Любое подмножество B Q A уникальным образом определяет так называемое топологическое ограничение T|B дерева T согласно B. А именно, T|B является топологическим поддеревом T, натянутым на все листья, помеченные элементами из B, и самых низких общих предков всех пар этих листьев. Отношение наследования в T|B определяется таким образом, чтобы оно было согласовано с отношением наследования в T. Подмножество B множества A, такое, что T1 jB..: ; Tk jB являются изоморфными, называется множеством соответствия.