Unrooted binary tree: Difference between revisions

Revision as of 13:40, 5 June 2020

Latest revision as of 05:59, 2 June 2025

(14 intermediate revisions by 10 users not shown)

Line 1:

[[File:TreeActinobacteria.svg|thumb|360px|A [[cladogram]] in the form of an unrooted binary tree, representing the similarities and evolutionary history among species of [[Actinomycetota|actinobacteria]].]]

In mathematics and computer science, an '''unrooted binary tree''' is an [[free tree|unrooted tree]] in which each [[vertex (graph theory)|vertex]] has either one or three neighbors.

Line 34:

==Fundamental Equalities==

The leaf-to-leaf path-length on a fixed Unrooted Binary Tree (UBT) T encodes the number of edges belonging to the unique path in T connecting a given leaf to another leaf. For example, by referring to the UBT shown in the image on the right, the path-length <math> p_{1,2} </math> between the leaves 1 and 2 is equal to 2 whereas the path-length <math> p_{1,3} </math> between the leaves 1 and 3 is equal to 3. The path-length sequence from a given leaf on a fixed UBT T encodes the lengths of the paths from the given leaf to all the remaining ones. For example, by referring to the UBT shown in the image on the right, the path-length sequence from the leaf 1 is <math> p_1=(p_{1,2}, p_{1,3}, p_{1,4})=(2,3,3) </math>. The set of path-length sequences associated to the leaves of T is usually referred to as the ''path-length sequence collection'' of T <ref name="On the Balanced Minimum Evolution P">{{cite journal | vauthors = Catanzaro D, Pesenti R, Wolsey L | title = On the Balanced Minimum Evolution Polytope | journal = Discrete Optimization | volume = 36 | pagesdate = 1-332020 | datepage = 100570 | doi = 10.1016/j.disopt.2020.100570 | s2cid = 213389485 | doi-access = free | hdl = 2078.1/230413 | hdl-access = free }}</ref>

.

[[File:An example of an unrooted binary tree with four leaves.pdf|thumb|An example of an unrooted binary tree with four leaves]]

[[Daniele Catanzaro]], [[Raffaele Pesenti]] and [[Laurence Wolsey]] showed<ref>{{cite journal | vauthors name= Catanzaro D, Pesenti R, Wolsey L | title = "On the Balanced Minimum Evolution Polytope | journal = Discrete Optimization | volume = 36 | pages = 1-33 | date = 2020 }}<P"/ref> that the path-length sequence collection encoding a given UBT with n leaves must satisfy specific equalities, namely

* <math> p_{i,i}=0 </math> for all <math> i\in [1,n]</math>

* <math> p_{i,j}=p_{j,i} </math> for all <math> i,j\in [1,n]: i\neq j</math>

* <math> p_{i,ij}\leq p_{i,k} + p_{k,j} </math> for all <math> i,j,k\in [1,n]: i\neq j\neq k</math>

* <math> \sum_{j=1}^{n} 1/2^{p_{i,j}}=1/2 </math> for all <math> i\in [1,n]</math> (which is an adaptation of the [[Kraft–McMillan inequality]])

* <math> \sum_{i=1}^n\sum_{j=1}^{n} p_{i,j}/2^{p_{i,j}}=2n-3 </math>, also referred to as the ''phylogenetic manifold''.<ref>{{cite journal | vauthors name= Catanzaro D, Pesenti R, Wolsey L | title = "On the Balanced Minimum Evolution Polytope | journal = Discrete Optimization | volume = 36 | pages = 1-33 | date = 2020 }}<P"/ref>.

These equalities are proved to be necessary and independent for a path-length collection to encode an UBT with n leaves.<ref>{{cite journal | vauthors name= Catanzaro D, Pesenti R, Wolsey L | title = "On the Balanced Minimum Evolution Polytope | journal = Discrete Optimization | volume = 36 | pages = 1-33 | date = 2020 }}<P"/ref>. It is currently unknown whether they are also sufficient.

==Alternative names==

Unrooted binary trees have also been called '''free binary trees''',<ref>{{harvtxt|Czumaj|Gibbons|1996}}.</ref> '''cubic trees''',<ref>{{harvtxt|Exoo|1996}}.</ref> '''ternary trees'''<ref name="rs91"/> and '''unrooted ternary trees''',.<ref>{{harvtxt|Cilibrasi|Vitanyi|2006}}.</ref> However, the "free binary tree" name has also been applied to unrooted trees that may have degree-two nodes<ref>{{harvtxt|Harary|Palmer|Robinson|1992}}.</ref> and to rooted binary trees with unordered children,<ref>{{harvtxt|Przytycka|Larmore|1994}}.</ref> and the "ternary tree" name is more frequently used to mean a [[ternary tree|rooted tree with three children per node]].

==Notes==

Line 66:

| volume = 1

| year = 2007}}.

*{{cite arxivarXiv

| last1 = Cilibrasi | first1 = Rudi

| last2 = Vitanyi | first2 = Paul M.B.

Line 81:

| title = Guthrie's problem: new equivalences and rapid reductions

| volume = 154

| year = 1996}}.| doi-access = free

}}.

*{{citation

| last = Eppstein | first = David

Line 91 ⟶ 92:

| title = Squarepants in a tree: Sum of subtree clustering and hyperbolic pants decomposition

| volume = 5

| year = 2009}}.| s2cid = 2434

}}.

*{{citation

| last = Exoo | first = Geoffrey

Line 100 ⟶ 102:

| url = http://www.combinatorics.org/Volume_3/PDFFiles/v3i1r30.pdf

| volume = 3

| year = 1996}}| doi = 10.37236/1254

| doi-access = free

}}.

*{{citation

| last = Furnas | first = George W.

Line 109 ⟶ 113:

| title = The generation of random, binary unordered trees

| volume = 1

| year = 1984}}.| s2cid = 121121529

}}.

*{{citation

| last1 = Harary | first1 = Frank | author1-link = Frank Harary

Line 132 ⟶ 137:

| year = 1989}}

*{{citation

| last1 = Przytycka | first1 = Teresa M. | author1-link = Teresa Przytycka

| last2 = Larmore | first2 = Lawrence L. | author2-link = Lawrence L. Larmore

| contribution = The optimal alphabetic tree problem revisited

Line 141 ⟶ 146:

| title = Proc. 21st International Colloquium on Automata, Languages and Programming (ICALP '94)

| volume = 820

| year = 1994| isbn = 978-3-540-58201-4 }}.

*{{citation

| last1 = Robertson | first1 = Neil | author1-link = Neil Robertson (mathematician)

Line 151 ⟶ 156:

| title = Graph minors. X. Obstructions to tree-decomposition

| volume = 52

| year = 1991}}.| doi-access = free

}}.

*{{citation

| last1 = St. John | first1 = Katherine

Line 163 ⟶ 169:

| title = Performance study of phylogenetic methods: (unweighted) quartet methods and neighbor-joining

| volume = 48

| year = 2003}}.| s2cid = 5550338

| url = http://infoscience.epfl.ch/record/97874/files/jalgs.pdf

}}.

[[Category:Trees (graph theory)]]