Супердерево максимального соответствия: различия между версиями

Супердерево максимального соответствия (посмотреть исходный код)

61 байт добавлено , 2 ноября 2015

4551

правка

@@ Строка 22: / Строка 22: @@
-Лемма 1 ([8]). Для любого множества D = fT1;T2... Tkg корневых неупорядоченных деревьев с уникальными метками листьев, таких, что A(T\) = A(T2) = : : : = A(Ti), оптимальное решение задачи MASP для D является оптимальным решением задачи MAST для D, и наоборот.
+Лемма 1 ([8]). Для любого множества <math>D = \{ T_1, T_2, ..., T_k \} \;</math> корневых неупорядоченных деревьев с уникальными метками листьев, таких, что <math>\Lambda(T_1) = \Lambda(T_2) = ... = \Lambda(T_k) \;</math>, оптимальное решение задачи MASP для D является оптимальным решением задачи MAST для D, и наоборот.
@@ Строка 56: / Строка 56: @@
 Теорема 8 ([ ]). Пусть дано множество k бинарных деревьев T степени D с n различных меток листьев; их супердерево максимального соответствия может быть найдено за время O((kD)kD+3(2n)k).
 == Применение ==