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 
in business circles.

  -------(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 
allow an answer).

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

Hope these examples help your students to see the benefit of trees, 
and in the bigger picture all of mathematics.

-Doctor Keith,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/