CS202: Discrete Structures

Definition 9.5.1 Weighted Graph. A weighted graph, (V, E, w), is a graph (V, E) together with a weight function w : E →ℝ. If e ∈ E, w(e) is the weight on edge e.

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

Example 9.5.2 A Distance Graph. Let V be the set of six capital cities in New England: Boston, Augusta, Hartford, Providence, Concord, and Montpelier. Let E be {{a, b} ∈ V × V| a ≠ b}; that is, (V, E) is a complete unordered graph. An example of a weight function on this graph is w(c₁, c₂) = the distance, in miles, from c₁ to c₂.

Many road maps define distance functions as in the following table.

Table 9.5.3 Distances between capital cities in New England

--	Augusta	Boston	Concord	Hartford	Montpelier	Providence
Augusta, ME	--	165	148	266	190	208
Boston, MA	165	--	75	103	192	43
Concord, NH	148	75	--	142	117	109
Hartford, CT	266	103	142	--	204	70
Montpelier, VT	190	192	117	204	--	223
Providence, RI	208	43	109	70	223	--

9.5.2 The Traveling Salesman Problem

The Traveling Salesman Problem is, given a weighted graph, to find a circuit (e₁, e₂, . . . , e_n) that visits every vertex at least once and minimizes the sum of the weights, $\sum _{i=1}^{n}$w (e_i). 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, then an optimal path would be any Hamiltonian circuit.

Example 9.5.4 The problem of a Boston salesman. The Traveling Salesman Problem gets its name from the situation of a salesman who wants to minimize the number of miles that he travels in visiting his customers. For example, if a salesman from Boston must visit the other capital cities of New England, then the problem is to find a circuit in the weighted graph of Example 9.5.2. Note that distance and cost are clearly related in this case. In addition, tolls and traffic congestion might also be taken into account.

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 n2ⁿ. 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. 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.

Algorithm 9.5.5 The Closest Neighbor Algorithm. Let G = (V, E, w) be a complete weighted graph with |V| = n. The closest neighbor circuit through G starting at v₁ is (v₁, v₂, . . . , v_n), defined by the steps:

(1) V₁ = V − { v₁}.

(2) For k = 2 to n − 1

(3) v_n = the only element of V_n

The cost of the closest neighbor circuit is $\sum_{k=1}^{n-1}$w(v_k, v_{k + 1}) + w(v_n, v₁)

Example 9.5.6 A small example. The closest neighbor circuit starting at A in Figure 9.5.7 is (1, 3, 2, 4, 1), with a cost of 29. The optimal path is (1, 2, 3, 4, 1), with a cost of 27.

Figure 9.5.7 A small example

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 ≤ C_cn or $\frac{C_{cn}}{C_{opt}} \geq 1$. 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 9.5.6, $\frac{C_{cn}}{C_{opt}}$ = $\frac{29}{27} \approx 1.074$. A 7 percent increase in cost may or may not be considered significant, depending on the situation.

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

Figure 9.5.9 Traveling a one-way street

Note that if j is down the one-way street from i, then w(i, j) < w(j, i). The values of C_opt, 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, y in the vertex set, and
• w(x, y) + w(y, z) ≥ w(x, z) for all x, y, z in the vertex set.

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

Theorem 9.5.10 If (V, E, w) is a complete weighted graph that satisfies the symmetry and triangle inequality conditions, then

$\frac{C_{cn}}{C_{opt}} \leq \frac{\left \lceil \mathrm{log_{2}}(2n) \right \rceil}{2}$

Observation 9.5.11 If |V| = 8, then this theorem says that C_cn can be no larger than twice the size of C_opt; however, it doesn't say that the closest neighbor circuit will necessarily be that far from an optimal circuit. The quantity $\frac{\left \lceil \mathrm{log_{2}}(2n) \right \rceil}{2}$ is called an upper bound for the ratio $\frac{C_{cn}}{C_{opt}}$. It tells us only that thing can't be any worse than the upper bound. Certainly, there are many graphs with eight vertices such that the optimal and closest neighbor circuits are the same. What is left unstated in this theorem is whether there are graphs for which the quantities are equal. If there are such graphs, we say that the upper bound is sharp.

