Unrooted binary tree: Difference between revisions

Revision as of 19:58, 14 January 2021

Latest revision as of 05:59, 2 June 2025

(11 intermediate revisions by 8 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 | date = 2020 | page = 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]]

Line 42:

* <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 name="On the Balanced Minimum Evolution P"/>

Line 49:

==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 102 ⟶ 103:

| volume = 3

| year = 1996| doi = 10.37236/1254

| doi-access = free

}}.

*{{citation

Line 135 ⟶ 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 144 ⟶ 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 154 ⟶ 156:

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

| volume = 52

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

}}.

*{{citation

| last1 = St. John | first1 = Katherine