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

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

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

Определения

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

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

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

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

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

Некорневое двоичное дерево T можно преобразовать в полное корневое двоичное дерево (то есть корневое дерево, в котором каждый нелистовой узел имеет ровно два дочерних узла), выбрав корневое ребро e из T и поместив новый корневой узел в середине. e и направляя каждое ребро полученного разделенного дерева от корневого узла. И наоборот, любое полностью корневое двоичное дерево можно преобразовать в некорневое двоичное дерево, удалив корневой узел, заменив путь между двумя его дочерними элементами одним ненаправленным ребром и подавив ориентацию остальных ребер в графе. По этой причине  полнокорневых бинарных деревьев с n листьями ровно в 2 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 помеченных листьях представляет собой двойной факториал

${\displaystyle (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, показанному на изображении справа, длина пути между листьями 1 и 2 равна 2, тогда как длина пути между листьями 1 и 3 равна 3. Длина пути последовательность от заданного листа на фиксированном УБТ T кодирует длины путей от данного листа ко всем остальным. Например, если обратиться к UBT, показанному на изображении справа, последовательность длин путей из листа 1 равна . Набор последовательностей длины пути, связанных с листьями T, обычно называют набором последовательностей длины пути T ^[7] . ${\displaystyle p_{1,2}}$ ${\displaystyle p_{1,3}}$ ${\displaystyle p_{1}=(p_{1,2},p_{1,3},p_{1,4})=(2,3,3)}$

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

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

• ${\displaystyle p_{i,i}=0}$для всех ${\displaystyle i\in [1,n]}$
• ${\displaystyle p_{i,j}=p_{j,i}}$для всех ${\displaystyle i,j\in [1,n]:i\neq j}$
• ${\displaystyle p_{i,j}\leq p_{i,k}+p_{k,j}}$для всех ${\displaystyle i,j,k\in [1,n]:i\neq j\neq k}$
• ${\displaystyle \sum _{j=1}^{n}1/2^{p_{i,j}}=1/2}$для всех (что является адаптацией неравенства Крафта – Макмиллана ) ${\displaystyle i\in [1,n]}$
• ${\displaystyle \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] , а название «тройное дерево» более распространено. часто используется для обозначения корневого дерева с тремя дочерними элементами на узел .

Примечания

1. Furnas (1984).
2. См., например, Эппштейн (2009) для того же соответствия между кластеризацией и деревьями, но с использованием корневых двоичных деревьев вместо некорневых деревьев и, следовательно, включая произвольный выбор корневого узла.
3. Хенди и Пенни (1989).
4. Сент-Джон и др. (2003).
5. Робертсон и Сеймур (1991).
6. Болдинг, Бишоп и Каннингс (2007).
7. Катандзаро Д., Песенти Р., Уолси Л. (2020). «О сбалансированном многограннике минимальной эволюции». Дискретная оптимизация . 36 : 100570. doi : 10.1016/j.disopt.2020.100570 . S2CID  213389485.
8. Чумай и Гиббонс (1996).
9. Эксу (1996).
10. Чилибраси и Витаньи (2006).
11. Харари, Палмер и Робинсон (1992).
12. Пшитицка и Лармор (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 Transactions on Algorithms , 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.