4817
правок
Поддерево максимального соответствия: различия между версиями
Перейти к навигации
Перейти к поиску
Поддерево максимального соответствия (посмотреть исходный код)
Версия от 08:46, 22 сентября 2015
, 22 сентября 2015→Постановка задачи
Irina (обсуждение | вклад) (Новая страница: «== Постановка задачи == Рассмотрим два корневых дерева T1 и T2 с n листьями у каждого. Внутре…») |
Irina (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
== Постановка задачи == | == Постановка задачи == | ||
Рассмотрим два корневых дерева | Рассмотрим два корневых дерева <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>. | ||
| Строка 8: | Строка 8: | ||
Интуитивно два дерева представляются изоморфными, если потомки каждой вершины могут быть переупорядочены таким образом, что метки листьев в каждом дереве идут в одном и том же порядке и формы двух деревьев становятся идентичными. Формально два дерева U1 и U2 с одним и тем же набором меток листьев называются изоморфными, если существует взаимно однозначное отображение fi между их вершинами, отображающее листья на листья с теми же метками, такое, что для любых двух различных листьев a, b of U1, /i(lcaиДв, b)) = \caU2(fi(a), ji{b)). | Интуитивно два дерева представляются изоморфными, если потомки каждой вершины могут быть переупорядочены таким образом, что метки листьев в каждом дереве идут в одном и том же порядке и формы двух деревьев становятся идентичными. Формально два дерева U1 и U2 с одним и тем же набором меток листьев называются изоморфными, если существует взаимно однозначное отображение fi между их вершинами, отображающее листья на листья с теми же метками, такое, что для любых двух различных листьев a, b of U1, /i(lcaиДв, b)) = \caU2(fi(a), ji{b)). | ||
== Основные результаты == | == Основные результаты == | ||