Skip to main content
\(\newcommand{\identity}{\mathrm{id}} \newcommand{\notdivide}{{\not{\mid}}} \newcommand{\notsubset}{\not\subset} \newcommand{\lcm}{\operatorname{lcm}} \newcommand{\gf}{\operatorname{GF}} \newcommand{\inn}{\operatorname{Inn}} \newcommand{\aut}{\operatorname{Aut}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\cis}{\operatorname{cis}} \newcommand{\chr}{\operatorname{char}} \newcommand{\Null}{\operatorname{Null}} \renewcommand{\vec}[1]{\mathbf{#1}} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \)

Section9.5Graph Optimization

The common thread that connects all of the problems in this section is the desire to optimize (maximize or minimize) a quantity that is associated with a graph. We will concentrate most of our attention on two of these problems, the Traveling Salesman Problem and the Maximum Flow Problem. At the close of this section, we will discuss some other common optimization problems.

Subsection9.5.1Weighted Graphs

Definition9.5.1Weighted Graph

A weighted graph, \((V, E, w)\), is a graph \((V, E)\) together with a weight function \(w: E \to \mathbb{R}\). If \(e \in 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.

Example9.5.2A 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\} \in V \times V \mid a\neq b\}\); that is, \((V,E)\) is a complete unordered graph. An example of a weight function on this graph is \(w\left(c_1, c _2\right) = \textrm{the distance, in miles, from } c_1 \textrm{ to } c_2\).

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

-- 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 --
Table9.5.3Distances between capital cities in New England

Subsection9.5.2The 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)\). 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.

Example9.5.4The 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 \(n 2^n\). 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.

Example9.5.6A 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.

A small weighted graph
Figure9.5.7A 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}\leq 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.

Example9.5.8The 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\text{.}\)

A small directed weighted graph
Figure9.5.9Traveling a one-way street

Note that if \(j\) is down the one-way street from \(i\text{,}\) 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, v) = w(y, x)\) for all \(x\), \(y\) in the vertex set, and

  • \(w(x, y) + w(y, z) \geq 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.

Observation9.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 \log _2 (2n)\right\rceil }{2}\) is called an upper bound for the ratio \(\frac{C_{cn}}{C_{opt}}\). It tells us only that things 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 9.5.8 is 1.6, which is greater than \(\frac{\lceil \log _2 (2\cdot 4)\rceil}{2} = 1.5\); however, the weight function in this example does not satisfy the conditions of the theorem.

Example9.5.12The 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\text{.}\) Assume that before each plate can be welded, the arm must be positioned at a certain point \(P_0\) . Given a list of \(n\) points, we want to put them in order so that \[d\left(P _0,P_1\right) + d\left(P_1,P _2 \right) +\cdots +d\left(P_{n-1},P_n\right)+ d\left(P_n ,P _0 \right)\] 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 \in \mathbb{R} \mid \text{ }0 \leq x\leq 1\}\), and let \(S = [0,1]^2\), 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\), 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)\). 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 \[\left(x_1, y_1\right),\left(x_{f(2)},y_{f(2)}\right),\ldots ,\left(x_{f(n)},y_{f(n)}\right)\] 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:

The Strip Algorithm
Figure9.5.14The Strip Algorithm

Step 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: \(\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\).

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

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

Subsection9.5.3Networks and the Maximum Flow Problem

Definition9.5.15Network

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.

Example9.5.16A 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.

City Water System
Figure9.5.17City Water System
City Water Network
Figure9.5.18Flow 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.

Problem9.5.19The 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 \to \mathbb{R}\) such that (1) the flow of material through any edge is nonnegative and no larger than its capacity: \(0 \leq f(e) \leq w(e)\), for all \(e\in 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} \begin{array}{ccc} \sum_{(x,v)\in E} f(x,v) & = & \sum_{(v,y)\in E} f(v,y) \\ \textrm{Flow into } v & = & \textrm{ Flow out of } v \\ \end{array}\label{flow-rules}\tag{9.5.1} \end{align} 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\text{.}\)

