4446
правок
Поддерево максимального соответствия (для трех или более деревьев): различия между версиями
Материал из WEGA
Поддерево максимального соответствия (для трех или более деревьев) (посмотреть исходный код)
Версия от 14:37, 25 сентября 2015
, 25 сентября 2015→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 41: | Строка 41: | ||
Отношение истинного доминирования | Отношение истинного доминирования | ||
Проиндексируем потомков каждой внутренней вершины любого дерева на произвольном пути. Пусть имеется пара | Проиндексируем потомков каждой внутренней вершины любого дерева на произвольном пути. Пусть имеется пара <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^^ называются совместимыми в том и только том случае, если векторы направлений различаются по всем координатам. | ||
