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

Перейти к навигации Перейти к поиску
Строка 34: Строка 34:




Примечание 1. Если mast(vE) > 0, то v = (lcaT1 (a;b);::: lcaT (a; b)) для некоторых меток листьев a, b, где lcaT (a; b) – самый низкий общий предок листьев с метками 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.
Кортеж v, такой, что v = (lcaT1 (a; b)..: 1саг (a, b)) для некоторых a; b 2 A, называется lca-кортежем. Согласно примечанию 1, достаточно вычислить значения mast только для lca-кортежей. Как и при использовании наивного подхода, mast(vE) вычисляется из значений mast других lca-кортежей, доминируемых vE. Еще одно важное наблюдение заключается в том, что для вычисления mast(vE) необходимы только некоторые lca-кортежи, доминируемые v. Чтобы реализовать его, Фарах и коллеги определяют так называемое отношение истинного доминирования и показывают, что значение mast для любого lca-кортежа v может быть вычислено из значений mast lca-кортежей, истинно доминируемых v, и что отношение истинного доминирования имеет размер O(n3).
 
Кортеж <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>.




Источник — http://pco.iis.nsk.su/wega/index.php/Поддерево_максимального_соответствия_(для_трех_или_более_деревьев)