st of each link within the complete set. Not all of these links are necessary to achieve the desired network attributes. By only constructing the minimal set of links that are needed to achieve the desired network attributes, the network designer obtains a cost-minimizing network. The first network attribute we consider is one in which all nodes are linked together. In graph-theory terms, a graph that connects all of the nodes with the minimum number of links is known as a tree graph. A tree graph that connects all of the nodes in a network is known as a spanning tree. In a network with n nodes, such a spanning tree would consist of n - 1 links. A tree graph has no cycles, which are paths along which it is possible to pass through a succession of links and eventually return to the original node without crossing any link more than once. The network designer's problem is to find the least-cost tree that includes all of the desired nodes. In graph theory terms, this tree is a minimum spanning tree. The network designer begins with the complete graph, as shown in Figure 2.2. Then the network designer evaluates the cost of each link. Finally, the network designer chooses a tree that connects all of the nodes at the lowest cost, which is the minimum spanning tree. Finding the most efficient tree is complicated by the fact Networks in Telecommunications a. The complete graph b. The least-cost tree Figure 2.3. The least-cost minimum spanning tree network. Total cost is 5 + 6 + 8 = 19. that the number of spanning trees is very large for even a small number of nodes and quickly becomes extremely large as the number of nodes increases. Network designers resort to algorithms that run on computers to solve such problems. According to Cayley's formula (1889), the number of spanning trees in a graph with n nodes is nn where n is greater than 2. For four nodes there are sixteen possibilities, depicted in Figure 2.2. For ten nodes, there are 100 million possible configurations. Consider the network designer's problem when choosin