Unrooted binary tree: Difference between revisions

Revision as of 19:09, 16 June 2017

Revision as of 20:00, 16 June 2017

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 [[wikipedia.org/wiki/Tree_(graph_theory)#Plane_treeOrdered 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''&nbsp;&minus;&nbsp;2 internal nodes, so the labels may be taken from the set of integers from 1 to 2''n''&nbsp;&minus;&nbsp;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.<ref name="f84">{{harvtxt|Furnas|1984}}.</ref>