4501
правка
Поддерево максимального соответствия (для трех или более деревьев): различия между версиями
Перейти к навигации
Перейти к поиску
м
Поддерево максимального соответствия (для трех или более деревьев) (посмотреть исходный код)
Версия от 16:22, 25 сентября 2015
, 25 сентября 2015→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 34: | Строка 34: | ||
Примечание 1. Если <math>mast(\overrightarrow{v}) > 0 \;</math>, то <math>\overrightarrow{v} = (lca^{T^1} (a, b), ..., lca^{T^k} (a, b)) \;</math> для некоторых меток листьев a, b, где <math>lca^{T^i} (a, b) \;</math> – самый низкий общий предок листьев с метками a и b в дереве V. | '''Примечание 1.''' Если <math>mast(\overrightarrow{v}) > 0 \;</math>, то <math>\overrightarrow{v} = (lca^{T^1} (a, b), ..., lca^{T^k} (a, b)) \;</math> для некоторых меток листьев a, b, где <math>lca^{T^i} (a, b) \;</math> – самый низкий общий предок листьев с метками a и b в дереве V. | ||
Кортеж <math>\overrightarrow{v} \;</math>, такой, что <math>\overrightarrow{v} = (lca^{T^1} (a, b), ..., lca^{T^k} (a, b)) \;</math> для некоторых <math>a, b \in A \;</math>, называется lca-кортежем. Согласно примечанию 1, достаточно вычислить значения mast только для lca-кортежей. Как и при использовании наивного подхода, <math>mast(\overrightarrow{v}) \;</math> вычисляется из значений mast других lca-кортежей, доминируемых <math>\overrightarrow{v} \;</math>. Еще одно важное наблюдение заключается в том, что для вычисления <math>mast(\overrightarrow{v}) \;</math> необходимы только некоторые lca-кортежи, доминируемые <math>\overrightarrow{v} \;</math>. Чтобы реализовать его, Фарах и коллеги определяют так называемое отношение истинного доминирования и показывают, что значение mast для любого lca-кортежа <math>\overrightarrow{v} \;</math> может быть вычислено из значений mast lca-кортежей, истинно доминируемых <math>\overrightarrow{v} \;</math>, и что отношение истинного доминирования имеет размер <math>O(n^3) \;</math>. | Кортеж <math>\overrightarrow{v} \;</math>, такой, что <math>\overrightarrow{v} = (lca^{T^1} (a, b), ..., lca^{T^k} (a, b)) \;</math> для некоторых <math>a, b \in A \;</math>, называется lca-кортежем. Согласно примечанию 1, достаточно вычислить значения mast только для lca-кортежей. Как и при использовании наивного подхода, <math>mast(\overrightarrow{v}) \;</math> вычисляется из значений mast других lca-кортежей, доминируемых <math>\overrightarrow{v} \;</math>. Еще одно важное наблюдение заключается в том, что для вычисления <math>mast(\overrightarrow{v}) \;</math> необходимы только некоторые lca-кортежи, доминируемые <math>\overrightarrow{v} \;</math>. Чтобы реализовать его, Фарах и коллеги определяют так называемое отношение истинного доминирования и показывают, что значение mast для любого lca-кортежа <math>\overrightarrow{v} \;</math> может быть вычислено из значений mast lca-кортежей, истинно доминируемых <math>\overrightarrow{v} \;</math>, и что отношение истинного доминирования имеет размер <math>O(n^3) \;</math>. | ||
| Строка 44: | Строка 44: | ||
Определение 1. v истинно доминирует | '''Определение 1.''' <math>\overrightarrow{v} \;</math> истинно доминирует <math>\overrightarrow{u} \;</math> (обозначается <math>\overrightarrow{u} < \overrightarrow{v} \;</math>), если <math>\overrightarrow{v} \;</math> доминирует <math>\overrightarrow{u} \;</math> по активному направлению <math>\overrightarrow{ \delta }</math> и существует другой кортеж, <math>\overrightarrow{w} \;</math>, также доминируемый <math>\overrightarrow{v} \;</math> по активному направлению <math>\overrightarrow{ \delta_{\bot}}</math>, совместимому с <math>\delta \;</math>. | ||