Spanning Tree Essay, Research Paper
A spanning tree is an application of a network. There is another type of spanning tree called the minimum spanning tree. This data structure is used in many business applications. I will be discussing what a spanning tree is and what a minimum spanning tree is, and how they work. I will also discuss how spanning trees are used in every day business.
A spanning tree of a graph is just a subgraph that contains all the vertices and is a tree. A graph may have many spanning trees for instance the complete graph on four vertices has sixteen spanning trees.
A minimum spanning tree is a spanning tree in which the total weight of the lines is guaranteed to be the minimum of all possible trees in the graph. The weight of a tree is just the sum of weights of its edges, because different trees have different lengths you run in the problem of how to find the minimum length spanning tree. The problem can be solved by using an algorithm for the minimum spanning tree.
There are many algorithms written on minimum spanning trees, here are two of the most common Prim s algorithm and Kruskal s algorithm.
Prim s algorithm for the minimum spanning tree problem follows the strategy of beginning with a small tree and growing it until it includes all vertices in the given graph. Initially the tree contains just an arbitrary starting node. At each stage a vertex not yet in the tree but closest to some vertex that is in the tree is found. This closest vertex is added to the tree. Finding the vertex allows you to improve your knowledge of the distance of the remaining vertices in the tree. A set done contains the vertices in the tree. Prim s algorithm is correct because at each stage it has built a minimum spanning tree over those vertices in the set done which eventually contain all the vertices.
Krushal s algorithm for the minimum spanning tree problem begins with many disjoint spanning trees, a spanning forest. It repeatedly joins two trees together until a spanning tree of the entire given graph remains.
You may ask yourself why minimum spanning trees. A standard application of a minimum spanning tree is a problem like phone network design. You have a business with several offices, you want to lease phone lines to connect them up with each other, and the phone company charges different amounts of money to connect different pairs of cities. You want a set of lines that connects all your offices with a minimum total cost. It should be a spanning tree, since if a network isn t a tree you can always remove some edges and money.
Another application is that he minimum spanning tree can be used to approximately solve the traveling salesman problem. A formal way of defining this problem is to find the shortest path that visits each point at least once. If you have a path visiting all points exactly once it s a special kind of tree. For instance in the definition of a spanning tree at the beginning of my paper I said that a complete graph on four vertices has sixteen spanning trees, well twelve of the sixteen spanning trees are actually paths. If you have a path visiting some vertices more than once you can always drop some edges to get a tree. So the minimum spanning tree is less than the total weight, because it s a minimization over a larger set.
In conclusion we have seen what a spanning tree is and what a minimum spanning tree is. These two types of trees are important to networking. You can see how important spanning trees are to every day business.