Discrete Mathematics for Computer Science

Subsection 13.5.1 Weighted Graphs

As you will see in our examples, \(w(e)\) is often a cost associated with the edge \(e\text{;}\) therefore, most weights will be positive.

Subsection 13.5.2 The Traveling Salesman Problem

The Traveling Salesman Problem is, given a weighted graph, to find a circuit \(\left(e_1, e_2,\ldots ,e_n\right)\) that visits every vertex at least once and minimizes the sum of the weights, \(\sum_{i=1}^n w\left(e_i\right)\text{.}\) Any such circuit is called an optimal path.

Some statements of the Traveling Salesman Problem require that the circuit be Hamiltonian. In many applications, the graph in question will be complete and this restriction presents no problem. If the weight on each edge is constant, for example, \(w(e) = 1\text{,}\) then an optimal path would be any Hamiltonian circuit.

The search for an efficient algorithm that solves the Traveling Salesman has occupied researchers for years. If the graph in question is complete, there are \((n -1)!\) different circuits. As \(n\) gets large, it is impossible to check every possible circuit. The most efficient algorithms for solving the Traveling Salesman Problem take an amount of time that is proportional to \(n 2^n\text{.}\) Since this quantity grows so quickly, we can't expect to have the time to solve the Traveling Salesman Problem for large values of \(n\text{.}\) Most of the useful algorithms that have been developed have to be heuristic; that is, they find a circuit that should be close to the optimal one. One such algorithm is the “closest neighbor” algorithm, one of the earliest attempts at solving the Traveling Salesman Problem. The general idea behind this algorithm is, starting at any vertex, to visit the closest neighbor to the starting point. At each vertex, the next vertex that is visited is the closest one that has not been reached. This shortsighted approach typifies heuristic algorithms called greedy algorithms, which attempt to solve a minimization (maximization) problem by minimizing (maximizing) the quantity associated with only the first step.

The closest neighbor circuit starting at A in Figure 13.5.7 is \((1,3,2,4,1)\text{,}\) with a cost of 29. The optimal path is \((1,2,3,4,1)\text{,}\) with a cost of 27.

Although the closest neighbor circuit is often not optimal, we may be satisfied if it is close to optimal. If \(C_{opt}\) and \(C_{cn}\) are the costs of optimal and closest neighbor circuits in a graph, then it is always the case that \(C_{opt}\leq C_{cn}\) or \(\frac{C_{cn}}{C_{opt}}\geq 1\text{.}\) We can assess how good the closest neighbor algorithm is by determining how small the quantity \(\frac{C_{cn}}{C_{opt}}\) gets. If it is always near 1, then the algorithm is good. However, if there are graphs for which it is large, then the algorithm may be discarded. Note that in Example 13.5.6, \(\frac{C_{cn}}{C_{opt}} = \frac{29}{27}\approx 1.074\text{.}\) A 7 percent increase in cost may or may not be considered significant, depending on the situation.

A salesman must make stops at vertices A, B, and C, which are all on the same one-way street. The graph in Figure 13.5.9 is weighted by the function \(w(i, j)\) equal to the time it takes to drive from vertex \(i\) to vertex \(j\text{.}\)

Note that if \(j\) is down the one-way street from \(i\text{,}\) then \(w(i, j) < w(j, i)\text{.}\) The values of \(C_{opt}\text{,}\) and \(C_{cn}\) are 20 and 32, respectively. Verify that \(C_{cn}\) is 32 by using the closest neighbor algorithm. The value of \(\frac{C_{cn}}{C_{opt}} = 1.6\) is significant in this case since our salesman would spend 60 percent more time on the road if he used the closest neighbor algorithm.

A more general result relating to the closest neighbor algorithm presumes that the graph in question is complete and that the weight function satisfies the conditions

• \(w(x, y) = w(y, x)\) for all \(x\text{,}\) \(y\) in the vertex set, and

• \(w(x, y) + w(y, z) \geq w(x, z)\) for all \(x\text{,}\) \(y\text{,}\) \(z\) in the vertex set.

The first condition is called the symmetry condition and the second is the triangle inequality.

The type of problem that is outlined in the example above is of such importance that it is one of the most studied version of the Traveling Salesman Problem. What follows is the usual statement of the problem. Let \([0, 1] = \{x \in \mathbb{R} \mid \text{ }0 \leq x\leq 1\}\text{,}\) and let \(S = [0,1]^2\text{,}\) the unit square. Given \(n\) pairs of real numbers \(\left(x_1, y_1\right),\left(x_2,y_2\right), \dots , \left(x_n,y_n\right)\) in \(S\) that represent the \(n\) vertices of a \(K_n\text{,}\) find a circuit of the graph that minimizes the sum of the distances traveled in traversing the circuit.

Since the problem calls for a circuit, it doesn't matter which vertex we start at; assume that we will start at \(\left(x_1,y_1\right)\text{.}\) Once the problem is solved, we can always change our starting position. A function can most efficiently describe a circuit in this problem. Every bijection \(f: \{1, . . . , n\} \to \{1, . . . , n\}\) with \(f(1) = 1\) describes a circuit

There are \((n - 1)!\) such bijections. Since a circuit and its reversal have the same associated cost, there are \(\frac{(n - 1)!}{2}\) cases to consider. An examination of all possible cases is not feasible for large values of \(n\text{.}\)

One popular heuristic algorithm is the strip algorithm:

