Некореневе двійкове дерево

Некореневе двійкове дерево — це некореневе дерево, в якому кожна вершина має одного або трьох сусідів.

Кладограма у вигляді некореневого двійкового дерева, що представляє подібність і еволюційну історію родів актинобактерій

Визначення

Вільне дерево або некореневе дерево — це неорієнтований зв'язний граф без циклів. Вершини, що мають одного сусіда, називають листками дерева, інші вершини називають внутрішніми вузлами. Степінь вершини — це число її сусідів. У дереві з більш ніж однією дугою листки мають степінь 1. Неорієнтоване двійкове дерево — це вільне дерево, в якому всі внутрішні вузли мають степінь 3.

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

Крім того, можна розрізняти дерева, в яких усі вершини мають різні мітки, дерева, в яких позначено тільки листки, і дерева, в яких вузли не позначено. Некореневе двійкове дерево з n листками має n − 2 внутрішніх вузлів, так що мітки можна взяти з інтервалу від 1 до 2n − 1, якщо потрібно позначити всі вузли, або набору чисел від 1 до n якщо потрібно позначити тільки листки.

Пов'язані структури

Кореневі двійкові дерева

Некореневе двійкове дерево T можна перетворити на кореневе двійкове дерево (тобто кореневе дерево, в якому кожен нелистковий вузол має рівно два нащадки), вибравши кореневе ребро e дерева T, помістивши новий корінь посередині ребра e і спрямувавши ребра отриманого поділеного дерева від кореня. І навпаки: будь-яке кореневе дерево можна перетворити на некореневе двійкове дерево, видаливши кореневий вузол, замінивши шлях між двома його нащадками одним неорієнтованим ребром і прибравши напрямки дуг у графі. З цієї причини є рівно в 2n − 3 рази більше кореневих дерев із n листками, ніж некореневих двійкових деревами з n листками.

Ієрархічна кластеризація

Ієрархічну кластеризацію набору об'єктів можна формалізувати як максимальне сімейство множин об'єктів, у якому жодні дві множини не перетинаються (але деякі множини можуть міститися в інших). Тобто для двох множин S і T в сімействі або S і T не перетинаються, або одна множина міститься в іншій, і не можна додати жодної множини в сімейство, зберігши цю властивість. Якщо T — некореневе двійкове дерево, воно визначає ієрархічну кластеризацію листків цього дерева: для кожного ребра (u,v) з T існує кластер, що складається з листків, ближчих до u, ніж до v, і ці множини разом із порожньою множиною і множиною всіх листків утворюють максимальне сімейство без перетинів. З іншого боку, з будь-якого сімейства множин без перетинів над множиною з n елементів можна сформувати єдине некореневе двійкове дерево, яке має вузол для будь-якої трійки (A,B,C) неперетинних множин із сімейства, що покривають разом усі елементи.

Еволюційні дерева

Згідно з простими видами теорії еволюції, історію життя можна звести до філогенетичного дерева, в якому кожен вузол описує рід, листки представляють види, які існують нині, а ребра — зв'язки предок-нащадок між родами. Це дерево має природну орієнтацію ребер від батьківського виду до нащадків, а корінь є спільним предком видів, тому таке дерево є кореневим деревом. Однак деякі методи відновлення двійкових дерев можуть відновити лише вузли та ребра цього дерева, але не їх орієнтацію.

Наприклад, методи кладистики, такі як ^[en], використовують як дані множину двійкових властивостей, що описують ознаки цих родів. Ці методи шукають дерево, лисками якого є задані види, в якому внутрішні вузли також позначено деякими ознаками, і намагаються мінімізувати кількість випадків, у яких ознака присутня лише на одній вершині ребра у дереві. В ідеалі, кожна ознака може мати лише одне ребро з таким випадком. Зміна кореня дерева не змінює числа ребер з різними ознаками, так що методи, засновані на принципах найбільшої економії, не дозволяють визначити положення кореня дерева і створюють некореневе дерево, часто некореневе двійкове дерево.

Некореневі двійкові дерева можна також утворити методами реконструкції еволюційних дерев, заснованими на визначенні даних для кожних чотирьох родів листків, некореневого двійкового дерева, що описує еволюцію цих чотирьох видів, і методами, які для вимірювання відстані між деревами використовують ^[en].

Декомпозиція на гілки

Некореневі двійкові дерева використовують для визначення гілкової декомпозиції графів шляхом утворення некореневого двійкового дерева, листя якого представляють ребра даного графа. Тобто, гілкову декомпозицію можна розглядати як ієрархічну кластеризацію ребер грфа. Гілкова декомпозиція та відповідна числова величина, ширина галуження, тісно пов'язані з деревною шириною та утворюють основу для побудови ефективних алгоритмів динамічного програмування на графах.

