Unrooted binary tree

From Wikipedia for FEVERv2
Jump to navigation Jump to search

In mathematics and computer science, an unrooted binary tree is an unrooted tree in which each vertex has either one or three neighbors. Unrooted binary tree_sentence_0

Definitions Unrooted binary tree_section_0

A free tree or unrooted tree is a connected undirected graph with no cycles. Unrooted binary tree_sentence_1

The vertices with one neighbor are the leaves of the tree, and the remaining vertices are the internal nodes of the tree. Unrooted binary tree_sentence_2

The 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. Unrooted binary tree_sentence_3

An unrooted binary tree is a free tree in which all internal nodes have degree exactly three. Unrooted binary tree_sentence_4

In some applications it may make sense to distinguish subtypes of unrooted binary trees: a planar embedding of the tree may be fixed by specifying a cyclic ordering for the edges at each vertex, making it into a plane tree. Unrooted binary tree_sentence_5

In computer science, binary trees are often rooted and ordered when they are used as data structures, but in the applications of unrooted binary trees in hierarchical clustering and evolutionary tree reconstruction, unordered trees are more common. Unrooted binary tree_sentence_6

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. Unrooted binary tree_sentence_7

In an unrooted binary tree with n leaves, there will be n − 2 internal nodes, so the labels may be taken from the set of integers from 1 to 2n − 1 when all nodes are to be labeled, or from the set of integers from 1 to n when only the leaves are to be labeled. Unrooted binary tree_sentence_8

Related structures Unrooted binary tree_section_1

Rooted binary trees Unrooted binary tree_section_2

Main article: Rooted binary tree Unrooted binary tree_sentence_9

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. Unrooted binary tree_sentence_10

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. Unrooted binary tree_sentence_11

For this reason, there are exactly 2n −3 times as many full rooted binary trees with n leaves as there are unrooted binary trees with n leaves. Unrooted binary tree_sentence_12

Hierarchical clustering Unrooted binary tree_section_3

A hierarchical clustering of a collection of objects may be formalized as a maximal family of sets of the objects in which no two sets cross. Unrooted binary tree_sentence_13

That is, for every two sets S and T in the family, either S and T are disjoint or one is a subset of the other, and no more sets can be added to the family while preserving this property. Unrooted binary tree_sentence_14

If T is an unrooted binary tree, it defines a hierarchical clustering of its leaves: for each edge (u,v) in T there is a cluster consisting of the leaves that are closer to u than to v, and these sets together with the empty set and the set of all leaves form a maximal non-crossing family. Unrooted binary tree_sentence_15

Conversely, from any maximal non-crossing family of sets over a set of n elements, one can form a unique unrooted binary tree that has a node for each triple (A,B,C) of disjoint sets in the family that together cover all of the elements. Unrooted binary tree_sentence_16

Evolutionary trees Unrooted binary tree_section_4

According to simple forms of the theory of evolution, the history of life can be summarized as a phylogenetic tree in which each node describes a species, the leaves represent the species that exist today, and the edges represent ancestor-descendant relationships between species. Unrooted binary tree_sentence_17

This tree has a natural orientation from ancestors to descendants, and a root at the common ancestor of the species, so it is a rooted tree. Unrooted binary tree_sentence_18

However, some methods of reconstructing binary trees can reconstruct only the nodes and the edges of this tree, but not their orientations. Unrooted binary tree_sentence_19

For instance, cladistic methods such as maximum parsimony use as data a set of binary attributes describing features of the species. Unrooted binary tree_sentence_20

These methods seek a tree with the given species as leaves in which the internal nodes are also labeled with features, and attempt to minimize the number of times some feature is present at only one of the two endpoints of an edge in the tree. Unrooted binary tree_sentence_21

Ideally, each feature should only have one edge for which this is the case. Unrooted binary tree_sentence_22

Changing the root of a tree does not change this number of edge differences, so methods based on parsimony are not capable of determining the location of the tree root and will produce an unrooted tree, often an unrooted binary tree. Unrooted binary tree_sentence_23

Unrooted binary trees also are produced by methods for inferring evolutionary trees based on quartet data specifying, for each four leaf species, the unrooted binary tree describing the evolution of those four species, and by methods that use quartet distance to measure the distance between trees. Unrooted binary tree_sentence_24

Branch-decomposition Unrooted binary tree_section_5

Unrooted binary trees are also used to define branch-decompositions of graphs, by forming an unrooted binary tree whose leaves represent the edges of the given graph. Unrooted binary tree_sentence_25

That is, a branch-decomposition may be viewed as a hierarchical clustering of the edges of the graph. Unrooted binary tree_sentence_26

Branch-decompositions and an associated numerical quantity, branch-width, are closely related to treewidth and form the basis for efficient dynamic programming algorithms on graphs. Unrooted binary tree_sentence_27

Enumeration Unrooted binary tree_section_6

Because of their applications in hierarchical clustering, the most natural graph enumeration problem on unrooted binary trees is to count the number of trees with n labeled leaves and unlabeled internal nodes. Unrooted binary tree_sentence_28

An unrooted binary tree on n labeled leaves can be formed by connecting the nth leaf to a new node in the middle of any of the edges of an unrooted binary tree on n − 1 labeled leaves. Unrooted binary tree_sentence_29

There are 2n − 5 edges at which the nth node can be attached; therefore, the number of trees on n leaves is larger than the number of trees on n − 1 leaves by a factor of 2n − 5. Unrooted binary tree_sentence_30

Thus, the number of trees on n labeled leaves is the double factorial Unrooted binary tree_sentence_31

The numbers of trees on 2, 3, 4, 5, ... labeled leaves are Unrooted binary tree_sentence_32

Unrooted binary tree_description_list_0

  • 1, 1, 3, 15, 105, 945, 10395, 135135, 2027025, 34459425, ... (sequence in the OEIS).Unrooted binary tree_item_0_0

Fundamental Equalities Unrooted binary tree_section_7

Daniele Catanzaro, Raffaele Pesenti and Laurence Wolsey showed that the path-length sequence collection encoding a given UBT with n leaves must satisfy specific equalities, namely Unrooted binary tree_sentence_33

These equalities are proved to be necessary and independent for a path-length collection to encode an UBT with n leaves. Unrooted binary tree_sentence_34

It is currently unknown whether they are also sufficient. Unrooted binary tree_sentence_35

Alternative names Unrooted binary tree_section_8

Unrooted binary trees have also been called free binary trees, cubic trees, ternary trees and unrooted ternary trees,. Unrooted binary tree_sentence_36

However, the "free binary tree" name has also been applied to unrooted trees that may have degree-two nodes and to rooted binary trees with unordered children, and the "ternary tree" name is more frequently used to mean a rooted tree with three children per node. Unrooted binary tree_sentence_37


Credits to the contents of this page go to the authors of the corresponding Wikipedia page: en.wikipedia.org/wiki/Unrooted binary tree.