Content deleted Content added
mNo edit summary |
|||
Line 36:
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>{{cite journal | vauthors = Catanzaro D, Pesenti R, Wolsey L | title = On the Balanced Minimum Evolution Polytope | journal = Discrete Optimization | volume = 36 | pages = 1-33 | date = 2020 }}</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 = Catanzaro D, Pesenti R, Wolsey L | title = On the Balanced Minimum Evolution Polytope | journal = Discrete Optimization | volume = 36 | pages = 1-33 | date = 2020 }}</ref> that the path-length sequence collection encoding a given UBT with n leaves must satisfy specific equalities, namely
Line 43 ⟶ 44:
* <math> p_{i,i}\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''.
==Alternative names==
| |||