Content deleted Content added
m →References: and moret too while I'm at it |
m Open access bot: hdl updated in citation with #oabot. |
||
| (29 intermediate revisions by 20 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 5:
A [[free tree]] or unrooted tree is a [[connected graph|connected]] [[undirected graph]] with no [[cycle (graph theory)|cycles]]. The vertices with one neighbor are the ''leaves'' of the tree, and the remaining vertices are the ''internal nodes'' of the tree. The [[degree (graph theory)|degree]] of a vertex is its number of neighbors; in a tree with more than one node, the leaves are the vertices of degree one. An unrooted binary tree is a free tree in which all internal nodes have degree exactly three.
In some applications it may make sense to distinguish subtypes of unrooted binary trees: a [[planar graph|planar embedding]] of the tree may be fixed by specifying a cyclic ordering for the edges at each vertex, making it into a [[Ordered tree|plane tree]]. In computer science, binary trees are often rooted and ordered when they are used as [[data structure]]s, but in the applications of unrooted binary trees in [[hierarchical clustering]] and [[evolutionary tree]] reconstruction, unordered trees are more common.<ref name="f84"/>
Additionally, one may distinguish between trees in which all vertices have distinct labels, trees in which the leaves only are labeled, and trees in which the nodes are not labeled. In an unrooted binary tree with ''n'' leaves, there will be ''n'' −
==Related structures==
===Rooted binary trees===
{{Main|Rooted binary tree}}
An unrooted binary tree ''T'' may be transformed into a full rooted [[binary tree]] (that is, a rooted tree in which each non-leaf node has exactly two children) by choosing a ''root edge'' ''e'' of ''T'', placing a new root node in the middle of ''e'', and directing every edge of the resulting subdivided tree away from the root node. Conversely, any full rooted binary tree may be transformed into an unrooted binary tree by removing the root node, replacing the path between its two children by a single undirected edge, and suppressing the orientation of the remaining edges in the graph. For this reason, there are exactly 2''n'' −3 times as many full rooted binary trees with ''n'' leaves as there are unrooted binary trees with ''n'' leaves.<ref name="f84"/>
Line 31 ⟶ 32:
The numbers of trees on 2, 3, 4, 5, ... labeled leaves are
:1, 1, 3, 15, 105, 945, 10395, 135135, 2027025, 34459425, ... {{OEIS|A001147}}.
==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]]
Daniele Catanzaro, [[Raffaele Pesenti]] and [[Laurence Wolsey]] showed<ref name="On the Balanced Minimum Evolution P"/> 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,j}\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"/>
These equalities are proved to be necessary and independent for a path-length collection to encode an UBT with n leaves.<ref name="On the Balanced Minimum Evolution P"/> 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'''
==Notes==
Line 44 ⟶ 60:
| last3 = Cannings | first3 = Christopher
| edition = 3rd
| isbn =
| page = 502
| publisher = Wiley-Interscience
Line 50 ⟶ 66:
| volume = 1
| year = 2007}}.
*{{cite
| last1 = Cilibrasi | first1 = Rudi
| last2 = Vitanyi | first2 = Paul M.B.
Line 65 ⟶ 81:
| title = Guthrie's problem: new equivalences and rapid reductions
| volume = 154
| year = 1996
}}.
*{{citation
| last = Eppstein | first = David
Line 75 ⟶ 92:
| title = Squarepants in a tree: Sum of subtree clustering and hyperbolic pants decomposition
| volume = 5
| year = 2009
}}.
*{{citation
| last = Exoo | first = Geoffrey
Line 84 ⟶ 102:
| url = http://www.combinatorics.org/Volume_3/PDFFiles/v3i1r30.pdf
| volume = 3
| year = 1996
| doi-access = free
}}.
*{{citation
| last = Furnas | first = George W.
Line 93 ⟶ 113:
| title = The generation of random, binary unordered trees
| volume = 1
| year = 1984
}}.
*{{citation
| last1 = Harary | first1 = Frank | author1-link = Frank Harary
Line 116 ⟶ 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 125 ⟶ 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 135 ⟶ 156:
| title = Graph minors. X. Obstructions to tree-decomposition
| volume = 52
| year = 1991
}}.
*{{citation
| last1 = St. John | first1 = Katherine
Line 147 ⟶ 169:
| title = Performance study of phylogenetic methods: (unweighted) quartet methods and neighbor-joining
| volume = 48
| year = 2003
| url = http://infoscience.epfl.ch/record/97874/files/jalgs.pdf
}}.
[[Category:Trees (graph theory)]]
| |||