Minimum Spanning Tree - Term Paper Example

Minimum Spanning Tree A minimum spanning tree is a system or network of arcs with its corresponding weight or cost which creates a tree that minimizes the cost of every arc in the system, this is also known as the MST. A MST is a sub graph of a spanning tree’s graph that contains edges and vertices corresponding to specific factors and unit of measure. A MST is applied in businesses to cut cost and save money and time in their operation that is why it is called minimum spanning tree because it minimizes certain units of measure. A good example that would reciprocate the MST model is the Single Vehicle Routing: The Traveling Salesman Problem. A traveling salesman travels to different places in order to do his work effectively and efficiently. And by traveling, the salesman needs money to pay for his expenses which is shouldered by the company. Also looking at the company’s side, they would also want to cut cost on the expenses but still lets the traveling salesman do his work efficiently. So the company applies MST to this problem. In order to minimize on expenses, time and distance traveled, the company should implement MST to derive an optimal solution for the sequence of route for the traveling salesman. As stated above, the MST contains arcs and vertices which will be represented by the points of visitation and the sequence of route of the traveling salesman. This point of visitation will act as vertices or nodes on the graph and the arc will represent the sequence of route of the traveling salesman. In order to cut cost on the operational expenses we have to have a good sequence of route for the traveling salesperson so that he would not be going back and forth or revisiting a certain point more than once, we are implementing this in order to save and cut cost. We can determine this sequence of route by finding the MST of the problem. Here are three algorithms in which can identify the MST of the problem and these are Kruskal’s algorithm, Prism’s algorithm and Heuristic’s algorithm. There are two primary steps in Kruskal’s algorithm, the first step is that we need to gather or sort the arcs and search for cycles at each repetition or iteration of the search; this sortation will require time especially when dealing with large arcs, meaning longer routes for the traveling salesman. And in searching for cycles in each repetition or iteration we have to keep the arc that was determined in the minimum spanning tree in the protection of a forest data structure where the elements in the forest data structure is a subset of nodes on a tree also known as the subtree. And when we want to add points in the subtree, let say (i , j) which would represent the traveling salesman’s visitation points, we would then scan the subtree list to determine if this points is not yet in the sequence of route of the traveling salesman, then we can add the points, but if the points are already in the sequence of route of the traveling salesman then we do not add this points because it would create a cycle which would mean that time, distance and expenses isn’t minimized in this problem. Kruskal’s algorithm will require time to study the points of visitation and sequence of route in order for implementation to be effective and efficient. In Prism’s algorithm, we need to absorb the cut concept in a system because in Prism’s algorithm the subsets are divided into two. In Prism’s algorithm we need to identify a single arc, let say (S, T) in which we can move to the MST. In order to determine total complexity of the arcs, we need to scan each arc to know if it cost less than the current minimum. We can also improve the complexity level by identifying the minimum inbound cost because by doing this we can simply amend the labels after each iteration or repetition is added with a new point of visitation or node by scanning all the arcs. Then we can add a node or a point of visitation in the traveling salesman’s sequence of route by placing the minimum label to the MST model. Another solution that would provide feasible solution to the traveling salesman’s problem is the Heuristic algorithm. Heuristic algorithm provides solutions that are close and parallel to the optimal solution. And these solutions can work in efficiency under practical running time and in theoretical terms. There are steps needed to be followed in applying Heuristic algorithm for the traveling salesman’s problem. First step is we must produce a minimum spanning tree for the node; we have already identified how to find the MST above. Second step is we have to have two copies of the LIST of each arc within the MST. Third step is, using the LIST we have; we will produce a WALK of nodes of each arc. Forth step, using the nodes generated from the third step, we have to create a Heuristic tour in the specific order that is found in the WALK, and during this step we should take shortcuts in order to avoid repeated visits to any node or point of visitation. So in order to identify the Heuristic tour we have to eliminate all nodes that are visited several times. Also Heuristic tour is also known as embedded tour. Another heuristic approach to the traveling salesman’s problem is the Christofides’ Heuristic. Christofides’ Heuristic is known for its sufficient networks fulfilling the triangle-inequity for the worst – case performance bound of the traveling salesman’s problem. Christofides’ Heuristic also practices the approach of minimum cost perfect matching, also known as MCPM which can be applied in businesses. Here are the necessary steps needed to be followed in order for Christofides’ Heuristic to be successfully implemented. First is we should complete the network, let say (G) represents the network fulfilling the triangle – inequality then find the MST on the Network which is (G). Second is we will let (S) represent the nodes of the network that would be in line with the MST with an odd degree. Third is that we should accumulate a perfect node matching represented by W* with its set of nodes within its minimum total cost. And forth is, we should produce a tour of nodes represented by Tc working with the set of arcs which did not revisit any nodes or point of visitation more than once to minimize total cost. Applying the minimum spanning tree model in a business setting will allow the business to grow and develop as a whole and as a community because MST will minimize the company’s total cost. Minimum Spanning tree model will provide optimal solutions with algorithms that would cut cost on operational factors such as distance traveled, time and expenses using its vertices and arcs within the graph that would make the business operate effectively and efficiently. These vertices and arcs will represent as points and sequences of the problem that would allow the algorithms to make these arcs and vertices to act as a basis in coming up with an optimal solution for the problem. Basing from our example which is the traveling salesman, it has allowed Kruskal’s algorithm, Prism’s algorithm and Heuristics algorithm to find its minimum spanning tree. We have generated points and sequences that would build our vertices and arcs in order to determine how we can minimize the total cost, by not revisiting a specific node or point of visitation within the sequence or the arc. Any business would want to cut cost on their expenses because it will allow them to generate more profit and sales if they have cut cost on their operational, production expenses and etc. Minimum spanning tree model will help businesses determine the best way to minimize the company’s cost because it contains and illustrates points and nodes that would lead to the minimization of using one’s resources in the business but will still allow its operation to work on an effective and efficient manner, just like our example above. The minimum spanning tree model has allowed the traveling salesman to work effectively and efficiently with less cost with the help of the MST model because he has determined points and sequence of route that would illustrate him where to go first and which way to go in order to avoid revisits of a specific point in his travel and to avoid cycles which would mean he is traveling in the best way and in the shortest distance which would also allow him to save on travel expenses. Businesses must implement minimum spanning tree model to their system because it would be very productive for their operation and that it would allow businesses to utilize their resources and efforts well. Minimum spanning tree model’s primary aim is to generate a system in which networks and all types of businesses can operate competently using minimal resources. Works Cited gradroutingA.”Minimum Spanning Tree” isye.gatech.edu.n.d.web.20 July 2011. GeeksforGeeks.”Applications of Minimum Spanning Tree Problem”geeksforgeeks.org. 04 March 2011.web.20 July 2011 ICS161.”Design and Analysis for Algorithms”. ics.uci.edu.06 Feb 1996.web. 20 July 2011 Read More