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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.