Unrooted binary tree: Difference between revisions

Revision as of 07:20, 6 May 2023

Latest revision as of 05:59, 2 June 2025

(5 intermediate revisions by 5 users not shown)

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