Step Item 3 may need a bit more explanation. How do you travel up or down a strip? In most cases, the vertices in a strip will be vertically distributed so that the order in which they are visited is obvious. In some cases, however, the order might not be clear, as in the third strip in Phase I of Figure 13.5.14. Within a strip, the order in which you visit the points (if you are going up the strip) is determined thusly: \(\left(x_i,y_i\right)\) precedes \(\left(x_j,y_j\right)\) if \(y_i <y_j\) or if \(y_i=y_j\) and \(x_i < x_j\) . In traveling down a strip, replace \(y_i < y_j\) with \(y_i >y_j\text{.}\)

The selection of \(\left\lceil \sqrt{n/2}\right\rceil\) strips was made in a 1959 paper by Beardwood, Halton, and Hammersley. It balances the problems that arise if the number of strips is too small or too large. If the square is divided into too few strips, some strips may be packed with vertices so that visiting them would require excessive horizontal motion. If too many strips are used, excessive vertical motion tends to be the result. An update on what is known about this algorithm is contained in [42].

Since the construction of a circuit in the square consists of sorting the given points, it should come as no surprise that the strip algorithm requires a time that is roughly a multiple of \(n \log n\) time units when \(n\) points are to be visited.

The worst case that has been encountered with this algorithm is one in which the circuit obtained has a total distance of approximately \(\sqrt{2n}\) (see Sopowit et al.).

Subsection 13.5.3 Networks and the Maximum Flow Problem

An example of a real situation that can be represented by a network is a city's water system. A reservoir would be the source, while a distribution point in the city to all of the users would be the sink. The system of pumps and pipes that carries the water from source to sink makes up the remaining network. We can assume that the water that passes through a pipe in one minute is controlled by a pump and the maximum rate is determined by the size of the pipe and the strength of the pump. This maximum rate of flow through a pipe is called its capacity and is the information that the weight function of a network contains.

Consider the system that is illustrated in Figure 13.5.17. The numbers that appear next to each pipe indicate the capacity of that pipe in thousands of gallons per minute. This map can be drawn in the form of a network, as in Figure 13.5.18.

Although the material passing through this network is water, networks can also represent the flow of other materials, such as automobiles, electricity, bits, telephone calls, or patients in a health system.

Since the Maximum Flow Problem consists of maximizing the amount of material that passes through a given network, it is equivalent to finding a flow with the largest possible value. Any such flow is called a maximal flow.

For the network in Figure 13.5.18, one flow is \(f_1\text{,}\) defined by \(f_1\left(e_1\right)=25\text{,}\) \(f_1\left(e_2\right)=20\text{,}\) \(f_1\left(e_3\right)=0\text{,}\) \(f_1\left(e_4\right)= 25\text{,}\) and \(f_1\left(e_5\right)=20\text{.}\) The value of \(f_1\text{,}\) \(V\left(f_1\right)\text{,}\) is 45. Since the total flow into the sink can be no larger than 50 (\(w \left(e_4\right) + w \left(e_5\right) = 30 + 20\)), we can tell that \(f_1\) is not very far from the solution. Can you improve on \(f_1\) at all? The sum of the capacities into the sink can't always be obtained by a flow. The same is true for the sum of the capacities out of the source. In this case, the sum of the capacities out of the source is 60, which obviously can't be reached in this network.

A solution of the Maximum Flow Problem for this network is the maximal flow \(f_2\text{,}\) where \(f_2\left(e_1\right)=25\text{,}\) \(f_2\left(e_2\right)=25\text{,}\) \(f_2\left(e_3\right)=5\text{,}\) \(f_2\left(e_4\right)= 30\text{,}\) and \(f_2\left(e_5\right)=20\text{,}\) with \(V\left(f_2\right) = 50\text{.}\) This solution is not unique. In fact, there is an infinite number of maximal flows for this problem.

There have been several algorithms developed to solve the Maximal Flow Problem. One of these is the Ford and Fulkerson Algorithm (FFA). The FFA consists of repeatedly finding paths in a network called flow augmenting paths until no improvement can be made in the flow that has been obtained.

Consider the network in Figure 13.5.28, where the current flow, \(f\text{,}\) is indicated by a labeling of the edges.

The path \(\left(Source, v_2 , v_1,v_3 , Sink\right)\) is a flow augmenting path that allows us to increase the flow by one unit. Note that \(\left(v_1,v_3\right)\) is used in the reverse direction, which is allowed because \(f\left(v_1,v_3\right)>0\text{.}\) The value of the new flow that we obtain is 8. This flow must be maximal since the capacities out of the source add up to 8. This maximal flow is defined by Figure 13.5.29.

Subsection 13.5.4 Other Graph Optimization Problems

1. The Minimum Spanning Tree Problem: Given a weighted graph, \((V, E, w)\text{,}\) find a subset \(E'\) of \(E\) with the properties that \((V, E')\) is connected and the sum of the weights of edges in \(E'\) is as small as possible. We will discuss this problem in Chapter 10.

2. The Minimum Matching Problem: Given an undirected weighted graph, \((K, E, w)\text{,}\) with an even number of vertices, pair up the vertices so that each pair is connected by an edge and the sum of these edges is as small as possible. A unit square version of this problem has been studied extensively. See [42] for details on what is known about this version of the problem.

3. The Graph Center Problem: Given a connected, undirected, weighted graph, find a vertex (called a center) in the graph with the property that the distance from the center to every other vertex is as small as possible. “As small as possible” is normally interpreted as minimizing the maximum distance from the center to a vertex.