Некорневое двоичное дерево

Кладограмма видов в виде бинарного дерева без корней, показывающая сходства и историю эволюции актинобактерий .

В математике и информатике некорневое двоичное дерево — это некорневое дерево , в котором каждая вершина имеет одного или трех соседей.

Определения

или Свободное дерево некорневое дерево — это связный неориентированный граф без циклов . Вершины с одним соседом являются листьями дерева, а остальные вершины — внутренними узлами дерева. Степень ; вершины — это количество ее соседей в дереве с более чем одним узлом листьями являются вершины степени один. Некорневое двоичное дерево — это свободное дерево, в котором все внутренние узлы имеют степень ровно третью.

В некоторых приложениях может иметь смысл различать подтипы некорневых бинарных деревьев: плоское вложение дерева можно исправить, указав циклический порядок ребер в каждой вершине, превратив его в плоское дерево . В информатике бинарные деревья часто имеют корни и упорядочены, когда они используются в качестве структур данных , но в приложениях неукорененных бинарных деревьев в иерархической кластеризации и эволюционной реконструкции деревьев более распространены неупорядоченные деревья. ^[1]

Кроме того, можно различать деревья, в которых все вершины имеют разные метки, деревья, в которых помечены только листья, и деревья, в которых узлы не помечены. В некорневом двоичном дереве с n листьями будет n - 2 внутренних узлов, поэтому метки можно брать из набора целых чисел от 1 до 2 n - 1, когда нужно пометить все узлы, или из набора целых чисел. от 1 до n , когда необходимо пометить только листья. ^[1]

Связанные структуры

Укорененные бинарные деревья

Некорневое двоичное дерево T можно преобразовать в полное корневое двоичное дерево (то есть корневое дерево, в котором каждый нелистовой узел имеет ровно два дочерних узла), выбрав корневое ребро e из T и поместив новый корневой узел в середине. e и направляя каждое ребро полученного разделенного дерева от корневого узла. И наоборот, любое полностью корневое двоичное дерево можно преобразовать в некорневое двоичное дерево, удалив корневой узел, заменив путь между двумя его дочерними элементами одним ненаправленным ребром и подавив ориентацию остальных ребер в графе. По этой причине листьями ровно в 2 n полнокорневых бинарных деревьев с n -3 раза больше , чем некорневых бинарных деревьев с n листьями. ^[1]

Иерархическая кластеризация

Иерархическую кластеризацию набора объектов можно формализовать как максимальное семейство множеств объектов, в котором никакие два множества не пересекаются. То есть для каждых двух множеств S и T в семействе либо S и T не пересекаются, либо одно является подмножеством другого, и при сохранении этого свойства в семейство больше нельзя добавлять множества. Если T — некорневое двоичное дерево, оно определяет иерархическую кластеризацию своих листьев: для каждого ребра ( u , v ) в T существует кластер, состоящий из листьев, которые ближе к u, чем к v , и эти множества вместе с пустое множество и множество всех листьев образуют максимальное непересекающееся семейство. И наоборот, из любого максимального непересекающегося семейства множеств над набором из n элементов можно сформировать уникальное некорневое двоичное дерево, которое имеет узел для каждой тройки ( A , B , C ) непересекающихся множеств в семействе, которые вместе покрывают все элементов. ^[2]

Эволюционные деревья

Согласно простым формам теории эволюции , историю жизни можно резюмировать как филогенетическое дерево , в котором каждый узел описывает вид, листья представляют виды, существующие сегодня, а ребра представляют отношения предков-потомков между видами. Это дерево имеет естественную ориентацию от предков к потомкам и корень у общего предка вида, поэтому является укорененным деревом. Однако некоторые методы реконструкции бинарных деревьев позволяют восстановить только узлы и ребра этого дерева, но не их ориентации.

Например, кладистические методы, такие как максимальная экономия, используют в качестве данных набор бинарных атрибутов, описывающих особенности вида. Эти методы ищут дерево с заданным видом в качестве листьев, в котором внутренние узлы также помечены признаками, и пытаются минимизировать количество раз, когда какой-либо признак присутствует только в одной из двух конечных точек ребра в дереве. В идеале каждый объект должен иметь только одно ребро. Изменение корня дерева не меняет этого количества различий ребер, поэтому методы, основанные на экономии, не способны определить местоположение корня дерева и создают некорневое дерево, часто некорневое двоичное дерево. ^[3]

Некорневые бинарные деревья также создаются с помощью методов построения эволюционных деревьев на основе данных квартета, определяющих для каждых четырех видов листьев некорневое двоичное дерево, описывающее эволюцию этих четырех видов, а также методами, которые используют квартетное расстояние для измерения расстояния между деревьями. ^[4]

