# Minimum spanning tree

###### Minimum spanning tree
ECE 250 Algorithms and Data Structures Minimum Douglas Wilhelm Harder, M.Math. LEL spanning tree Department of Electrical and Computer Engineering University of Waterloo Waterloo, Ontario, Canada ece.uwaterloo.ca dwharderalumni.uwaterloo.ca © 20062013 by Douglas Wilhelm Harder. Some rights reserved.Minimum spanning trees 2 Outline In this topic, we will – Define a spanning tree – Define the weight of a spanning tree in a weighted graph – Define a minimum spanning tree – Consider applications – List possible algorithmsMinimum spanning trees 3 Spanning trees Given a connected graph with V = n vertices, a spanning tree is defined a collection of n– 1 edges which connect all n vertices – The n vertices and n– 1 edges define a connected subgraph A spanning tree is not necessarily uniqueMinimum spanning trees 4 Spanning trees This graph has 16 vertices and 35 edgesMinimum spanning trees 5 Spanning trees These 15 edges form a minimum spanning treeMinimum spanning trees 6 Spanning trees As do these 15 edges:Minimum spanning trees 7 Spanning trees Such a collection of edges is called a tree because if any vertex is taken to be the root, we form a tree by treating the adjacent vertices as children, and so on...Minimum spanning trees 8 Spanning trees Nor do they necessarily have nice propertiesMinimum spanning trees 9 Spanning trees on weighted graphs The weight of a spanning tree is the sum of the weights on all the edges which comprise the spanning tree – The weight of this spanning tree is 20Minimum spanning trees 10 Minimum Spanning Trees Which spanning tree which minimizes the weight – Such a tree is termed a minimum spanning tree The weight of this spanning tree is 14Minimum spanning trees 11 Minimum Spanning Trees If we use a different vertex as the root, we get a different tree, however, this is simply the result of one or more rotationsECE 250 Algorithms and Data Structures Douglas Wilhelm Harder, M.Math. LEL Department of Electrical and Computer Engineering University of Waterloo Waterloo, Ontario, Canada ece.uwaterloo.ca dwharderalumni.uwaterloo.ca © 20062013 by Douglas Wilhelm Harder. Some rights reserved.Minimum spanning trees 13 Unweighted graphs Observation – In an unweighted graph, we nominally give each edge a weight of 1 – Consequently, all minimum spanning trees have weight V – 1Minimum spanning trees 14 Application Consider supplying power to – All circuit elements on a board – A number of loads within a building A minimum spanning tree will give the lowestcost solution www.kpmb.com www.commedore.caMinimum spanning trees 15 Application The first application of a minimum spanning tree algorithm was by the Czech mathematician Otakar Borůvka who designed electricity grid in Morovia in 1926 www.kpmb.com www.commedore.caMinimum spanning trees 16 Application Consider attempting to find the best means of connecting a number of LANs – Minimize the number of bridges – Costs not strictly dependant on distancesMinimum spanning trees 17 Application A minimum spanning tree will provide the optimal solutionMinimum spanning trees 18 Application Consider an ad hoc wireless network – Any two terminals can connect with any others Problem: – Errors in transmission increase with transmission length – Can we find clusters of terminals which can communicate safelyMinimum spanning trees 19 Application Find a minimum spanning treeMinimum spanning trees 20 Application Remove connections which are too long This clusters terminals into smaller and more manageable sub networksMinimum spanning trees 21 Algorithms Two common algorithms for finding minimum spanning trees are: – Prim’s algorithm – Kruskal’s algorithmMinimum spanning trees 22 Summary This topic covered – The definition of spanning trees, weighted graphs, and minimum spanning trees – Applications generally involve networks (electrical or communications) – Two algorithms are Prim’s and Kruskal’sMinimum spanning trees 23 References Wikipedia, http://en.wikipedia.org/wiki/Minimumspanningtree These slides are provided for the ECE 250 Algorithms and Data Structures course. The material in it reflects Douglas W. Harder’s best judgment in light of the information available to him at the time of preparation. Any reliance on these course slides by any party for any other purpose are the responsibility of such parties. Douglas W. Harder accepts no responsibility for damages, if any, suffered by any party as a result of decisions made or actions based on these course slides for any other purpose than that for which it was intended.
Website URL
Comment
Presentations
Free
Category:
Presentations
User Name:
Dr.SethPatton
User Type:
Teacher
Country:
United Kingdom