Unrooted binary tree: Difference between revisions

Revision as of 22:24, 29 January 2024

Latest revision as of 05:59, 2 June 2025

(3 intermediate revisions by 3 users not shown)

Line 10:

==Related structures==

===UnrootedRooted binary trees===

{{Main|UnrootedRooted binary tree}}

An Rootedunrooted binary tree ''T'' may be transformed into a full Unrootrooted [[binary tree]] (that is, a unrootedrooted tree in which each non-leaf node has exactly two children) by choosing a ''unrootroot edge'' ''e'' of ''T'', placing a new unrootroot node in the middle of ''e'', and directing every edge of the resulting subdivided tree away from the unrootroot node. Conversely, any full unrootedrooted binary tree may be transformed into an rootedunrooted binary tree by removing the unrootroot node, replacing the path between its two children by a single directedundirected edge, and suppressing the orientation of the remaining edges in the graph. For this reason, there are exactly 2''n''&nbsp;&minus;3 times as many full unrootedrooted binary trees with ''n'' leaves as there are rootedunrooted binary trees with ''n'' leaves.<ref name="f84"/>

===Hierarchical clustering===

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 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)