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

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

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

Определения

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

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

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

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

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

Некорневое бинарное дерево T может быть преобразовано в полное корневое бинарное дерево (то есть корневое дерево, в котором каждый нелистовой узел имеет ровно два потомка), выбрав корневое ребро e из T , поместив новый корневой узел в середину e и направив каждое ребро полученного подразделенного дерева от корневого узла. И наоборот, любое полное корневое бинарное дерево может быть преобразовано в некорневое бинарное дерево, удалив корневой узел, заменив путь между его двумя потомками одним ненаправленным ребром и подавив ориентацию оставшихся ребер в графе. По этой причине существует ровно в 2 n  −3 раза больше полных корневых бинарных деревьев с n листьями, чем некорневых бинарных деревьев с 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. Последовательность длин путей от данного листа на фиксированном UBT 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. Фурнас (1984).
2. См., например, Эппштейн (2009) о том же соответствии между кластеризацией и деревьями, но с использованием корневых бинарных деревьев вместо некорневых деревьев и, следовательно, с включением произвольного выбора корневого узла.
3. Хенди и Пенни (1989).
4. Сент-Джон и др. (2003).
5. Робертсон и Сеймур (1991).
6. Болдинг, Бишоп и Каннингс (2007).
7. Catanzaro D, Pesenti R, Wolsey L (2020). "О сбалансированном минимальном эволюционном многограннике". Дискретная оптимизация . 36 : 100570. doi : 10.1016/j.disopt.2020.100570 . S2CID  213389485.
8. Чумай и Гиббонс (1996).
9. Эксу (1996).
10. Чилибраси и Витаний (2006).
11. Харари, Палмер и Робинсон (1992).
12. Пшитицкая и Лармор (1994).

Ссылки

• Болдинг, DJ; Бишоп, Мартин Дж.; Каннингс, Кристофер (2007), Справочник по статистической генетике , т. 1 (3-е изд.), Wiley-Interscience, стр. 502, ISBN 978-0-470-05830-5.
• Cilibrasi, Rudi; Vitanyi, Paul MB (2006). «Новая эвристика квартетного дерева для иерархической кластеризации». arXiv : cs/0606048 ..
• Чумай, Артур; Гиббонс, Алан (1996), «Проблема Гатри: новые эквивалентности и быстрые сокращения», Теоретическая информатика , 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) , Электронный журнал комбинаторики , 3 (1): R30, doi : 10.37236/1254.
• Фурнас, Джордж У. (1984), «Генерация случайных, бинарных неупорядоченных деревьев», Журнал классификации , 1 (1): 187–233, doi :10.1007/BF01890123, S2CID  121121529.
• Харари, Фрэнк ; Палмер, Э.М.; Робинсон, Р.У. (1992), «Подсчет свободных двоичных деревьев, допускающих заданную высоту» (PDF) , Журнал комбинаторики, информации и системных наук , 17 : 175–181.
• Хенди, Майкл Д.; Пенни, Дэвид (1989), «Структура для количественного изучения эволюционных деревьев», Systematic Biology , 38 (4): 297–309, doi :10.2307/2992396, JSTOR  2992396
• Przytycka, Teresa M. ; Larmore, Lawrence L. (1994), "Повторный взгляд на проблему оптимального алфавитного дерева", Proc. 21st International Colloquium on Automata, Languages ​​and Programming (ICALP '94) , Lecture Notes in Computer Science, vol. 820, Springer-Verlag, стр. 251–262, doi :10.1007/3-540-58201-0_73, ISBN 978-3-540-58201-4.
• Робертсон, Нил ; Сеймур, Пол Д. (1991), «Миноры графа. X. Препятствия к декомпозиции дерева», Журнал комбинаторной теории , 52 (2): 153–190, doi : 10.1016/0095-8956(91)90061-N.
• Сент-Джон, Кэтрин; Уорнов, Тэнди ; Морет, Бернард М.Е.; Вотерд, Лиза (2003), «Исследование эффективности филогенетических методов: (невзвешенные) квартетные методы и метод объединения соседей» (PDF) , Журнал алгоритмов , 48 (1): 173–193, doi :10.1016/S0196-6774(03)00049-X, S2CID  5550338.