Minimum spanning tree algorithm

minimum spanning tree applications and minimum spanning tree definition
Dr.SethPatton Profile Pic
Dr.SethPatton,United Kingdom,Teacher
Published Date:22-07-2017
Your Website URL(Optional)
Comment
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 © 2006-2013 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 sub-graph 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 © 2006-2013 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 lowest-cost 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 safely?Minimum 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- networks