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

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