Некорневое двоичное дерево - Unrooted binary tree

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

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

Определения

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

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

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

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

Бинарные деревья с корнями

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

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

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

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

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

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

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

Ветвь-разложение

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

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

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

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

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

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

Длина пути от листа к листу на фиксированном некорневом двоичном дереве (UBT) T кодирует количество ребер, принадлежащих уникальному пути в T, соединяющему данный лист с другим листом. Например, если обратиться к UBT, показанному на изображении справа, длина пути между листами 1 и 2 равна 2, тогда как длина пути между листами 1 и 3 равна 3. Длина пути последовательность из данного листа на фиксированном UBT T кодирует длины путей от данного листа ко всем оставшимся. Например, если обратиться к UBT, показанному на изображении справа, последовательность длины пути из листа 1 будет . Набор последовательностей длины пути, связанных с листами T, обычно называется набором последовательностей длины пути T.

Пример бинарного дерева без корней с четырьмя листьями

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

  • для всех
  • для всех
  • для всех
  • для всех (что является адаптацией неравенства Крафт-Макмиллана )
  • , также называемое филогенетическим многообразием .

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

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

Некорневых бинарные деревья называют также бесплатные бинарные деревья , кубические деревья , тройные деревья и некорневых тройные деревья ,. Однако имя «свободное двоичное дерево» также применялось к некорневым деревьям, которые могут иметь узлы второй степени, и к корневым двоичным деревьям с неупорядоченными дочерними элементами, а имя «троичное дерево» чаще используется для обозначения корневого дерева с тремя детей на узел .

Заметки

Рекомендации