1991 Problem B:  Minimal Spanning Trees for a Communications Network
 

The cost for a communication line between two stations is proportional to the length of the line.  The cost for conventional minimal spanning trees of a set of stations can often be cut by introducing “phantom” stations and then constructing a new Steiner tree.  This divide allows costs to be cut by up to 14.4% (1 – √3/2).  Moreover, a network with n stations never requires more than n – 2 points to construct the cheapest Steiner tree.  Two simple cases follow:

 For local networks, it is often necessary to use rectilinear or “checkerboard” distances, instead of straight Euclidean lines.  Distances in this metric are computed as shown:

 Suppose you wish to design a minimum cost spanning tree for a local network with nine stations.  Their rectangular coordinates are:

             a (0, 15), b (5, 20), c (16, 24), e (33, 25), f (23, 11), g (35, 7), h (25, 0), I (10, 3).

 You are restricted to using rectilinear lines.  Moreover, all “phantom” stations must be located at lattice points (i.e., the coordinates must be integers).  The cost for each line is its length.  

  1. Find a minimal cost tree for the network.
  2. Suppose each station has a cost d3/2 x w, where d = degree of the station.  If w = 1.2, find a minimal cost tree.
  3. Try to generalize this problem.