Аноним

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

Материал из WEGA
м
Строка 71: Строка 71:




Задача 2. Пусть D = f T1 ; T2; : ; Tk g – множество корневых неупорядоченных деревьев, в котором каждое дерево Ti имеет уникальные метки листьев, при этом множества меток листьев A(Tj) могут перекрываться. Задача нахождения супердерева максимальной совместимости (MCSP) заключается в построении дерева Q с уникальными метками листьев, с множеством меток листьев A(Q) С ST2D A(Tj), таким, что \A(Q)\ максимально и для каждого Ti 2 D топологическое ограничение поддерева Q0 дерева Q согласно A(Tj) уточняет топологическое ограничение Ti0 согласно Ti; иначе говоря, Ti0 может быть получено путем коллапсирования определенных ребер Qi0.
'''Задача 2'''. Пусть <math>D = \{ T_1, T_2, ..., T_k \} \;</math> – множество корневых неупорядоченных деревьев, в котором каждое дерево <math>T_i \;</math> имеет уникальные метки листьев, при этом множества меток листьев <math>\Lambda(T_i) \;</math> могут перекрываться. Задача нахождения супердерева максимальной совместимости (MCSP) заключается в построении дерева <math>Q \;</math> с уникальными метками листьев, с множеством меток листьев <math>\Lambda(Q) \subseteq \bigcup_{T_i \in D} \Lambda(T_i) \;</math>, таким, что <math>| \Lambda(Q) | \;</math> максимально и для каждого <math>T_i \in D \;</math> топологическое ограничение поддерева <math>Q_i' \;</math> дерева <math>Q \;</math> согласно <math>\Lambda(T_i) \;</math> уточняет топологическое ограничение <math>T'_i \;</math> согласно <math>T_i \;</math>; иначе говоря, <math>T'_i \;</math> может быть получено путем коллапсирования определенных ребер <math>Q'_i \;</math>.
 


== Открытые вопросы ==
== Открытые вопросы ==
4551

правка