Proof
Definition9.5.21The 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_1\), defined by \(f_1\left(e_1\right)=25\), \(f_1\left(e_2\right)=20\), \(f_1\left(e_3\right)=0\), \(f_1\left(e_4\right)= 25\), and \(f_1\left(e_5\right)=20\). The value of \(f_1\), \(V\left(f_1\right)\), 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\), where \(f_2\left(e_1\right)=25\), \(f_2\left(e_2\right)=25\), \(f_2\left(e_3\right)=5\), \(f_2\left(e_4\right)= 30\), and \(f_2\left(e_5\right)=20\), with \(V\left(f_2\right) = 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.

Definition9.5.22Flow 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.

Example9.5.23Augmenting City Water Flow

For \(f_1\) in Figure 9.5.18, a flow augmenting path would be\(\left(e_2 , e_3 , e_4 \right)\) since \(w\left(e_2\right)-f_1\left(e_2\right)= 15\), \(w\left(e_3\right)-f_1\left(e_3\right)=5\), and \(w\left(e_4\right)-f_1\left(e_4\right)=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_2\), 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.

List9.5.25Notes 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)}\).

Example9.5.27A flow augmenting path going against the flow

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

Current Flow
Figure9.5.28Current Flow

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

Updated Flow
Figure9.5.29Updated Flow

Subsection9.5.4Other Graph Optimization Problems

  1. The Minimum Spanning Tree Problem: Given a weighted graph, \((V, E, w)\), find a subset \(\text{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)\), 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 [41] 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 (the 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” could be interpreted either as minimizing the sum of the distances to each vertex or as minimizing the maximum distance from the center to a vertex.

Subsection9.5.5Exercises for Section 9.5

1

Find the closest neighbor circuit through the six capitals of New England starting at Boston. If you start at a different city, will you get a different circuit?

Answer
2

Is Theorem 9.5.1 sharp for \(n = 3\)? For \(n = 4\)?

3

Given the following sets of points in the unit square, find the shortest circuit that visits all the points and find the circuit that is obtained with the strip algorithm.

  1. \(\{(0.1k, 0.1k) : k = 0, 1, 2, . . . , 10\}\)

  2. \(\{(0.1, 0.3), (0.3, 0.8), (0.5, 0.3), (0.7, 0.9), (0.9, 0.1)\}\)

  3. \(\{(0.0, 0.5), (0.5, 0.0), (0.5, 1.0), (1.0, 0.5)\}\)

  4. \(\{(0, 0), (0.2, 0.6), (0.4, 0.1), (0.6, 0.8), (0.7, 0.5)\}\)

Answer
4

For \(n = 4, 5, \text{and } 6\), locate \(n\) points in the unit square for which the strip algorithm works poorly.

5

Consider the network whose maximum capacities are shown on the following graph.

Figure for Exercise 9-5-5

  1. A function \(f\) is partially defined on the edges of this network by: \(f(\text{Source}, c) =2\), \(f(\text{Source}, b) =2\), \(f(\text{Source}, a) = 2\), and \(f(a, d) = 1\). Define \(f\) on the rest of the other edges so that \(f\) is a flow. What is the value of \(f\) ?

  2. Find a flow augmenting path with respect to \(f\) for this network. What is the value of the augmented flow?

  3. Is the augmented flow a maximum flow? Explain.

Answer
6

Given the following network with capacity function \(c\) and flow function \(f\text{,}\) find a maximal flow function. The labels on thevedges of the network are of the form \(f(e)/c(e)\), where \(c(e)\) is the capacity of edge \(e\) and \(f(e)\) is the used capacity for flow \(f\text{.}\)

Figure for Exercise 9-5-6
7

Find maximal flows for the following networks.

Figure for Exercise 9-5-7a
Figure for Exercise 9-5-7b
Figure for Exercise 9-5-7c
Answer
8

  1. Find two maximal flows for the network in Figure 9.5.28 other than the one found in the text.

  2. Describe the set of all maximal flows for the same network.

  3. Prove that if a network has two maximal flows, then it has an infinite number of maximal flows.

9

Discuss reasons that the closest neighbor algorithm is not used in the unit square version of the Traveling Salesman Problem.

Hint Answer
10

Explore the possibility of solving the Traveling Salesman Problem in the “unit box”: \([0,1]^3\).

11

Devise a “closest neighbor” algorithm for matching points in the unit square.