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

Термины «порожденное поддерево» и «изоморфизм» нуждаются в определении. Интуитивно поддерево T, порожденное подмножеством L листьев T, представляет собой топологическое поддерево T, элементами которого являются только листья из L, сохраняющее информацию о ветвлении, относящуюся к L. Более формально, для любых двух листьев a, b дерева T обозначим за <math>lca_T (a, b) \; </math> их самого низкого общего предка в T. Если a = b, <math>lca_T(a, b) = a \; </math>. Поддерево U дерева T, порожденное подмножеством листьев L, представляет собой дерево с множеством листьев L и множеством внутренних вершин <math>\{ lca_T(a, b) | a, b \in L \} \;</math>, наследующее отношение родства от T, то есть для всех <math>a, b \in L, lca_U(a, b) = lca_T(a, b) \;</math>.

Интуитивно два дерева представляются изоморфными, если потомки каждой вершины могут быть переупорядочены таким образом, что метки листьев в каждом дереве идут в одном и том же порядке и формы двух деревьев становятся идентичными. Формально два дерева <math>U_1 \;</math> и <math>U_2 \;</math> с одним и тем же набором меток листьев называются изоморфными, если существует взаимно однозначное отображение <math>\mu \;</math> между их вершинами, отображающее листья на листья с теми же метками, такое, что для любых двух различных листьев <math>a, b \in U_1</math>, <math>\mu (lca_U1 (a, b)) = lca_U2 (\mu (a), \mu (b))</math>.