Tree

in graph theory

A connected non-oriented graph which does not contain cycles. A tree has no multiple edges and no loops. Since they are the simplest possible, connected graphs, trees are suitable models for the study of various problems in graph theory. Any tree with vertices contains edges. The number of different trees which may be constructed on numbered vertices is . A tree with one distinguished vertex is said to be a rooted tree.

The enumerating series

for the number of non-isomorphic rooted trees with vertices satisfies the functional equation

The enumerating series

for the number of non-isomorphic trees with vertices can be represented using the enumerating series for rooted trees:

The functional equations for and yield the values of and for specific values of (see, for example, [1]).

It has been shown that, as ,

where , [2]. Problems of enumeration of trees of a specific kind arise, for example, in chemistry in the study of isomers.

Trees may be fairly simply coded by strings of zeros and ones. Consider, for example, some regular (without intersection of edges) imbedding of a tree in the plane (cf. Graph imbedding). Starting from any vertex, one moves along the edges of , turning at each vertex towards the first edge on the right, and returning in the terminal vertices of the tree. While moving along some edge, one writes 0 if the edge is traversed for the first time, and writes 1 when the edge is traversed for the second time (in the opposite direction). If is the number of tree edges, one returns to the starting vertex after steps, having passed each edge twice. The sequence of 0's and 1's of length thus obtained (the code of the tree) makes it possible to uniquely reconstruct not only the tree itself, but also its imbedding in the plane. Several different codes correspond to one specific tree. The following estimate follows from this mode of coding: .

A tree with vertices can be uniquely retrieved (up to an isomorphism) from the set of all its -vertex subgraphs , which are obtained from by elimination of one of its vertices .

Any tree is also uniquely defined by the distances (length of the shortest path) between its terminal (valency 1) vertices.

A spanning tree of a graph is a subgraph of the given graph which contains all its vertices and which is a tree. The number of spanning trees of any given connected graph without loops and without multiple edges can be computed as follows. Let be the matrix obtained from the adjacency matrix of by replacing all the signs of the elements by the opposite signs and by replacing the -th entry on the principal diagonal by the valency of the vertex . The cofactors of all entries on the principal diagonal of will then all be equal, and their common value is the number of spanning trees of . Spanning trees are employed, for example, to find independent cycles in an electric circuit.

Of importance in applications is the problem of finding the spanning tree with the smallest sum of the edge-weights in a connected graph in which weights are assigned to the edges. Such a problem arises, for example, in designing communication networks. An algorithm for the solution of this shortest spanning tree problem is known [3], [4]. A tree growing (or issuing) from a vertex is the name given to an oriented graph which is (disregarding the orientation) a rooted tree with root , and in which for any vertex the (unique) chain connecting to is an oriented path from to . Such trees are employed, for example, in the description of deterministic functions, for the representation of information in information-searching systems, etc.

The concept of a "forest" is a generalization of the concept of a "tree" . A forest is a graph without cycles (not necessarily connected).

References

[1]	F. Harary, "Graph theory" , Addison-Wesley (1969) pp. Chapt. 9
[2]	R. Otter, "The number of trees" Ann. of Math. , 49 : 3 (1948) pp. 583–599
[3]	R.C. Prim, "Shortest connection networks and some generalizations" Bell Systems Techn. J. , 36 : 6 (1957) pp. 1389–1401
[4]	J.B. Kruskal, "On the shortest spanning subtree of a graph and the travelling salesman problem" Proc. Amer. Math. Soc. , 7 (1956) pp. 48–50

Comments

A directed tree is a directed graph which is a tree with root such that for each vertex there is a directed path from to . Thus, each vertex except has incoming degree precisely and has incoming degree and is a source. Alternatively and equivalently (orientation reversal), a directed tree is a tree with root such that each vertex has outgoing degree (and has outgoing degree and is a sink). Both definitions occur in the literature. Sometimes the phrase rooted tree is used in the meaning of directed tree.

References

[a1]	W.K. Chen, "Applied graph theory" , North-Holland (1971)
[a2]	L. Comtet, "Advanced combinatorics" , Reidel (1974) (Translated from French)
[a3]	M. Goudran, M. Minoux, "Graphes et algorithmes" , Eyrolles (1979) pp. Chapt. 4