Minimum Spanning Tree
Written by Mike James   
Monday, 04 January 2010
Article Index
Minimum Spanning Tree
Prim's algorithm
Implementing Prim's algorithm

Graphs

In computer science and discrete mathematics a graph is a set of points – called vertices or nodes and a set of connecting lines called paths, arcs or edges. This definition of a graph includes the familiar temperature charts etc but only as a special case. In this sense a graph is anything from a hierarchy chart to a computer network.


Graph


A simple graph of vertices and arcs

Graphs are important in computer science as a basic tool of theory and they are of practical importance. Before we can go on to explain why we need some additional definitions:

  • A path is a route from one vertex to another via arcs.
  • If there is a path between every pair of vertices the graph is a "connected graph".
  • A path from a given vertex and back again is called a cycle.

path

A connected graph showing a path and a cycle

Now we can define a tree – a tree is a connected graph with no cycles. There are many equivalent definitions of a tree including the one that gives it its name –  a root node connected to leaf nodes by branches.


tree

Check that this is a connected graph with no cycles – aka a tree!

A slightly more advanced form of graph is the network. A network is a graph which has weights assigned to each of its paths. You can think of each weight as either being a distance or a cost associated with the path. With networks you can ask questions such as "find the shortest path", "find the shortest round trip" and so on.

MST = Minimum Spanning Tree

One important version of this "shortest" type of question is – what is the shortest connector. That is, the sub-graph with the shortest total distance that connects all of the vertices.

It doesn't take much to see the shortest sub-graph that connects all of the vertices is going to be a tree because if it contains any cycles you can get a shorter graph by deleting at least one arc without altering the connectivity. As a result this problem is often called finding the "minimum spanning tree", MST.

Why is the MST important?

Consider the situation that you have to connect three computer sites into a network. All you care about is that every computer is connected and the cost of connection is proportional to distance. In this case the minimum spanning tree is going to be a good starting point for a practical implementation of the network.

Another, slightly more esoteric, example of the usefulness of an MST is that it provides an upper bound to the travelling salesman problem. The travelling salesman's round route has to be shorter than twice the MST for the network.

<ASIN:1584883960>

<ASIN:0201000237>



Last Updated ( Wednesday, 31 March 2010 )
 
 

   
RSS feed of all content
I Programmer - full contents
Copyright © 2014 i-programmer.info. All Rights Reserved.
Joomla! is Free Software released under the GNU/GPL License.