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

Проиндексируем потомков каждой внутренней вершины любого дерева на произвольном пути. Пусть имеется пара <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>. Доминирование по направлению считается активным, если поддеревья с корнем в vi(<5i),... v Ук(8к) имеют по меньшей мере одну общую метку листа. Заметим, что каждая метка листа может обозначать только одно активное направление и, следовательно, каждый lca-кортеж может иметь не более и активных направлений доминирования. Два направления 8^^ и 8^^ называются совместимыми в том и только том случае, если векторы направлений различаются по всем координатам.