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

Проиндексируем потомков каждой внутренней вершины любого дерева на произвольном пути. Пусть имеется пара <math>\overrightarrow{v}, \overrightarrow{w}</math> lca-кортежей, такая, что <math>\overrightarrow{w} \prec \overrightarrow{v} \;</math>. Соответствующее отношение доминирования ассоциирует ее с направлением <math>\overrightarrow{\delta}_{\overrightarrow{w} \prec \overrightarrow{v}} = (\delta_1, ..., \delta_k)</math>, по которому <math>\overrightarrow{w_i} \;</math> спускается от потомка <math>v_i \;</math>, индексированного с <math>\delta_i \;</math>. Пусть <math>v_i(j) \;</math> – потомок <math>v_i \;</math> с индексом <math>j \;</math>. Доминирование по направлению считается активным, если поддеревья с корнями в <math>v_1(\delta_1),..., v_к(\delta+k) \;</math> имеют по меньшей мере одну общую метку листа. Заметим, что каждая метка листа может обозначать только одно активное направление и, следовательно, каждый lca-кортеж может иметь не более и активных направлений доминирования. Два направления <math>\overrightarrow{\delta}_{\overrightarrow{w} \prec \overrightarrow{v}}</math> и <math>\overrightarrow{\delta}_{\overrightarrow{u} \prec \overrightarrow{v}}</math> называются совместимыми в том и только том случае, если векторы направлений различаются по всем координатам.