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

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