NETWORK OPTIMIZATION MODELS:THE TERMINOLOGY OF NETWORKS

THE TERMINOLOGY OF NETWORKS

A relatively extensive terminology has been developed to describe the various kinds of networks and their components. Although we have avoided as much of this special vocabulary as we could, we still need to introduce a considerable number of terms for use throughout the chapter. We suggest that you read through this section once at the outset to understand the definitions and then plan to return to refresh your memory as the terms are used in subsequent sections. To assist you, each term is highlighted in boldface at the point where it is defined.

A network consists of a set of points and a set of lines connecting certain pairs of the points. The points are called nodes (or vertices); e.g., the network in Fig. 10.1 has seven nodes designated by the seven circles. The lines are called arcs (or links or edges or branches); e.g., the network in Fig. 10.1 has 12 arcs corresponding to the 12 roads in the road system. Arcs are labeled by naming the nodes at either end; for example, AB is the arc between nodes A and B in Fig. 10.1.

The arcs of a network may have a flow of some type through them, e.g., the flow of trams on the roads of Seervada Park in Sec. 10.1. Table 10.1 gives several examples of flow in typical networks. If flow through an arc is allowed in only one direction (e.g., a one-way street), the arc is said to be a directed arc. The direction is indicated by adding an arrowhead at the end of the line representing the arc. When a directed arc is labeled by listing two nodes it connects, the from node always is given before the to node; e.g., an arc that is directed from node A to node B must be labeled as AB rather than BA. Alternatively, this arc may be labeled as A --- B.

If flow through an arc is allowed in either direction (e.g., a pipeline that can be used to pump fluid in either direction), the arc is said to be an undirected arc. To help you distinguish between the two kinds of arcs, we shall frequently refer to undirected arcs by the suggestive name of links.

Although the flow through an undirected arc is allowed to be in either direction, we do assume that the flow will be one way in the direction of choice rather than having

simultaneous flows in opposite directions. (The latter case requires the use of a pair of directed arcs in opposite directions.) However, in the process of making the decision on the flow through an undirected arc, it is permissible to make a sequence of assignments of flows in opposite directions, but with the understanding that the actual flow will be the net flow (the difference of the assigned flows in the two directions). For example, if a flow of 10 has been assigned in one direction and then a flow of 4 is assigned in the opposite di- rection, the actual effect is to cancel 4 units of the original assignment by reducing the flow in the original direction from 10 to 6. Even for a directed arc, the same technique some- times is used as a convenient device to reduce a previously assigned flow. In particular, you are allowed to make a fictional assignment of flow in the “wrong” direction through a di- rected arc to record a reduction of that amount in the flow in the “right” direction.

A network that has only directed arcs is called a directed network. Similarly, if all its arcs are undirected, the network is said to be an undirected network. A network with a mixture of directed and undirected arcs (or even all undirected arcs) can be converted to a directed network, if desired, by replacing each undirected arc by a pair of directed arcs in opposite directions. (You then have the choice of interpreting the flows through each pair of directed arcs as being simultaneous flows in opposite directions or providing a net flow in one direction, depending on which fits your application.)

When two nodes are not connected by an arc, a natural question is whether they are connected by a series of arcs. A path between two nodes is a sequence of distinct arcs connecting these nodes. For example, one of the paths connecting nodes O and T in Fig. 10.1 is the sequence of arcs OB–BD–DT (O --- B --- D --- T ), or vice versa. When some of or all the arcs in the network are directed arcs, we then distinguish between directed paths and undirected paths. A directed path from node i to node j is a sequence of connecting

arcs whose direction (if any) is toward node j, so that flow from node i to node j along this path is feasible. An undirected path from node i to node j is a sequence of connecting arcs whose direction (if any) can be either toward or away from node j. (Notice that a directed path also satisfies the definition of an undirected path, but not vice versa.) Frequently, an undirected path will have some arcs directed toward node j but others directed away (i.e., toward node i). You will see in Secs. 10.5 and 10.7 that, perhaps surprisingly, undirected paths play a major role in the analysis of directed networks.

To illustrate these definitions, Fig. 10.2 shows a typical directed network. (Its nodes and arcs are the same as in Fig. 3.13, where nodes A and B represent two factories, nodes D and E represent two warehouses, node C represents a distribution center, and the arcs represent shipping lanes.) The sequence of arcs AB–BC–CE (A --- B --- C --- E) is a directed path from node A to E, since flow toward node E along this entire path is feasible. On the other hand, BC–AC–AD (B --- C --- A --- D) is not a directed path from node B to node D, because the direction of arc AC is away from node D (on this path). However, B --- C --- A --- D is an undirected path from node B to node D, because the sequence of arcs BC–AC–AD does con- nect these two nodes (even though the direction of arc AC prevents flow through this path).

