Chapter 23. Graphs.

Combinatorial Optimization 1

§23.1 Graphs and Digraphs

Definition (Graph)
A graph G consists of two finite sets (sets having finitely many elements),
a set V of points, called vertices, and a set E of connecting lines, called
edges, such that each edge connects two vertices, called the endpoints of
the edge. We write
G = (V, E).
Excluded are isolated vertices (vertices that are not endpoints of any edge),
loops (edges whose endpoints coincide), and multiple edges (edges that have
both endpoints in common).
An edge (vi, vj ) is called incident with the vertex vi (and conversely);
similarly, is incident with vj .

The number of edges incident with a vertex v is called the degree of v.

Two vertices are called adjacent in G if they are connected by an edge in

G (that is, if they are the two endpoints of some edge in G).

Note: graphs in different fields under different names

1. ”networks” in electrical engineering
2. ”structures” in civil engineering
3. ”molecular structures” in chemistry
4. ”organizational structures” in economics
5. ”sociograms”, ”road maps”, ”telecommunication networks”, and so on.
Department of Mathematics V. Choi
 Chapter 23. Graphs. Combinatorial Optimization 2

Definition (Digraphs (Directed Graphs))

A digraph G = (V, E) is a graph in which each edge e = (i, j) has a
direction from its ”initial point” i to its ”terminal point” j.

Fig. 479. Digraph

Definition (Subgraph or Subdigraph)

A subgraph or subdigraph of a given graph or digraph G = (V, E) re-
spectively, is a graph or digraph obtained by deleting some of the edges and
vertices of G, retaining the other edges of G (together with their pairs of
endpoints).

Graph and subgraph

Digraph and subdigraph

Department of Mathematics V. Choi

 Chapter 23. Graphs. Combinatorial Optimization 3

• Computer Representation of Graphs and Digraphs

One should be aware that a graph may be sketched in various ways.

Definition (Adjacency Matrix of a Graph G)

