g the minimum-cost spanning tree. A network, in graph theory, is defined as a graph with numerical values assigned to the links. Figure 2.3 shows a complete graph with the costs of links and the least-cost spanning tree. The least-cost network can be found by Prim's algorithm (1957). Choose any node arbitrarily as the initial node and find the least-cost link connected to that node. Add that link and its end node to form the start of the tree. Find the least-cost link connected to that tree and add that link and its end node to the tree. Continue until all nodes are included. The design of a cost-minimizing network in the tree problem shows how networks are integrated. The final network design is the best selection from the set of Nn-2 alternative configurations. The links are not chosen individually, but reflect instead the best configuration, SO that the choices of what links to create are interdependent. Removing a link from the final network does more damage them simply breaking up the tree. If the network designer had known that such a link would be removed, the designer would have chosen an entirely different network configuration. Occupying the capacity of a link would have a similar effect, albeit on a lesser scale. This suggests that granting a third party access to a network element such as a link has complex consequences for the characteristics of the network. 3. Cost-Minimizing Design of a Cycle Network Consider the problem of a network designer who must choose a network that links a set of nodes in a complete cycle. This corresponds to the well-known traveling 2 A cycle that links all of the nodes in a graph is known as a Hamiltonian cycle. The Design and Costs of Networks Total cost = 29 The complete graph The least-cost cycle Total cost = 42 Total cost = 41 Figure 2.4. Choosing the least-cost cycle network. Total cost equals 29. salesman problem. A complete graph with four nodes is shown in Figure 2.3. The graph indicates the cost of establishing each of the links. The cycle network is useful for a