As an example of the relevance of undirected paths, suppose that 2 units of flow from node A to node C had previously been assigned to arc AC. Given this previous assign- ment, it now is feasible to assign a smaller flow, say, 1 unit, to the entire undirected path B --- C --- A --- D, even though the direction of arc AC prevents positive flow through C --- A. The reason is that this assignment of flow in the “wrong” direction for arc AC actually just reduces the flow in the “right” direction by 1 unit. Sections 10.5 and 10.7 make heavy use of this technique of assigning a flow through an undirected path that in- cludes arcs whose direction is opposite to this flow, where the real effect for these arcs is to reduce previously assigned positive flows in the “right” direction.

A path that begins and ends at the same node is called a cycle. In a directed net- work, a cycle is either a directed or an undirected cycle, depending on whether the

path involved is a directed or an undirected path. (Since a directed path also is an undirected path, a directed cycle is an undirected cycle, but not vice versa in general.) In Fig. 10.2, for example, DE–ED is a directed cycle. By contrast, AB–BC–AC is not a directed cycle, because the direction of arc AC opposes the direction of arcs AB and BC. On the other hand, AB–BC–AC is an undirected cycle, because A --- B --- C --- A is an undirected path. In the undirected network shown in Fig. 10.1, there are many cycles, for example, OA–AB–BC–CO. However, note that the definition of path (a sequence of distinct arcs) rules out retracing one’s steps in forming a cycle. For ex- ample, OB–BO in Fig. 10.1 does not qualify as a cycle, because OB and BO are two labels for the same arc (link). On the other hand, DE–ED is a (directed) cycle in Fig. 10.2, because DE and ED are distinct arcs.

Two nodes are said to be connected if the network contains at least one undirected path between them. (Note that the path does not need to be directed even if the network is directed.) A connected network is a network where every pair of nodes is connected. Thus, the networks in Figs. 10.1 and 10.2 are both connected. However, the latter network would not be connected if arcs AD and CE were removed.

Consider a connected network with n nodes (e.g., the n = 5 nodes in Fig. 10.2) where all the arcs have been deleted. A “tree” can then be “grown” by adding one arc (or “branch”) at a time from the original network in a certain way. The first arc can go anywhere to con- nect some pair of nodes. Thereafter, each new arc should be between a node that already is connected to other nodes and a new node not previously connected to any other nodes. Adding an arc in this way avoids creating a cycle and ensures that the number of con- nected nodes is 1 greater than the number of arcs. Each new arc creates a larger tree, which is a connected network (for some subset of the n nodes) that contains no undirected cycles. Once the (n - 1)st arc has been added, the process stops because the resulting tree spans (connects) all n nodes. This tree is called a spanning tree, i.e., a connected net- work for all n nodes that contains no undirected cycles. Every spanning tree has exactly n - 1 arcs, since this is the minimum number of arcs needed to have a connected network and the maximum number possible without having undirected cycles.

Figure 10.3 uses the five nodes and some of the arcs of Fig. 10.2 to illustrate this process of growing a tree one arc (branch) at a time until a spanning tree has been obtained. There are several alternative choices for the new arc at each stage of the process, so Fig. 10.3 shows only one of many ways to construct a spanning tree in this case. Note, however, how each new added arc satisfies the conditions specified in the preceding paragraph. We shall discuss and illustrate spanning trees further in Sec. 10.4.

Spanning trees play a key role in the analysis of many networks. For example, they form the basis for the minimum spanning tree problem discussed in Sec. 10.4. Another prime example is that (feasible) spanning trees correspond to the BF solutions for the net- work simplex method discussed in Sec. 10.7.

Finally, we shall need a little additional terminology about flows in networks. The maximum amount of flow (possibly infinity) that can be carried on a directed arc is referred to as the arc capacity. For nodes, a distinction is made among those that are net generators of flow, net absorbers of flow, or neither. A supply node (or source node or source) has the property that the flow out of the node exceeds the flow into the node. The reverse case is a demand node (or sink node or sink), where the flow into the node exceeds the flow out of the node. A transshipment node (or intermediate node) satisfies conservation of flow, so flow in equals flow out.