ing changing population patterns or business locations. For example, railroads and traditional phone sys- tems tend to be the products of long-term evolution instead of rational design. In this section, we consider some basic types of networks that are useful in simplify- ing discussions of network design (see also Wilson and Beineke 1979, offering an introduction to different types of graphs). One basic network directly links every pair of nodes. This type of network is represented by what is called a complete graph. If such a network has n nodes, then it will have n(n-1) links. For example, Figure 1.9 has six nodes and fifteen links. We refer to this type of network as a point-to-point network. For example, an airline that connects all of its origins and destinations with direct flights has a route structure that is a point-to-point network. Such a network involves the greatest number of links and can potentially be replaced by an alternative network with fewer links that connect the nodes at least indirectly. If the links are costly, then it can be very inefficient to maintain such dedicated links. When switching is expensive but transportation or transmission links are relatively less costly, a point- to-point network can be desirable. Southwest Airlines operated a point-to-point network structure to connect lower congestion second-tier airports, avoiding the high time costs to passengers of changing planes at larger airports and the high costs of landing rights at those airports. They further benefited from operating efficiencies associated with longer flights in comparison to multiple short flights. The Structure and Functions of Networks Figure 1.10. A star graph representing a hub-and-spoke network. An alternative to the point-to-point network is a hub-and-spoke network. The hub-and-spoke network is represented by a star graph. Figure 1.10 shows a star graph that connects six terminal nodes to a hub that is a central node, with six links that resemble the spokes of a wheel. Many major airlines operate hub