Ветвевая декомпозиция

Некорневые двоичные деревья также используются для определения разложений графов по ветвям путем формирования некорневого двоичного дерева, листья которого представляют собой ребра данного графа. То есть ветвевую декомпозицию можно рассматривать как иерархическую кластеризацию ребер графа. Декомпозиция ветвей и связанная с ней числовая величина, ширина ветвей, тесно связаны с шириной дерева и составляют основу эффективных динамического программирования на графах. алгоритмов ^[5]

Перечисление

Из-за их применения в иерархической кластеризации наиболее естественной задачей перечисления графов некорневых двоичных деревьев является подсчет количества деревьев с n помеченными листьями и неразмеченными внутренними узлами. Некорневое двоичное дерево на n помеченных листьях можно сформировать путем соединения n -го листа с новым узлом в середине любого из ребер некорневого двоичного дерева на n - 1 помеченных листьях. Существует 2 n − 5 ребер, к которым n- можно прикрепить й узел; следовательно, количество деревьев на n листьях больше количества деревьев на n - 1 листьях в 2 n - 5 раз. Таким образом, количество деревьев на n помеченных листьях представляет собой двойной факториал

(2n-5)!!={\frac {(2n-4)!}{(n-2)!2^{n-2}}}.

^[6]

Количество деревьев на 2, 3, 4, 5, ... помеченных листьях равно

1, 1, 3, 15, 105, 945, 10395, 135135, 2027025, 34459425, ... (последовательность A001147 в OEIS ).

Фундаментальные равенства

Длина пути от листа к листу в фиксированном некорневом двоичном дереве (UBT) T кодирует количество ребер, принадлежащих уникальному пути в T, соединяющему данный лист с другим листом. Например, если обратиться к UBT, показанному на изображении справа, длина пути $p_{1,2}$ между листьями 1 и 2 равна 2, тогда как длина пути $p_{1,3}$ между листьями 1 и 3 равна 3. Последовательность длин путей от данного листа на фиксированном UBT T кодирует длины путей от данного листа ко всем остальным. Например, если обратиться к UBT, показанному на изображении справа, последовательность длин путей из листа 1 равна $p_{1}=(p_{1,2},p_{1,3},p_{1,4})=(2,3,3)$ . Набор последовательностей длины пути, связанных с листьями T, обычно называют коллекцией последовательностей длины пути T. ^[7].

Даниэле Катандзаро, Рафаэле Пезенти и Лоуренс Вулси показали ^[7] что коллекция последовательностей длин путей, кодирующая данный UBT с n листьями, должна удовлетворять определенным равенствам, а именно

$p_{i,i}=0$ для всех $i\in [1,n]$
$p_{i,j}=p_{j,i}$ для всех $i,j\in [1,n]:i\neq j$
$p_{i,j}\leq p_{i,k}+p_{k,j}$ для всех $i,j,k\in [1,n]:i\neq j\neq k$
$\sum _{j=1}^{n}1/2^{p_{i,j}}=1/2$ для всех $i\in [1,n]$ (который является адаптацией неравенства Крафта – Макмиллана )
$\sum _{i=1}^{n}\sum _{j=1}^{n}p_{i,j}/2^{p_{i,j}}=2n-3$ , также называемый филогенетическим многообразием . ^[7]

Доказано, что эти равенства необходимы и независимы для набора длин путей для кодирования UBT с n листьями. ^[7] В настоящее время неизвестно, достаточны ли они.

Альтернативные названия

Некорневые бинарные деревья также называют свободными двоичными деревьями . ^[8] кубические деревья , ^[9] тройные деревья ^[5] и неукорененные троичные деревья . ^[10] Однако название «свободное двоичное дерево» также применялось к некорневым деревьям, которые могут иметь узлы второй степени. ^[11] и к корневым двоичным деревьям с неупорядоченными дочерними элементами, ^[12] а название «тройное дерево» чаще используется для обозначения корневого дерева с тремя дочерними элементами на узел .

Примечания

^ Jump up to: Перейти обратно: ^а ^б ^с Фурнас (1984) .
^ См., например, Эппштейн (2009) для того же соответствия между кластеризацией и деревьями, но с использованием корневых двоичных деревьев вместо некорневых деревьев и, следовательно, включая произвольный выбор корневого узла.
^ Хенди и Пенни (1989) .
^ Сент-Джон и др. (2003) .
^ Jump up to: Перейти обратно: ^а ^б Робертсон и Сеймур (1991) .
^ Болдинг, Бишоп и Каннингс (2007) .
^ Jump up to: Перейти обратно: ^а ^б ^с ^д Катандзаро Д., Пезенти Р., Уолси Л. (2020). «О сбалансированном многограннике минимальной эволюции» . Дискретная оптимизация . 36 : 100570. doi : 10.1016/j.disopt.2020.100570 . S2CID 213389485 .
^ Чумай и Гиббонс (1996) .
^ Исход (1996) .
^ Чилибраси и Витаньи (2006) .
^ Харари, Палмер и Робинсон (1992) .
^ Пшитицка и Лармор (1994) .