Перерахування

Зважаючи на застосування некореневих двійкових дерев у ієрархічній кластеризації, найприроднішою задачею перерахування графів на некореневих двійкових деревах є підрахунок числа дерев з n позначеними листками та непозначеними внутрішніми вузлами. Некореневе двійкове дерево з n позначеними листками можна утворити, з'єднавши n-й листок із новим вузлом у середині будь-якого ребра некореневого двійкового дерева з n − 1 позначеними листками. Є 2n − 5 ребер, до яких можна додати n-ий вузол, отже, число дерев з n листками більше, ніж число дерев з n − 1 листками в 2n − 5 разів, так що число дерев із n позначеними листками дорівнює подвійному факторіалу

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

Число дерев з 2, 3, 4, 5, … позначеними листками дорівнює

1, 1, 3, 15, 105, 945, 10395, 135135, 2027025, 34459425, . . . (послідовність A001147 з Онлайн енциклопедії послідовностей цілих чисел, OEIS).

Альтернативні назви

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

Примітки

1. Furnas, 1984.
2. Див., наприклад, статтю Епштейна (Eppstein, 2009) про відповідність між кластеризаціями та деревами, але з використанням кореневих двійкових дерев замість некореневих дерев, а тому з довільним вибором кореневого вузла.
3. Hendy, Penny, 1989.
4. St. John, Warnow, Moret, Vawterd, 2003.
5. Robertson, Seymour, 1991.
6. Balding, Bishop, Cannings, 2007.
7. Czumaj, Gibbons, 1996.
8. Exoo, 1996.
9. Cilibrasi, Vitanyi, 2006.
10. Harary, Palmer, Robinson, 1992.
11. Przytycka, Larmore, 1994.

Література

• D. J. Balding, Martin J. Bishop, Christopher Cannings. Handbook of Statistical Genetics. — 3rd. — Wiley-Interscience, 2007. — Т. 1. — С. 502. — .
• Rudi Cilibrasi, Paul M.B. Vitanyi. A new quartet tree heuristic for hierarchical clustering. — 2006.
• Artur Czumaj, Alan Gibbons. Guthrie's problem: new equivalences and rapid reductions // Theoretical Computer Science. — 1996. — Т. 154, вип. 1. — С. 3–22. — DOI:10.1016/0304-3975(95)00126-3.
• David Eppstein. Squarepants in a tree: Sum of subtree clustering and hyperbolic pants decomposition // ACM Transactions on Algorithms. — 2009. — Т. 5, вип. 3. — С. 1–24. — arXiv:cs.CG/0604034. — DOI:10.1145/1541885.1541890.
• Geoffrey Exoo. A simple method for constructing small cubic graphs of girths 14, 15, and 16 // Electronic Journal of Combinatorics. — 1996. — Т. 3, вип. 1.
• George W. Furnas. The generation of random, binary unordered trees // Journal of Classification. — 1984. — Т. 1, вип. 1. — С. 187–233. — DOI:10.1007/BF01890123.
• Frank Harary, E.M. Palmer, R.W. Robinson. Counting free binary trees admitting a given height // Journal of Combinatorics, Information, and System Sciences. — 1992. — Т. 17. — С. 175–181.
• Michael D. Hendy, David Penny. A framework for the quantitative study of evolutionary trees // Systematic Biology. — 1989. — Т. 38, вип. 4. — С. 297–309. — DOI:10.2307/2992396.
• Teresa M. Przytycka, Lawrence L. Larmore. The optimal alphabetic tree problem revisited // Proc. 21st International Colloquium on Automata, Languages and Programming (ICALP '94). — Springer-Verlag, 1994. — Т. 820. — С. 251–262. — (Lecture Notes in Computer Science) — DOI:10.1007/3-540-58201-0_73.
• Neil Robertson, Paul D. Seymour. Graph minors. X. Obstructions to tree-decomposition // Journal of Combinatorial Theory. — 1991. — Т. 52, вип. 2. — С. 153–190. — DOI:10.1016/0095-8956(91)90061-N.
• Katherine St. John, Tandy Warnow, Bernard M. E. Moret, Lisa Vawterd. Performance study of phylogenetic methods: (unweighted) quartet methods and neighbor-joining // Journal of Algorithms. — 2003. — Т. 48, вип. 1. — С. 173–193. — DOI:10.1016/S0196-6774(03)00049-X.