The value of $\frac{C_{cn}}{C_{opt}}$in Example Example 9.5.8 is 1.6, which is greater than $\frac{\left \lceil \mathrm{log_{2}}(2 \cdot 4) \right \rceil}{2} = 1.5$; however, the weight function in this example does not satisfy the conditions of the theorem.

Example 9.5.12 The Unit Square Problem. Suppose a robot is programmed to weld joints on square metal plates. Each plate must be welded at prescribed points on the square. To minimize the time it takes to complete the job, the total distance that a robot's arm moves should be minimized. Let d(P, Q) be the distance between P and Q. Assume that before each plate can be welded, the arm must be positioned at a certain point P₀. Given a list of n points, we want to put them in order so that

d(P₀, P₁) + d(P₁, P₂) + · · · + d(P_n − 1, P_n) + d(P_n, P₀)

is as small as possible.

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 ∈ ℝ | 0 ≤ x ≤ 1}, and let S = [0, 1]², the unit square. Given n pairs of real numbers (x₁, y₁), (x₂, y₂) , . . . , (x_n, y_n) in S that represent the n vertices of a K_n, 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 (x₁, y₁). 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} → {1, ..., n} with f (1) = 1 describes a circuit

(x₁, y₁), (x_f(2), y_f(2)) , . . . , (x_f(n), yf(n) )

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.

One popular heuristic algorithm is the strip algorithm:

Heuristic 9.5.13 The Strip Algorithm. Given n points in the unit square:

Phase 1:

• Divide the square into $\left \lceil \sqrt{n/2} \right \rceil$ vertical strips, as in Figure 9.5.14. Let d be the width of each strip. If a point lies on a boundary between two strips, consider it part of the left-hand strip.
• Starting from the left, find the first strip that contains one of the points. Locate the starting point by selecting the first point that is encountered in that strip as you travel from bottom to top. We will assume that the first point is (x₁, y₁)
• Alternate traveling up and down the strips that contain vertices until all of the vertices have been reached.
• Return to the starting point.

Phase 2:

• Shift all strips d/2 units to the right (creating a small strip on the left).
• Repeat Steps 1.2 through 1.4 of Phase 1 with the new strips.

When the two phases are complete, choose the shorter of the two circuits obtained.

Figure 9.5.14 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 9.5.14. Within a strip, the order in which you visit the points (if you are going up the strip) is determined thusly: (x_i, y_i) precedes (x_j, y_j) 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.

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 [39].

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.).

9.5.3 Networks and the Maximum Flow Problem

Definition 9.5.15 Network. A network is a simple weighted directed graph that contains two distinguished vertices called the source and the sink with the properties that the indegree of the source and outdegree of the sink are both zero, and source is connected to sink. The weight function on a network is the capacity function, which has positive weights.

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.

Example 9.5.16 A City Water System. Consider the system that is illustrated in Figure 9.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 9.5.18.

 

Figure 9.5.17 City Water System

 

Figure 9.5.18 Flow Diagram for a City's Water Network

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.

Problem 9.5.19 The Maximum Flow Problem. The Maximum Flow Problem is derived from the objective of moving the maximum amount of water or other material from the source to the sink. To measure this amount, we define a flow as a function f : E → ℝ such that (1) the flow of material through any edge is nonnegative and no larger than its capacity: 0 ≤ f(e) ≤ w(e), for all e ∈ E; and (2) for each vertex other than the source and sink, the total amount of material that is directed into a vertex is equal to the total amount that is directed out:

$\begin{align*} \sum_{(x,v) \in E} f(x,v) &= \sum_{(v,y) \in E} f(v,y) \\ \mathrm{Flow \; into \;}v &= \mathrm{Flow \; out \; of \;}v \end{align*}$     (9.5.1)

The summation on the left of (9.5.1) represents the sum of the flows through each edge in E that has v as a terminal vertex. The right-hand side indicates that you should add all of the flows through edges that initiate at v.

Theorem 9.5.20 Flow out of Source equals Flow in Sink. If f is a flow, then $\sum_{(source,v) \in E} f(source,v) = \sum_{(v,sink) \in E} f(v,sink)$

Proof. Subtract the right-hand side of (9.5.1) from the left-hand side. The result is:

Flow into v − Flow out of v = 0

Now sum up these differences for each vertex in V ′ = V − {source, sink}. The result is