Ссылки

Балдинг, диджей; Бишоп, Мартин Дж.; Каннингс, Кристофер (2007), Справочник по статистической генетике , том. 1 (3-е изд.), Wiley-Interscience, с. 502, ISBN 978-0-470-05830-5 .
Чилибраси, Руди; Витаньи, Пол МБ (2006). «Новая эвристика квартетного дерева для иерархической кластеризации». arXiv : cs/0606048 . .
Чумай, Артур; Гиббонс, Алан (1996), «Проблема Гатри: новые эквивалентности и быстрые сокращения», Theoretical Computer Science , 154 (1): 3–22, doi : 10.1016/0304-3975(95)00126-3 .
Эппштейн, Дэвид (2009), «Квадратные штаны в дереве: сумма кластеризации поддеревьев и разложение гиперболических штанов», Транзакции ACM по алгоритмам , 5 (3): 1–24, arXiv : cs.CG/0604034 , doi : 10.1145/1541885.1541890 , S2CID 2434 .
Эксу, Джеффри (1996), «Простой метод построения небольших кубических графов с обхватами 14, 15 и 16» (PDF) , Electronic Journal of Combinatorics , 3 (1): R30, doi : 10.37236/1254 .
Фурнас, Джордж В. (1984), «Генерация случайных двоичных неупорядоченных деревьев», Journal of Classification , 1 (1): 187–233, doi : 10.1007/BF01890123 , S2CID 121121529 .
Харари, Фрэнк ; Палмер, EM; Робинсон, Р.В. (1992), «Подсчет свободных бинарных деревьев, допускающих заданную высоту» (PDF) , Журнал комбинаторики, информации и системных наук , 17 : 175–181 .
Хенди, Майкл Д.; Пенни, Дэвид (1989), «Основы количественного изучения эволюционных деревьев», Systematic Biology , 38 (4): 297–309, doi : 10.2307/2992396 , JSTOR 2992396
Пшитицка, Тереза М .; Лармор, Лоуренс Л. (1994), «Возвращение к проблеме оптимального алфавитного дерева», Proc. 21-й международный коллоквиум по автоматам, языкам и программированию (ICALP '94) , Конспекты лекций по информатике, том. 820, Springer-Verlag, стр. 251–262, номер документа : 10.1007/3-540-58201-0_73 .
Робертсон, Нил ; Сеймур, Пол Д. (1991), «Минорные графы. X. Препятствия к разложению дерева», Journal of Combinatorial Theory , 52 (2): 153–190, doi : 10.1016/0095-8956(91)90061-N .
Сент-Джон, Кэтрин; Варноу, Тэнди ; Море, Бернар М.Э .; Вотерд, Лиза (2003), «Исследование эффективности филогенетических методов: (невзвешенные) квартетные методы и объединение соседей» (PDF) , Journal of Algorithms , 48 (1): 173–193, doi : 10.1016/S0196-6774(03) )00049-X , S2CID 5550338 .

[f84-1] Jump up to: Перейти обратно: ^а ^б ^с Фурнас (1984) .

[2] См., например, Эппштейн (2009) для того же соответствия между кластеризацией и деревьями, но с использованием корневых двоичных деревьев вместо некорневых деревьев и, следовательно, включая произвольный выбор корневого узла.

[3] Хенди и Пенни (1989) .

[4] Сент-Джон и др. (2003) .

[rs91-5] Jump up to: Перейти обратно: ^а ^б Робертсон и Сеймур (1991) .

[6] Болдинг, Бишоп и Каннингс (2007) .

[On_the_Balanced_Minimum_Evolution_P-7] Jump up to: Перейти обратно: ^а ^б ^с ^д Катандзаро Д., Пезенти Р., Уолси Л. (2020). «О сбалансированном многограннике минимальной эволюции» . Дискретная оптимизация . 36 : 100570. doi : 10.1016/j.disopt.2020.100570 . S2CID 213389485 .

[8] Чумай и Гиббонс (1996) .

[9] Исход (1996) .

[10] Чилибраси и Витаньи (2006) .

[11] Харари, Палмер и Робинсон (1992) .

[12] Пшитицка и Лармор (1994) .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]