What is a minimal spanning tree and how do I find it for a given cost matrix?

[slain4ever]

Homework Statement

The costs (in millions of dollars) of connecting any two of the four cities A,B,C and D by telephone lines are given in the following matrix:

0 3 5 4
3 0 2 3
5 2 0 6
4 3 6 0

a) Draw a diagram of the complete graph
b) find a minimal spanning tree

The Attempt at a Solution

I honestly have no idea what the question is even asking.

my best guess is that I need to draw a cost vs city bar graph so 2-6 million dollars on the y axis, then fill in for A-B, A-C etc.
is that right?

And I am not 100% sure about minimal spanning trees either. Would you draw 4 vertices labelled A to D then on the connecting lines fill in the proper cost values?

 

[slain4ever]

bump?

 

[Kreizhn]

A graph is a collection of vertices and edges. Your matrix describes the http://en.wikipedia.org/wiki/Graph_%28mathematics%29" . Algorithms for calculating spanning trees are well known and can be found in any introductory book on graph theory.

 

[Kreizhn]

Note that the wiki-link I gave you on spanning trees also hyperlinks to minimal spanning trees. Links to algorithms are supplied therein.

 

[Bacle]

Notice that trees satisfy the relation V=E+1 , where V,E are the number of vertices, edges
resp in the tree. First, make sure your tree is connected (A tree is a graph that is
connected, but has no loops. You need to find a subset of your graph that goes
thru every vertex, but has no loops).

So start at any vertex v , and join v to some edge v1 so that v1 is " 1 away" from
v, i.e., there is a path vev1 of length 1 from v to v1 . Then you have a subgraph
{v,v1,e} , with 2 vertices and 1 edge, i.e., a tree. Continue with the idea until the
tree spans, i.e., until the graph uses all the vertices (again, make sure your graph is
connected.) Can you take it from there?