Minimum Cost Communication Networks

Let points Ax, · · · , An in the plane represent n cities which require a communications network. Let N{i, j) denote the number of channels which the network must supply between and A}. The network sought must provide these channels at minimum cost. In calculating costs suppose that a monotone function j{N) represents the cost in dollars per mile to install N channels together along a common route. One possible network just connects each pair Ait A, by N(i, j) channels installed along a straight line path. This network will be called the complete network because the routes used form a complete graph. Fig. 1(a) is the complete network for a case with n = 4; the numbers on the lines are the N (i, j). The complete network makes each channel as short as possible; it is the cheapest network if f(N) = N. However, most situations have more complicated functions / (AO. In particular, there are usually some 'preliminary costs for surveying, obtaining the right-of-way, digging a trench, etc. These items have a non-zero cost /(0) dollars per mile regardless of how many channels are to be installed. In some cases preliminary costs may be so high that a network which merely minimizes preliminary costs is a reasonable choice. Such a network must minimize the total number of miles of right-of-way. For the example in Fig. 1 (a), the network which minimizes preliminary costs is Fig. 1(b) [or, more simply, Fig. 1(c)]. Such networks can be drawn with a ruler and compass in a finite (possibly large) number of steps (see Ref.