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

Рассмотрим два корневых дерева <math>T_1 \;</math> и <math>T_2 \;</math> с n листьями у каждого. Внутренние вершины каждого дерева имеют не менее двух потомков. Листья каждого дерева помечены метками из одного и того же множества меток, ни одна конкретная метка в дереве не повторяется более одного раза. Дерево соответствия <math>T_1 \;</math> и <math>T_2 \;</math> определяется следующим образом. Пусть <math>L_1 \;</math> – подмножество листьев <math>T_1 \;</math>, а <math>L_2 \;</math> – подмножество тех листьев <math>T_2 \;</math>, которые имеют те же метки, что и листья в <math>L_1 \;</math>. Поддерево <math>T_1 \;</math>, порожденное <math>L_1 \;</math>, представляет собой поддерево соответствия <math>T_1 \;</math> и <math>T_2 \;</math> в том и только том случае, если оно изоморфно поддереву <math>T_2 \;</math>, порожденному <math>L_2 \;</math>. Задача нахождения поддерева максимального соответствия (Maximum Agreement Subtree, MAST) пытается найти наибольшее поддерево соответствия <math>T_1 \;</math> и <math>T_2 \;</math>.