1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Matrices and spanning trees

  1. Sep 30, 2011 #1
    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. jcsd
  3. Oct 2, 2011 #2
  4. Oct 2, 2011 #3
    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
  5. Oct 2, 2011 #4
    Note that the wiki-link I gave you on spanning trees also hyperlinks to minimal spanning trees. Links to algorithms are supplied therein.
  6. Oct 2, 2011 #5
    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?
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook