Namespaces
Variants
Actions

Difference between revisions of "Tree"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (move comment around)
 
(14 intermediate revisions by 3 users not shown)
Line 1: Line 1:
 +
<!--
 +
t0940601.png
 +
$#A+1 = 61 n = 0
 +
$#C+1 = 61 : ~/encyclopedia/old_files/data/T094/T.0904060 Tree
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
 +
 +
{{TEX|auto}}
 +
{{TEX|done}}
 +
 
''in graph theory''
 
''in graph theory''
  
A connected non-oriented [[Graph|graph]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094060/t0940601.png" /> 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094060/t0940602.png" /> vertices contains <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094060/t0940603.png" /> edges. The number of different trees which may be constructed on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094060/t0940604.png" /> numbered vertices is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094060/t0940605.png" />. A tree with one distinguished vertex is said to be a rooted tree.
+
A connected non-oriented [[Graph|graph]] $G$ 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 $n$
 +
vertices contains $n - 1$
 +
edges. The number of different trees which may be constructed on $n$
 +
numbered vertices is $n^{n-2}$.  
 +
 
 +
A tree with one distinguished vertex is said to be a [[rooted tree]]. A '''forest''' is a graph without cycles: every connected component of a forest is a tree.
 +
 
 +
[[File:Some_tree.svg|center|200px|Example of tree]]
 +
 
 +
== Enumeration ==
  
 
The enumerating series
 
The enumerating series
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094060/t0940606.png" /></td> </tr></table>
+
$$
 +
T ( x)  = \sum _ {n = 1 } ^  \infty  T _ {n} x  ^ {n}
 +
$$
 +
 
 +
for the number  $  T _ {n} $
 +
of non-isomorphic rooted trees with  $  n $
 +
vertices satisfies the functional equation
  
for the number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094060/t0940607.png" /> of non-isomorphic rooted trees with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094060/t0940608.png" /> vertices satisfies the functional equation
+
$$
 +
T ( x)  = x  \mathop{\rm exp}  \sum _ {r = 1 } ^  \infty 
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094060/t0940609.png" /></td> </tr></table>
+
\frac{1}{r}
 +
T ( x  ^ {r} ) .
 +
$$
  
 
The enumerating series
 
The enumerating series
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094060/t09406010.png" /></td> </tr></table>
+
$$
 +
t ( x)  = \sum _ {n = 1 } ^  \infty  t _ {n} x  ^ {n}
 +
$$
  
for the number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094060/t09406011.png" /> of non-isomorphic trees with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094060/t09406012.png" /> vertices can be represented using the enumerating series for rooted trees:
+
for the number t _ {n} $
 +
of non-isomorphic trees with $  n $
 +
vertices can be represented using the enumerating series for rooted trees:
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094060/t09406013.png" /></td> </tr></table>
+
$$
 +
t ( x)  = T ( x) - \frac{T  ^ {2} ( x) - T ( x  ^ {2} ) }{2}.
 +
$$
  
The functional equations for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094060/t09406014.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094060/t09406015.png" /> yield the values of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094060/t09406016.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094060/t09406017.png" /> for specific values of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094060/t09406018.png" /> (see, for example, [[#References|[1]]]).
+
The functional equations for $T(x)$ and $t(x)$ yield the values of $T_{n}$
 +
and $t_{n}$ for specific values of $n$, see {{Cite|R1}}.
  
It has been shown that, as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094060/t09406019.png" />,
+
It has been shown that, as $  n \rightarrow \infty $,
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094060/t09406020.png" /></td> </tr></table>
+
$$
 +
t _ {n}  \sim  C
 +
\frac{\alpha  ^ {n} }{n  ^ {5/2} }
 +
,
 +
$$
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094060/t09406021.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094060/t09406022.png" /> [[#References|[2]]]. Problems of enumeration of trees of a specific kind arise, for example, in chemistry in the study of isomers.
+
where $  C = 0.534948 \dots $,  
 +
$  \alpha = 2.95576 \dots$ (see {{Cite|R2}}).
  
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094060/t09406023.png" /> in the plane (cf. [[Graph imbedding|Graph imbedding]]). Starting from any vertex, one moves along the edges of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094060/t09406024.png" />, 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094060/t09406025.png" /> is the number of tree edges, one returns to the starting vertex after <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094060/t09406026.png" /> steps, having passed each edge twice. The sequence of 0's and 1's of length <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094060/t09406027.png" /> thus obtained (the code of the tree) makes it possible to uniquely reconstruct not only the tree <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094060/t09406028.png" /> 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: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094060/t09406029.png" />.
+
Problems of enumeration of trees of a specific kind arise, for example, in chemistry in the study of isomers.
  
A tree <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094060/t09406030.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094060/t09406031.png" /> vertices can be uniquely retrieved (up to an isomorphism) from the set of all its <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094060/t09406032.png" />-vertex subgraphs <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094060/t09406033.png" />, which are obtained from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094060/t09406034.png" /> by elimination of one of its vertices <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094060/t09406035.png" />.
+
== Encoding ==
 +
 
 +
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  $  D $
 +
in the plane (cf. [[Graph imbedding|Graph imbedding]]). Starting from any vertex, one moves along the edges of  $  D $,
 +
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  $  m $
 +
is the number of tree edges, one returns to the starting vertex after  $  2m $
 +
steps, having passed each edge twice. The sequence of 0's and 1's of length  $  2m $
 +
thus obtained (the code of the tree) makes it possible to uniquely reconstruct not only the tree  $  D $
 +
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:  $  t _ {n} < T _ {n} < 4  ^ {n} $.
 +
 
 +
A tree $G$ with $n$
 +
vertices can be uniquely retrieved (up to an isomorphism) from the set of all its $  ( n - 1 ) $-
 +
vertex subgraphs $  G - v $,  
 +
which are obtained from $  G $
 +
by elimination of one of its vertices $  v $.
  
 
Any tree is also uniquely defined by the distances (length of the shortest path) between its terminal (valency 1) 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094060/t09406036.png" /> without loops and without multiple edges can be computed as follows. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094060/t09406037.png" /> be the matrix obtained from the adjacency matrix of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094060/t09406038.png" /> by replacing all the signs of the elements by the opposite signs and by replacing the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094060/t09406039.png" />-th entry on the principal diagonal by the valency of the vertex <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094060/t09406040.png" />. The cofactors of all entries on the principal diagonal of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094060/t09406041.png" /> will then all be equal, and their common value is the number of spanning trees of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094060/t09406042.png" />. Spanning trees are employed, for example, to find independent cycles in an electric circuit.
+
== Spanning trees ==
 +
 
 +
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 $G$
 +
without loops and without multiple edges can be computed as follows. Let $  M $
 +
be the matrix obtained from the [[adjacency matrix]] of $G$
 +
by replacing all the signs of the elements by the opposite signs and by replacing the $  i $-
 +
th entry on the principal diagonal by the valency of the vertex $  v _ {i} $.  
 +
The cofactors of all entries on the principal diagonal of $  M $
 +
will then all be equal, and their common value is the number of spanning trees of $  G $.  
 +
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 ({{Cite|R3}}, {{Cite|R4}}).
  
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 [[#References|[3]]], [[#References|[4]]]. A tree growing (or issuing) from a vertex <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094060/t09406043.png" /> is the name given to an oriented graph which is (disregarding the orientation) a rooted tree with root <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094060/t09406044.png" />, and in which for any vertex <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094060/t09406045.png" /> the (unique) chain connecting <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094060/t09406046.png" /> to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094060/t09406047.png" /> is an oriented path from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094060/t09406048.png" /> to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094060/t09406049.png" />. Such trees are employed, for example, in the description of deterministic functions, for the representation of information in information-searching systems, etc.
+
== Directed trees ==
  
The concept of "forest" is a generalization of the concept of "tree" . A forest is a graph without cycles (not necessarily connected).
+
A tree growing (or issuing) from a vertex $ v _ {0} $
 +
is the name given to an oriented graph which is (disregarding the orientation) a rooted tree with root $  v _ {0} $,
 +
and in which for any vertex  $  v _ {1} $
 +
the (unique) chain connecting  $  v _ {0} $
 +
to  $  v _ {1} $
 +
is an oriented path from  $  v _ {0} $
 +
to  $  v _ {1} $.
 +
Such trees are employed, for example, in the description of deterministic functions, for the representation of information in information-searching systems, etc.
  
====References====
+
== Comments ==
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  F. Harary,  "Graph theory" , Addison-Wesley  (1969)  pp. Chapt. 9</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  R. Otter,  "The number of trees"  ''Ann. of Math.'' , '''49''' :  3  (1948)  pp. 583–599</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  R.C. Prim,  "Shortest connection networks and some generalizations"  ''Bell Systems Techn. J.'' , '''36''' :  6  (1957)  pp. 1389–1401</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  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</TD></TR></table>
 
  
 +
A directed tree is a directed graph which is a tree with root  $  r $ such that for each vertex  $  v $
 +
there is a directed path from  $  r $ to  $  v $.
 +
Thus, each vertex except  $  r $ has incoming degree precisely  $  1 $ and  $  r $ has incoming degree  $  0 $
 +
and is a source. Alternatively and equivalently (orientation reversal), a directed tree is a tree with root  $  r $
 +
such that each vertex has outgoing degree  $  1 $ (and  $  r $
 +
has outgoing degree  $  0 $ and is a sink). Both definitions occur in the literature. Sometimes the phrase rooted tree is used in the meaning of directed tree.
  
 +
== References ==
  
====Comments====
+
* {{Ref|R1}} F. Harary, "Graph theory", Addison-Wesley (1969) Chapt. 9 {{ZBL|0182.57702}}
A directed tree is a directed graph which is a tree with root <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094060/t09406050.png" /> such that for each vertex <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094060/t09406051.png" /> there is a directed path from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094060/t09406052.png" /> to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094060/t09406053.png" />. Thus, each vertex except <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094060/t09406054.png" /> has incoming degree precisely <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094060/t09406055.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094060/t09406056.png" /> has incoming degree <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094060/t09406057.png" /> and is a source. Alternatively and equivalently (orientation reversal), a directed tree is a tree with root <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094060/t09406058.png" /> such that each vertex has outgoing degree <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094060/t09406059.png" /> (and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094060/t09406060.png" /> has outgoing degree <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094060/t09406061.png" /> and is a sink). Both definitions occur in the literature. Sometimes the phrase rooted tree is used in the meaning of directed tree.
+
* {{Ref|R2}} R. Otter, "The number of trees", ''Ann. of Math.'', '''49''' : 3  (1948)  pp. 583–599 {{ZBL|0032.12601}}
 +
* {{Ref|R3}} R.C. Prim, "Shortest connection networks and some generalizations", ''Bell Systems Techn. J.'', '''36''' : 6  (1957)  pp. 1389–1401
 +
* {{Ref|R4}} 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
 +
* {{Ref|a1}} W.K. Chen, "Applied graph theory", North-Holland (1971)
 +
* {{Ref|a2}} L. Comtet, "Advanced combinatorics", Reidel (1974) (Translated from French)
 +
* {{Ref|a3}} M. Goudran, M. Minoux, "Graphes et algorithmes", Eyrolles (1979) Chapt. 4
  
====References====
+
[[Category:Graph theory]]
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  W.K. Chen,  "Applied graph theory" , North-Holland  (1971)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  L. Comtet,  "Advanced combinatorics" , Reidel  (1974)  (Translated from French)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  M. Goudran,  M. Minoux,  "Graphes et algorithmes" , Eyrolles  (1979)  pp. Chapt. 4</TD></TR></table>
 

Latest revision as of 06:20, 30 March 2023


in graph theory

A connected non-oriented graph $G$ 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 $n$ vertices contains $n - 1$ edges. The number of different trees which may be constructed on $n$ numbered vertices is $n^{n-2}$.

A tree with one distinguished vertex is said to be a rooted tree. A forest is a graph without cycles: every connected component of a forest is a tree.

Example of tree

Enumeration

The enumerating series

$$ T ( x) = \sum _ {n = 1 } ^ \infty T _ {n} x ^ {n} $$

for the number $ T _ {n} $ of non-isomorphic rooted trees with $ n $ vertices satisfies the functional equation

$$ T ( x) = x \mathop{\rm exp} \sum _ {r = 1 } ^ \infty \frac{1}{r} T ( x ^ {r} ) . $$

The enumerating series

$$ t ( x) = \sum _ {n = 1 } ^ \infty t _ {n} x ^ {n} $$

for the number $ t _ {n} $ of non-isomorphic trees with $ n $ vertices can be represented using the enumerating series for rooted trees:

$$ t ( x) = T ( x) - \frac{T ^ {2} ( x) - T ( x ^ {2} ) }{2}. $$

The functional equations for $T(x)$ and $t(x)$ yield the values of $T_{n}$ and $t_{n}$ for specific values of $n$, see [R1].

It has been shown that, as $ n \rightarrow \infty $,

$$ t _ {n} \sim C \frac{\alpha ^ {n} }{n ^ {5/2} } , $$

where $ C = 0.534948 \dots $, $ \alpha = 2.95576 \dots$ (see [R2]).

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

Encoding

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 $ D $ in the plane (cf. Graph imbedding). Starting from any vertex, one moves along the edges of $ D $, 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 $ m $ is the number of tree edges, one returns to the starting vertex after $ 2m $ steps, having passed each edge twice. The sequence of 0's and 1's of length $ 2m $ thus obtained (the code of the tree) makes it possible to uniquely reconstruct not only the tree $ D $ 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: $ t _ {n} < T _ {n} < 4 ^ {n} $.

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

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

Spanning trees

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 $G$ without loops and without multiple edges can be computed as follows. Let $ M $ be the matrix obtained from the adjacency matrix of $G$ by replacing all the signs of the elements by the opposite signs and by replacing the $ i $- th entry on the principal diagonal by the valency of the vertex $ v _ {i} $. The cofactors of all entries on the principal diagonal of $ M $ will then all be equal, and their common value is the number of spanning trees of $ G $. 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 ([R3], [R4]).

Directed trees

A tree growing (or issuing) from a vertex $ v _ {0} $ is the name given to an oriented graph which is (disregarding the orientation) a rooted tree with root $ v _ {0} $, and in which for any vertex $ v _ {1} $ the (unique) chain connecting $ v _ {0} $ to $ v _ {1} $ is an oriented path from $ v _ {0} $ to $ v _ {1} $. Such trees are employed, for example, in the description of deterministic functions, for the representation of information in information-searching systems, etc.

Comments

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

References

  • [R1] F. Harary, "Graph theory", Addison-Wesley (1969) Chapt. 9 Zbl 0182.57702
  • [R2] R. Otter, "The number of trees", Ann. of Math., 49 : 3 (1948) pp. 583–599 Zbl 0032.12601
  • [R3] R.C. Prim, "Shortest connection networks and some generalizations", Bell Systems Techn. J., 36 : 6 (1957) pp. 1389–1401
  • [R4] 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
  • [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) Chapt. 4
How to Cite This Entry:
Tree. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Tree&oldid=16337
This article was adapted from an original article by V.B. Alekseev (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article