Matrix A = [aij ] with entries
{
1 if G has an edge (i, j)
aij =
0 else
Note: 1. aij = 1 if and only if two vertices i and j are adjacent in G.
2. No vertex is considered to be adjacent to itself; thus, aii = 0.
3. Adjacency matrix A of a graph is symmetric aij = aji.
4. Incidence matrix B = [bij] of a graph is defined by
{
1 if vertex j is an endpoint of edge ej
bij = .
0 else
5. The adjacency matrix of a graph is generally much smaller than the inci-
dence matrix.

Example 1. (Adjacency Matrix of a Graph)

Department of Mathematics V. Choi

 Chapter 23. Graphs. Combinatorial Optimization 4

Definition (Adjacency Matrix of a Digraph G)

Matrix A = [aij ] with entries
{
1 if G has an directed edge (i, j)
aij =
0 else
Note: Adjacency matrix of a digraph G need not be symmetric.

Example 2. (Adjacency Matrix of a Digraph)

Definition (Lists)
The vertex incidence list of a graph shows, for each vertex, the incident
edges. The edge incidence list shows for each edge its two endpoints.
Similarly for a digraph; in the vertex list, outgoing edges then get a minus
sign, and in the edge list we now have ordered pairs of vertices.
Example 2. (Vertex Incidence List and Edge Incidence List)

Department of Mathematics V. Choi

 Chapter 23. Graphs. Combinatorial Optimization 5

Note: Sparse graphs are graphs with few edges (far fewer than the max-
imum possible number n(n − 1)/2 where n is the number of vertices).
1. For these graphs, matrices are not efficient.
2. Lists then have the advantage of requiring much less storage and being
easier to handle.

Department of Mathematics V. Choi

 Chapter 23. Graphs. Combinatorial Optimization 6

§23.2 Shortest Path Problems. Complexity

In a graph G = (V, E) we can walk from a vertex v1 along some edges to

some other vertex vk . Here we can
(A) make no restrictions, or
(B) require that each edge of G be traversed at most once, or
(C) require that each vertex be visited at most once.

In case (A) we call this a walk. Thus a walk from v1 to vk is of the form
(v1, v2), (v2, v3), · · · , (vk−1, vk ),
where some of these edges or vertices may be the same.

In case (B), where each edge may occur at most once, we call the walk a
trail.

In case (C), where each vertex may occur at most once (and thus each
edge automatically occurs at most once), we call the trail a path.

Note: 1. We admit that a walk, trail, or path may end at the vertex it
started from, in which case we call it closed.
2. A closed path is called a cycle (A cycle has at least three edges).

Department of Mathematics V. Choi

 Chapter 23. Graphs. Combinatorial Optimization 7

Definition (Shortest Path)

G = (V, E) is a weighted graph if each edge (vi, vj ) in G has a given
weight or length lij > 0.

A shortest path v1 → vk (with fixed v1 and vk ) is a path

(v1, v2), (v2, v3), · · · , (vk−1, vk ) such that the sum of the lengths of its
edges
l12 + l23 + · · · + lk−1,k
is minimum (as small as possible among all paths from v1 to vk ).

A longest path v1 → vk is one for which that sum is maximum.

Note: Shortest (and longest) path problems are among the most important
optimization problems.

[traveling salesman problem]

1. A salesman has to drive by car to his customers in n cities.
2. He can start at any city and after completion of the trip he has to return
to that city.
3. Furthermore, he can only visit each city once.
4. All the cities are linked by roads to each other, so any city can be visited
from any other city directly.
5. He has to find the optimal route (the shortest total mileage).

• The maximum number of possible optimal paths for n cities : (n − 1)!/2

Even for small number n = 15 the maximum number of possible paths is
very large(guess!).
∑
• A variation of the traveling salesman problem : maximize lij where lij
is his expected commission minus his travel expenses for going from town i
to town j.

Department of Mathematics V. Choi

 Chapter 23. Graphs. Combinatorial Optimization 8

• Breadth First Search(BFS)

• Depth First Search(DFS)

Moore’s BFS for Shortest Path (All Lengths One)

Department of Mathematics V. Choi

 Chapter 23. Graphs. Combinatorial Optimization 9

Example 1. (Application of Moore’s BFS Algorithm)

Find a shortest path s → t in the graph G.
Sol. The blue edges form a shortest path (length 4).

Note: Backtracking rule

1. There is another shortest path in Example 1.
2. Hence in the program we must introduce a rule that makes backtracking
unique because otherwise the computer would not know what to do next if
at some step there is a choice.
3. Using the numbering of the vertices from 1 to n (not the labeling!), at
each step, if a vertex labeled i is reached, take as the next vertex that with
the smallest number (not label!) among all the vertices labeled i − 1.

• Complexity of Moore’s algorithm : O(m)

To find the vertices to be labeled 1, we have to scan all edges incident with
s.
Next, when i = 1, we have to scan all edges incident with vertices labeled
1, etc. Hence each edge is scanned twice. These are 2m operations.

Department of Mathematics V. Choi

 Chapter 23. Graphs. Combinatorial Optimization 10

[Complexity of an Algorithm]
If a function g(m) is of the form
g(m) = kh(m) + more slowly growing terms (k ̸= 0)
we say that g(m) is of the order h(m) and write
g(m) = O(h(m)).
For instance,
am + b = O(m), am2 + bm + d = O(m2), 5 · 2m + 3m2 = O(2m).
The symbol O is quite practical and commonly used whenever the order of
growth is essential. If on a computer that does 109 operations per second, a
problem of size m = 50 will take 0.3 sec with an algorithm that requires m5
operations, but 13 days with an algorithm that requires 2m operations.

• Check terms for efficiency of an algorithm

(i) Time (number cA(m) of computer operations)
(ii) Space (stage needed in the internal memory)

• Two popular choice for complexity cA

(worse case) cA(m) = long time A takes for a problem of size m
(Average case) cA(m) = average time A takes for a problem of size m)
For Moore’s algorithm, cA(m) = 2m in both cases. Hence the complexity
of Moore’s algorithm is of order O(m).

Definition
An algorithm A is called efficient if cA = O(mk ) for some integer k ≥ 0;
that is cA may contain only powers of m, but no exponential functions.

An algorithm A is called polynomially bounded if A is efficient when we

choose the ”worst case” cA(m).

Department of Mathematics V. Choi

 Chapter 23. Graphs. Combinatorial Optimization 11

§23.3 Bellman’s Principle. Dijkstra’s Algorithm

Consider the problem of finding shortest paths from a given vertex, denoted
by 1 and called the origin, to all other vertices 2, 3, · · · , n of G.
For the length lij > 0, we assume that lij = ∞ for the edge (i, j) that does
not exist in G.
Let Lj denote the length of a shortest path Pj : 1 → j in G.

Theorem 1. (Bellman’s Minimality Principle or Optimality Princi-

ple)
If Pj : 1 → j is a shortest path from 1 to j in G and (i, j) is the last edge
of Pj , then Pi : 1 → i [obtained by dropping (i, j) form Pj ] is a shortest
path 1 → j.

Proof Suppose that the conclusion is false. Then there is a path Pi∗ : 1 → i
that is shorter than Pi. Hence, if we now add (i, j) to Pi∗, we get a path
1 → j that is shorter than Pj . This contradicts our assumption that Pj is
shortest.

Note: Bellman equations

1. For fixed j, ∃ various path 1 → j by adding shortest paths Pi to (i, j).
2. These paths obviously have lengths Li + lij .
3. We choose an i to minimize Li + lij , that is, we have Bellman equations
L1 = 0
Lj = mini̸=j (Li + lij ) (j = 2, 3, · · · , n).

Department of Mathematics V. Choi

 Chapter 23. Graphs. Combinatorial Optimization 12

Dijkstra’s Algorithm for Shortest Paths

Labeling procedure
(PL) a permanent label = length Lv of a shortest path 1 → v
(TL) a temporary label = upper bound L̃v for the length of a shortest path
1→v
In Step 2 the idea is to pick k ”minimally.”
In Step 3 the idea is that the upper bounds will in general improve (decrease)
and must be updated accordingly.

Department of Mathematics V. Choi

 Chapter 23. Graphs. Combinatorial Optimization 13

Example 1. (Application of Dijkstras Algorithm)

Applying Dijkstra’s algorithm to the graph, find shortest paths from vertex
1 to vertices 2, 3, 4.

Sol. We list the steps and computations.

1. L1 = 0, L̃2 = 8, L̃3 = 5, L̃4 = 7, PL = {1}, T L = {2, 3, 4}
2. L3 = min{L̃2, L̃3, L̃4} = 5, k = 3 PL = {1, 3}, T L = {2, 4}
3. L̃2 = min{8, L3 + l32} = min{8, 5 + 1} = 6
L̃4 = min{7, L3 + l34} = min{7, ∞} = 7
2. L2 = min{L̃2, L̃4} = min{6, 7} = 6, k = 2, PL = {1, 2, 3}, T L = {4}
3. L̃4 = min{7, L2 + l24} = min{7, 6 + 2} = 7
2. L4 = 7, k = 4 PL = {1, 2, 3, 4}, T L = ∅
The resulting shortest paths are of lengths L2 = 6, L3 = 5, L4 = 7.

Note: The complexity of Dijkstra’s algorithm is O(n2).

Step 2 requires comparison of elements, first n − 2, the next time n − 3,
etc., a total of (n − 2)(n − 1)/2.
Step 3 requires the same number of comparisons, a total of (n − 2)(n −
1)/2, as well as additions, first n − 2, the next time n − 3, etc., a total of
(n − 2)(n − 1)/2.
Hence the total number of operations is 3(n − 2)(n − 1)/2 = O(n2).

Department of Mathematics V. Choi

 Chapter 23. Graphs. Combinatorial Optimization 14

§23.4 Shortest Spanning Trees: Greedy Algorithm

• A tree T is a graph that is connected and has no cycles.
• A cycle is a path s → t of at least three edges that is closed(s = t).

Definition (Spanning Tree)

A spanning tree T in a given connected graph G = (V, E) is a tree
containing all the n vertices of G. Such a tree has n − 1 edges.

A shortest spanning tree T in a connected graph G = (V, E) (whose

∑
edges (i, j) have lengths lij > 0) is a spanning tree for which lij (sum
∑
over all edges of T ) is minimum compared to lij for any other spanning
tree in G.

Note: The set of shortest paths from vertex 1 to the vertices 2, 3, · · · , n in

the last section forms a spanning tree.
• Application of spanning tree
1. Railway lines connecting a number of cities : the ”length” of a line is the
construction cost and one wants to minimize the total construction cost.
2. Bus lines : ”length” may be the average annual operating cost.
3. Steamship lines (freight lines) : ”length” may be profit and the goal is
the maximization of total profit.
4. A network of telephone lines between some cities : a shortest spanning
tree may simply represent a selection of lines that connect all the cities at
minimal cost.
Department of Mathematics V. Choi
 Chapter 23. Graphs. Combinatorial Optimization 15

Kruskal’s Greedy Algorithm for Shortest Spanning Trees

Example 1. (Application of Kruskal’s Algorithm)

Using Kruskal’s algorithm, determine a shortest spanning tree in the following
graph

Sol. See Table 23.4. We stop after n − 1 choices since a spanning tree has
n − 1 edges.

Department of Mathematics V. Choi

 Chapter 23. Graphs. Combinatorial Optimization 16

[Efficiency increase of Kruskals method]

• Double Labeling of Vertices
Each vertex i carries a double label (ri, pi) where
ri = Root of the subtree to which i belongs,
pi = Predecessor of i in its subtree (pi = 0 for roots).

• Rejecting
If (i, j) is next in the list to be considered, reject (i, j) if ri = rj .
If ri ̸= rj include (i, j) in T .

• In Example 1, the double-label list is shown in Table 23.5, and the choice
process is illustrated in Fig. 491.

Note: Ordering is the more expensive part of the algorithm.

For a complete list of m edges, an algorithm would be O(m log2 m) but since
the n − 1 edges of the tree are most likely to be found earlier, by inspecting
the q topmost edges, for such a list of q edges one would have O(q log2 m).

Department of Mathematics V. Choi

 Chapter 23. Graphs. Combinatorial Optimization 17

§23.5 Shortest Spanning Trees: Prim’s Algorithm

Prim’s Algorithm for Shortest Spanning Trees

Note: 1. Denote by U the set of vertices of the growing tree T and by S

the set of its edges.
2. Initially U = {1} and S = ∅; at the end, U = V , the vertex set of the
given graph G = (V, E), whose edges (i, j) have length lij > 0.
3. In Step 1, the labels λ2, · · · , λn of vertices 2, · · · , n are the lengths of
the edges connecting them to vertex 1.
4. In Step 2, we choose the shortest λj as the edge of the growing tree T
and include j in U .
5. In Step 3, if ljk < λk , then update λk = ljk for k ∈ / U.
Department of Mathematics V. Choi
 Chapter 23. Graphs. Combinatorial Optimization 18

Example 1. (Application of Prim’s Algorithm)

Find a shortest spanning tree in the following graph

Sol. 1. U = {1}, S = ∅, λ2 = 2, λ3 = 4.
2. λ2 is smallest, U = {1, 2}, S = {(1, 2)}.
3. Update labels : λ3 = 4, λ4 = l24 = 11.
2. λ3 is smallest, U = {1, 2, 3}, S = {(1, 2), (1, 3)}.
3. Update labels : λ4 = l34 = 8, λ6 = l36 = 1.
2. λ6 is smallest, U = {1, 2, 3, 6}, S = {(1, 2), (1, 3), (3, 6)}.
3. Update labels : λ4 = 8, λ5 = l65 = 9.
2. λ4 is smallest, U = {1, 2, 3, 6, 4}, S = {(1, 2), (1, 3), (3, 6), (3, 4)}.
3. Update labels : λ5 = l45 = 6.
2. λ5 is smallest, U = {1, 2, 3, 6, 4, 5}, S = {(1, 2), (1, 3), (3, 6), (3, 4), (4, 5)}.
STOP

Department of Mathematics V. Choi

 Chapter 23. Graphs. Combinatorial Optimization 19

§23.6 Flows in Networks

Definition
A network is a digraph G = (V, E) in which each edge (i, j) has assigned
to it a capacity cij > 0, and at one vertex s, a flow is produced that flows
along the edges of the digraph G to another vertex t.

The capacity cij is the maximum possible flow along (i, j).
The vertex s is called the source, and t is called the target or sink where
the flow disappears.

Note: Denote the flow along a edge (i, j) by fij and impose two conditions:
1. For each edge (i, j) in G the flow does not exceed the capacity cij ,
0 ≤ fij ≤ cij (”Edge condition”).
2. For each vertex i, not s or t,
Inflow = Outflow (”Vertex condition”, ”Kirchhoffs law”);
in a formula


0 if vertex i ̸= s, i ̸= t,
∑ ∑
fki − fij = −f at the source s,

f
| k{z } j
| {z } at the target(sink) t,
Inflow Outflow

where f is the total flow.

Fig. 493. In flow and outflow for a vertex i (not s or t)

Department of Mathematics V. Choi

 Chapter 23. Graphs. Combinatorial Optimization 20

A path v1 → vk from a vertex v1 to a vertex vk in a digraph G means a

sequence of edges
(v1, v2), (v2, v3), · · · , (vk−1, vk ),
regardless of their directions in G, that forms a path as in a graph.

Hence when we travel along this path from v1 to vk we may traverse some
edge in its given direction, then we call it a forward edge of our path, or
opposite to its given direction, then we call it a backward edge of our path.

Definition (Flow Augmenting Path)

A flow augmenting path in a network with a given flow fij on each edge
(i, j) is a path P : s → t such that
(i) no forward edge is used to capacity; thus fij < cij for these;
(ii) no backward edge has flow 0; thus fij > 0 for these.

Department of Mathematics V. Choi

 Chapter 23. Graphs. Combinatorial Optimization 21

Example 1. (Flow Augmenting Paths)

Find flow augmenting paths in the following network, where the first number
is the capacity and the second number a given flow.

Sol. The existing flow f = 9 (outflow from s is 5 + 4 = 9, which equals the

inflow 6 + 3 = 9 into t).
We use the notation
∆ij = cij − fij for forward edges
∆ij = fij for backward edges
∆ = min ∆ij taken over all edges of a path.
For a flow augmenting path P1 : 1 − 2 − 3 − 6,

∆12 = 20 − 5 = 15, ∆23 = 11 − 8 = 3, ∆36 = 13 − 6 = 7

hence ∆ = 3. We can use P1 to increase the given flow 9 to f = 9 + 3 = 12.

We augment the flow by 3. Then the flow in each of the edges of P1 is

increased by 3, so that we now have f12 = 8(instead of 5), f23 = 11(instead
of 8), and f36 = 9(instead of 6). Edge (2, 3) is now used to capacity.

Department of Mathematics V. Choi

 Chapter 23. Graphs. Combinatorial Optimization 22

For another flow augmenting path P2 : 1 − 4 − 5 − 3 − 6,

∆14 = 10 − 4 = 6, ∆45 = 7 − 4 = 3, ∆53 = 2, ∆36 = 13 − 9 = 4
hence ∆ = 2. We can use P2 to increase the given flow to f = 12 + 2 = 14.

Then the flow in each of the edges of P2 is increased by 2, so that we now

have f14 = 6(instead of 4), f45 = 6(instead of 4), f53 = 0(instead of 2), and
f36 = 11(instead of 9).

No further augmentation is possible. We shall confirm later that f = 14 is

maximum.

Department of Mathematics V. Choi

 Chapter 23. Graphs. Combinatorial Optimization 23

Definition (Cut set, Capacity, Net flow)

Let G = (V, E) be a network.
If we may cut the network somewhere between s and t, then the cut parti-
tions the vertex set V into two parts S and T , where S is the set of vertices
on one side of the cut on which s lies and T is the set of the other vertices.
The (S, T ) is called cut set.

The capacity cap(S, T ) of a cut set (S, T ) is the sum of the capacities of
all forward edges in (S, T ) (forward edges only!), that is, the edges that are
directed from S to T ,
∑
cap(S, T ) = cij [sum over the forward edges of (S, T )] .
The net flow means the sum of the flows in the forward edges minus the
sum of the flows in the backward edges of the cut set.

cut set : S = {s, 2, 4}, T = {3, 5, t}

forward edges for the cut : (2, 3), (4, 5),
backward edges for the cut : (5, 2)
cap(S, T ) = 11 + 7 = 18
net flow : 11 + 6 − 3 = 14

Note: In the path 1 − 4 − 5 − 2 − 3 − 6, (5, 2) is a forward edge.

Department of Mathematics V. Choi

 Chapter 23. Graphs. Combinatorial Optimization 24

Theorem 1. (Net Flow in Cut Sets)

Any given flow in a network G is the net flow through any cut set (S, T )
of G.
Proof By Kirchhoff’s law, multiplied by −1 at a vertex i we have
∑ ∑ {
0 i ̸= s, i ̸= t,
fij − fli =
f at the source s.
j
| {z } | {z }
l
Outflow Inflow
Assuming fij = 0 for j = i and also for edges without flow or nonexisting
edges, we can sum over j and l from 1 to n(number of vertices)
∑ {
0 i ̸= s, i ̸= t,
(fij − fji) =
f i = s.
j

We now sum over all i in S. Since s is in S, this sum equals f :

∑∑
(fij − fji) = f.
i∈S j∈V

In this sum, edges with both ends in T cannot contribute, since we sum only
over i in S; but edges (i, j) with both ends in S contribute +fij at one end
and −fij at the other, a total contribution of 0. This infers to prove the
theorem.

Theorem 2. (Upper Bound for Flows)

A flow f in a network G cannot exceed the capacity of any cut set (S, T )
in G.
Proof By Theorem 1, net flow f = f1 − f2 through the cut set, where f1
is the sum of the flows through the forward edges and f2 is the sum of the
flows through the backward edges of the cut set. Thus f ≤ f1 ≤ cap(S, T ).

Department of Mathematics V. Choi

 Chapter 23. Graphs. Combinatorial Optimization 25

Theorem 3. (Augmenting Path Theorem for Flows)

A flow from s to t in a network G is maximum if and only if there does not
exist a flow augmenting path s → t in G.
Proof (⇒) If there is a flow augmenting path P : s → t, we can use it to
push through it an additional flow. Hence the given flow cannot be maxi-
mum.
(⇐) Suppose that there is no flow augmenting path s → t in G. Let S0 be
the set of all vertices i (including s) such that there is a flow augmenting
path and let T0 be the set of the other vertices in G.
Consider any edge (i, j) with i ∈ S0 and j ∈ T0. Then we have a flow
augmenting path s → i but s → i → j is not flow augmenting. Hence we
must have
{ {
cij forward
fij = if (i, j) is a edge of s → i → j.
0 backward
Otherwise we could use (i, j) to get a flow augmenting path s → i → j.
From the cut set (S0, T0), forward edges are used to capacity and backward
edges carry no flow. The net flow through the cut set (S0, T0) is equal to
cap(S0, T0), and thus f = cap(S0, T0) by Theorem 1.
Note that f ≤ cap(S0, T0) by Theorem 2.
Hence f must be maximum since we have reached equality.

Theorem 4. (Max-Flow Min-Cut Theorem)

The maximum flow in any network G equals the capacity of a ”minimum
cut set” (= a cut set of minimum capacity) in G.
Proof Note that a maximum flow f = cap(S0, T0) for a suitable cut set
(S0, T0). By Theorem 2, f ≤ cap(S, T ) for any cut set (S, T ) in G. Hence
we have cap(S0, T0) ≤ cap(S, T ), which means that (S0, T0) is a minimum
cut set.

Department of Mathematics V. Choi

 Chapter 23. Graphs. Combinatorial Optimization 26

§23.7 Maximum Flow: Ford-Fulkerson Algorithm

Ford-Fulkerson Algorithm for Maximum Flow

Department of Mathematics V. Choi

 Chapter 23. Graphs. Combinatorial Optimization 27

Example 1. (Ford-Fulkerson Algorithm)

Applying the Ford-Fulkerson algorithm, determine the maximum flow for
the following network.

Sol. Apply the Ford-Fulkerson algorithm as follows.

1. An initial flow f = 9.
2. Label s(= 1) by ∅. Mark 2, 3, 4, 5, 6 ”unlabeled”.
3. Scan 1.
∆12 = 20 − 5 = 15, ∆2 = ∆12 = 15. Label 2 by (1+, 15)
∆14 = 10 − 4 = 6, ∆4 = ∆14 = 6. Label 4 by (1+, 6)
4. Scan 2
∆23 = 11 − 8 = 3, ∆3 = min(∆2, ∆23) = 3. Label 3 by (2+, 3)
∆5 = min(∆2, f52) = 3. Label 5 by (2−, 3)
Scan 3
∆36 = 13 − 6 = 7, ∆6 = min(∆3, ∆36) = 3. Label 6 by (3+, 3)
Stop scan because t is reached.
5. P : 1 − 2 − 3 − 6 is a flow augmenting path with ∆t = ∆6 = 3.
6. Using ∆t = 3, augmentation gives f12 = 5 + 3 = 8, f23 = 8 + 3 = 11,
f36 = 6 + 3 = 9, other fij unchanged. Augmented flow f = f + 3 = 12.

7. Remove labels on vertices 2, 3, 4, 5, 6. Go to Step 3.

3. Scan 1
∆12 = 20 − 8 = 12, ∆2 = ∆12 = 12. Label 2 by (1+, 12)

Department of Mathematics V. Choi

 Chapter 23. Graphs. Combinatorial Optimization 28

∆14 = 10 − 4 = 6, ∆4 = ∆14 = 6. Label 4 by (1+, 6)

4. Scan 2 ∆5 = min(∆2, f52) = 3. Label 5 by (2−, 3)
Scan 4 : No vertex left for labeling.
Scan 5
∆3 = min(∆5, f35) = 2. Label 3 by (5−, 2)
Scan 3
∆36 = 13 − 9 = 4, ∆6 = min(∆3, ∆36) = 2. Label 6 by (3+, 2)
Stop scan because t is reached.
5. P : 1 − 2 − 5 − 3 − 6 is a flow augmenting path with ∆t = ∆6 = 2.
6. Using ∆t = 2, augmentation gives f12 = 8 + 3 = 10, f52 = 3 − 2 = 1,
f35 = 2 − 2 = 0, f36 = 9 + 2 = 11,other fij unchanged. Augmented flow
f = f + 2 = 14.

7. Remove labels on vertices 2, 3, 4, 5, 6. Go to Step 3.

3. Scan 1
∆12 = 20 − 10 = 10, ∆2 = ∆12 = 10. Label 2 by (1+, 10)
∆14 = 10 − 4 = 6, ∆4 = ∆14 = 6. Label 4 by (1+, 6)
4. Scan 2 ∆5 = min(∆2, f52) = 1. Label 5 by (2−, 1)
Scan 4 : No vertex left for labeling.
Scan 5 : No vertex left for labeling.
Stop algorithm because one can no longer reach t. Hence the above flow is
maximum.
Note: Compare with Example 1 in Sec. 23.6.

Department of Mathematics V. Choi