Heuristics: Minimal Spanning Tree 2
Inhaltsverzeichnis
Theory
A graph is a tree if there is a chain between every pair of nodes and if it contains no cycles. A spanning tree is a tree in which every pair of nodes is connected with a unique chain of the tree. This spanning tree is used in the minimal spanning tree problem, which is an optimization problem. In most of the cases it’s used to link towns either directly or through others towns. The aim here is to have a minimal total length. Towns can be replaced by network of computer or other systems. The goal is then to find the minimal total cost to link these systems. It's based on this theorem : "If a (finite) connected graph has a positive real number attached to each edge (the length of the edge), and if these lengths are all distinct, then among the spanning'trees of the graph there is only one, the sum of whose edges is a minimum; that is, the shortest spanning tree of the graph is unique." This type of solution is popular because of the multiplicity of applications and its efficiency. For example, one needs only 10 minutes to solve a minimal spanning tree of 50 nodes with the Prim's algorithm. To solve a minimal spanning tree problem, we can use several algorithms which are different in their implementation. However two algorithms played a central role in the history and are now use to solve the type of problem.
The first algorithm is the Prim’s algorithm. He defines an isolated terminal as a node with which no connection have been made at the given stage of the construction. A fragment is also defined as a node directly connected with other nodes of a subtree. He based his theory on two principles:
•“Any isolated terminal can be connected to a nearest neighbor.”
•“Any isolated fragment can be connected to a nearest neighbor by a shortest available link.”
With this principles the solver can link every node to create a minimal spanning. Indeed it permits to reduce the nomber of isolated terminal and fragment to one.
The second used algorithm is the Kruskal's algorithm. The considered graph G has to be complete to perform this algortihm. That is to say that every node is at least to an other node or more. Here is the algorithm : "Among the edges of G not yet chosen, choose the shortest edge which does not form any loops with those edges already chosen. Clearly the set of edges eventually chosen must form a spanning tree of G, and in fact it forms a shortest spanning tree." One has to repeat this step as long as possible.
(To see the contruction of a minimal spanning tree with the Prim's or the Kruskal's algorithm in detail, go to "Detailed solution process with explanation")
Example
I would like to visit some of my friends in France this summer. But the road aren’t free in this country. Here are the cities I’d like to go and the cost of the use of every path.
To select the minimal cost path to join all of these, the construction of a minimal spanning is a solution to my problem. I can use either the kruskal's algorithm or the prim's algorithm to create it. Here is my solution with the minimal spanning tree. (To see the contruction of a minimal spanning tree in detail, go to "Detailed solution process with explanation")
Presentation of a problem
Consider the following communications network (Distance as evaluation of the edges)
We want to connect every system (node) with the others in the way that the distance between every system is minimal and there is only one way to go from one to another system. To do that, we can use 2 algorithms that have been explain before : Kruskal's and Prim's algorithm.
Detailed solution process with explanation
Kruskal's algorithm : With the Kruskal‘s algorithm, we have to list the existing link of our network in increrasing order. When two links have the same length, it doesn't have importance in which order they are. They only have to be together.
Sources
Domschke,et al.,Übungen und Fallbeispiele zum Operations Research, 5th edition, 2005.
Graham R.L. & Hell P. (1985): On the history of the minimum spanning tree problem. In: Annals of the history of computing, Vol.7, No. 1 (Jan. 1985), pp. 43-57.
Kruskal, J.B. Jr. (1956): On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem. In:Proceedings of the American Mathematical Society,Vol. 7, No. 1 (Feb., 1956), pp. 48-50.
Prim, R.C. (1957): Shortest connection networks and some generalizations. In: The bell system technical journal (Nov. 1957), pp. 1389-1401.
Radin, R. L. (1998): Optimization in Operations Research. New Jersey, Prentice Hall, pp. 522-523.
