# Homework Help: Matrices and spanning trees

1. Sep 30, 2011

### slain4ever

1. The problem statement, all variables and given/known data
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

3. 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?

2. Oct 2, 2011

bump?

3. Oct 2, 2011

### Kreizhn

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

Last edited by a moderator: May 5, 2017
4. Oct 2, 2011

### Kreizhn

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

5. Oct 2, 2011

### 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?