Associated Topics || Dr. Math Home || Search Dr. Math

### Using Trees

```
Date: 10/18/96 at 14:52:31
From: Anonymous
Subject: Use of Trees

I teach a discrete math course.   We are studying trees and one of my
students asked what trees were used for. Can you tell me more about
the applications of trees?

Thanks.
```

```
Date: 10/18/96 at 18:25:52
From: Doctor Keith
Subject: Re: Use of Trees

Hi,

Here are some applications:

-------(1)-------
The classic example is the minimal connector problem.  That is, if you
have n nodes, what is the least number of edges to connect the nodes?
Doesn't sound like a practical example?  Well say you had to connect
several cities with a transportation system (say a new mag-lev train)
and you wanted to find the best route (particularly if you use a
weighted graph).  That route would be a tree because you can't afford
multiple connections.  This is probably the one in your book, but if
not it is a good one.

-------(2)-------
The classic Ethernet LAN is a tree, and the probability of successful
transmission can be modeled as weights.  The resulting graph can be
used to study or design the network.

-------(3)-------
Many problems in probability (classic counting problems) use trees to
model all the possibilities.  Any book on probability will have tons
of these, and the benefit for finding probabilities is tremendous.
The example of two teams meeting in play-off is a good example.

-------(4)-------
Likewise the alternative analysis diagrams used in decision making are
trees and weights in the tree can be used to pick the optimal decion.
These are very popular in Total Quality teams, which are all the vogue

-------(5)-------
A friend of mine did a masters thesis in Spanish, part of which was
the use of trees to study lingustic constructions.  This is easily
seen in sentence diagrams used to find subject, object, verb,
prepositions, clauses, etc.

-------(6)-------
Sorting algorithms can be modeled as trees, and the speed of the
algorithm can be checked by the number of final states.  Bubble sort
and heap sort can be easily shown and studied in this way.

-------(7)-------
As a final thought from my experience: one of the key algorithms in
linear programming is the simplex algorithm.  The simplex algorithm is
used to find optimal solutions in areas such as telecommunications,
routing, shipping, and many others.  The simplex algorithm can be
considered as finding the optimal path between nodes (feasible
solutions) without ever returning to the same node (as cycles do not

-----------------

and in the bigger picture all of mathematics.

-Doctor Keith,  The Math Forum
Check out our web site!  http://mathforum.org/dr.math/
```
Associated Topics:
High School Discrete Mathematics

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search