Difference between revisions of "Walther MA279 Spring2016 topic5" - Rhea

Revision as of 22:17, 24 April 2016

group c

Historical Notes

The idea of kruskal's algorithm came from the problem of seven bridge of Königsberg. In the city of Konigsberg, in the east Prussia(now the city is belonged to Russia), 7 bridges connected two island in the river and the mainland of both sides. Leonhard Euler wanted to find out if there is a way to devise a walk through the city that would cross each bridge only once. Euler failed to do that but he came up the way to prove that it is impossible. He developed the theorem to figure out at what circumstance one is able to finish the path without turning back. That is Euler's theorem we learned in class. The contribution of Euler is he laid the foundations of graph theory and prefigured the idea of topology. Now, we can turn all the path problem into points and bridges.This is the foundation of the problem we are talking about, Kriskal's algorithm.

KRUSKAL

Kruskal's algorithm(similar to cheapest-link algorithm) is an algorithm used for computing the minimum spanning tree of a undirected edge-weighted graph.

Kruskal's algorithm works by choosing, on each iteration, the cheapest possible edge that does not create a cycle with edges already on the tree. Thus, generally, Kruskal's algorithm builds the MST by creating many disjoint trees that eventually coalesce into one spanning tree. For a visualization, see here (try the large graph to see how Kruskal creates disjoint trees along the way).

PRIM

The main alternative to Kruskal's algorithm for computing a minimum spanning tree is known as Prim's algorithm. Prim's algorithm computes the MST by adding edges to a single connected tree until all vertices have been included in the tree. In other words, start at an arbitrary vertex. Then add the cheapest edge that connects a vertex on the tree to a non-tree vertex. Repeat this procedure until V-1 edges have been added(a tree of a graph has exactly V-1 edges assuming the graph is connected). For a visualization of Prim's algorithm, see here.

For another example of Prim's algorithm:

   G-C       3
   E-D       8
   D-H       6
   I-D       1
   J-E      15
   I-E      11
   G-F      16
   H-G      13
   I-H      12
   J-I       9

Represented graphically as:

   (A)------14-----(B)------2------(C)------10-----(D)------8------(E)
    |              /|              /|              /|              /| 
    |             / |             / |             / |             / | 
    |            /  |            /  |            /  |            /  | 
    |           /   |           /   |           /   |           /   | 
    |          /    |          /    |          /    |          /    | 
    |         /     |         /     |         /     |         /     | 
    |        /      |        /      |        /      |        /      | 
    5       7       17      3       4       6       1       11      15
    |      /        |      /        |      /        |      /        | 
    |     /         |     /         |     /         |     /         | 
    |    /          |    /          |    /          |    /          | 
    |   /           |   /           |   /           |   /           | 
    |  /            |  /            |  /            |  /            | 
    | /             | /             | /             | /             | 
    |/              |/              |/              |/              | 
   (F)------16-----(G)------13-----(H)------12-----(I)------9------(J)

If we start Prim's algorithm from G, the order in which edges are added to the MST (edge specified by weight) is :

3 2 4 6 1 7 5 8 9

Note that it is not necessary that edges are added from cheapest to most expensive, as is the case for Kruskal. Also, note how the edges added form one connected tree at each stage, which is not necessarily true of Kruskal.

CUT PROPERTY

A cut of a graph divides the vertices into two nonempty disjoint sets. A crossing edge of the cut is any edge that connects vertices in different sets.

The cut property states that given any cut in the graph, the cheapest crossing edge must be in the MST.
Proof: Assume distinct edge weights, although it is clear that if two crossing edges are both the cheapest, either can be included. The proof is by contradiction. Define e to the cheapest crossing edge and let T* be the MST. Suppose T* does not contain e. Then T* must contain some other crossing edge f(since the MST is connected). If we add e to T*, we now get a cycle. Since e was defined to be the cheapest crossing edge, we can remove f from T* and we now have an MST of lower weight (removing an edge in a cycle doesn't affect connectedness). But this is a contradiction to the definition of T* meaning e must be in T*.

The reason Kruskal and Prim correctly compute the MST is due to the Cut Property. As outlined in the procedure for Prim above, at each stage Prim looks at the set of edges connecting tree vertices to non-tree vertices(i.e crossing edges). Prim then selects the cheapest crossing edge which, by the Cut Property, must be in the MST. After V-1 iterations, Prim has selected V-1 edges that all belong to the MST. Since there are exactly V-1 edges in the MST, Prim must have computed the MST.

RUNNING TIME

Depending on the implementation, Prim can run in time O(ElogE) or O(ElogV). Both implementations use a minimum priority queue to support the operations of finding the minimum crossing edge. However, the logE version is known as "lazy" Prim since it allows edges no longer eligible to be added to the tree to remain on the priority queue. The logV version is known as "eager" Prim, and stores only eligible edges on the priority queue.

Borůvka

There is another alternative to Kruskal's algorithm is Borůvka's algorithm.Borůvka's algorithm is an algorithm for finding a MST in a graph for which all edge weights are distinct. The way to use this algorithm is first to mark every vertex and finding the cheapest edge for each vertex and no matter the edges already added. And use this way until a tree spaning all vertices is completed. Here is a example to use the Borůvka's algorithm:

First mark each vertex in the graph.

Then, find the minimum edge for every vertice.(Some of them add twice,like AD,CE,it's OK). Now this graph divide to two part:{A,B,D,F} and {C,E,G}

Now add the minimun edge between this two part. It is the same edge,BE/EB. Finally, there is the MST.

Also, there is an animation to show the process of Borůvka's algorithm. click.

CONCLUSION

All three algorithms are greedy algorithms and each of them has the same worst-case running time. Kruskal's algorithm starts with an edge, Prim's algorithm starts with a vertex and Borůvka's algorithm start to find the minimum edge for a vertex. Kruskal's algorithm and Borůvka's algorithm can function on disconnected graphs but in Prim's algorithm, the graph must be connected. Different structure and data cause different approach to application. These three algorithms can be used to find the MST, which could be used in computer networking or laying cable in a wide area in the real world.

Reference

Igor Podsechin,Tampereen lyseon lukio,Tietotekniikka,"Comparing minimum spanning tree algorithms"http://www2.aka.fi/Tiedostot/Tiedostot/Viksu/Viksu%202008/IgorPodsechin.pdf

Pallavi Jayawant and Kerry Glavin(Communicated by Arthur T. Benjamin),"Minimum spanning trees ",2009.http://msp.org/involve/2009/2-4/involve-v2-n4-p06-p.pdf

Borůvka's algorithm themorem ,https://en.wikipedia.org/wiki/Bor%C5%AFvka%27s_algorithm

Yvette (I-Ting) Tsai,"A Randomized Algorithm to Find Minimum Spanning Tree",Dec 5, 2013.http://cs-www.bu.edu/faculty/homer/537/talks/Tsai-CS537_Report.pdf