$\sum_{v \in V'} \left( \sum_{(x,v) \in E} f(x,v) - \sum_{(v,y) \in E} f(v,y) \right ) = 0$       (9.5.2)

Now observe that if an edge connects two vertices in V ′, its flow appears as both a positive and a negative term in (9.5.2). This means that the only positive terms that are not cancelled out are the flows into the sink. In addition, the only negative terms that remain are the flows out of the source. Therefore,

$\sum_{(v,sink) \in E} f(v,sink) - \sum_{(source,v) \in E} f(source,v) = 0$

Definition 9.5.21 The Value of a Flow. The two values flow into the sink and flow out of the source were proved to be equal in Theorem 9.5.20 and this common value is called the value of the flow . It is denoted by V(f ). The value of a flow represents the amount of material that passes through the network with that flow.

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 9.5.18, one flow is f₁, defined by f₁(e₁) = 25, f₁(e₂) = 20, f₁(e₃) = 0, f₁(e₄) = 25, and f₁(e₅) = 20. The value of f₁, V (f₁), is 45. Since the total flow into the sink can be no larger than 50 (w(e₄) + w(e₅) = 30 + 20), we can tell that f₁ is not very far from the solution. Can you improve on f₁ 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₂, where f₂(e₁) = 25, f₂(e₂) = 25, f₂(e₃) = 5, f₂(e₄) = 30, and f₂(e₅) = 20, with V(f₂) = 50. 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.

Definition 9.5.22 Flow Augmenting Path. Given a flow f in a network (V, E), a flow augmenting path with respect to f is a simple path from the source to the sink using edges both in their forward and their reverse directions such that for each edge e in the path, w(e) − f(e) > 0 if e is used in its forward direction and f (e) > 0 if e is used in the reverse direction.

Example 9.5.23 Augmenting City Water Flow. For f₁ in Figure 9.5.18, a flow augmenting path would be (e₂, e₃, e₄) since w(e₂) −f₁(e₂) = 15, w(e₃) − f₁(e₃) = 5, and w(e₄) − f₁(e₄) = 5.

These positive differences represent unused capacities, and the smallest value represents the amount of flow that can be added to each edge in the path. Note that by adding 5 to each edge in our path, we obtain f₂, which is maximal. If an edge with a positive flow is used in its reverse direction, it is contributing a movement of material that is counterproductive to the objective of maximizing flow. This is why the algorithm directs us to decrease the flow through that edge.

Algorithm 9.5.24 The Ford and Fulkerson Algorithm.

(1) Define the flow function f₀ by f₀(e) = 0 for each edge e ∈ E.

(2) i = 0.

(3) Repeat:

(4) Terminate with a maximal flow f_i

List 9.5.25 Notes on the Ford and Fulkerson Algorithm

1. It should be clear that every flow augmenting path leads to a flow of increased value and that none of the capacities of the network can be violated.
2. The depth-first search should be used to find flow augmenting paths since it is far more efficient than the breadth-first search in this situation. The depth-first search differs from the breadth-first algorithm in that you sequentially visit vertices until you reach a "dead end" and then backtrack.
3. There have been networks discovered for which the FFA does not terminate in a finite number of steps. These examples all have irrational capacities. It has been proven that if all capacities are positive integers, the FFA terminates in a finite number of steps. See Ford and Fulkerson, Even, or Berge for details.
4. When you use the FFA to solve the Maximum Flow Problem by hand it is convenient to label each edge of the network with the fraction $\frac{f_{i}(e)}{w(e)}$.

Algorithm 9.5.26 Depth-First Search for a Flow Augmenting Path. This is a depth-first search for the Sink Initiating at the Source. Let E′ be the set of directed edges that can be used in producing a flow augmenting path. Add to the network a vertex cal led start and the edge (start, source).

(1) S =vertex set of the network.

(2) p =source Move p along the edge (start, source)

(3) while p is not equal to start or sink:

(4) if p = start:

then no flow augmenting path exists.

else p = sink and you have found a flow augmenting path.

Example 9.5.27 A flow augmenting path going against the flow. Consider the network in Figure 9.5.28, where the current flow, f , is indicated by a labeling of the edges.

Figure 9.5.28 Current Flow

The path (Source, v₂, v₁, v₃, Sink) is a flow augmenting path that allows us to increase the flow by one unit. Note that (v₁, v₃) is used in the reverse direction, which is allowed because f (v₁, v₃) > 0. 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 9.5.29.