6CCS3OME/7CCSMOME – Optimisation Methods
Lecture 4
Network flow problems Ford-Fulkerson method
Tomasz Radzik and Kathleen Steinho ̈fel
Department of Informatics, King’s College London 2020/21, Second term
Maximum network-flow problem
85 27 27
t
1
49s12141 36
• A Flow Network: G = (V, E, c, s, t), where
• V – set of n nodes, E – set of m directed edges (links)
• For each (u,v) ∈ E, c(u,v) ≥ 0 is the capacity of edge (u,v).
if (u, v) ̸∈ E, then (for convenience) define c(u, v) = 0; • two distinguished nodes: source s and sink t. (s ̸= t)
• Find (design) a maximum flow from the source to the sink:
• a flow of the maximum total amount, while the flow on each edge is not greater than the capacity of this edge;
• a continuous flow of the maximum total rate, while the rate of flow on each edge is not greater than the capacity of this edge.
6CCS3OME/7CCSMOME, Lecture 4: Network flow problems; Ford-Fulkerson method 2 / 40
2
Flow in network: example
52 85
t
1
27272 441
9s121 36
1
the rate (value) of this flow = 5 + 2 + 1 + 1 = 9
85 22571
7252 7
4241 9s1213
311
36
33
2
6CCS3OME/7CCSMOME, Lecture 4: Network flow problems; Ford-Fulkerson method
3 / 40
the maximum flow rate (value) = 5+5+1 = 11
t
1
2
1
Application: Problem of Representatives
• Applications in transportation and communication networks.
• Applications discussed in the Ahuja-Magnanti-Orlin textbook:
parallel machine scheduling, assignment of computer modules to computer processors, rounding of census data, tanker scheduling,
the problem of representatives.
• The problem of representatives:
A town has r residents, q clubs, p political parties; r ≫ q ≫ p.
Each resident may be a member of a number of clubs, but belongs to exactly one political party.
Select the governing council of exactly q members, which satisfies the following balancing “properties”:
1. Each club is represented in the council by (exactly) one of its members. One council member can represent only one club.
2. For each political party Pk, the number of council members belonging to this party is at most uk. (The numbers uk are given.)
Is it possible to select a council which satisfies this properties?
6CCS3OME/7CCSMOME, Lecture 4: Network flow problems; Ford-Fulkerson method 4 / 40
Problem of Representatives reduced to the Maximum-flow Problem
clubs
residents parties
integral flow from s to t
(positive flow on the red (bold) edges)
C
P
2 u 1 = 1
C
2
R 3
1 1
C 1 R 1 2 3
C3 C4
1 C3 1
11 5
2
R 1
R 1 1 1
P u = 1 C 111 111
R
1 R
11 1
R 4
R 1
R 5
R 1 R6
1 1
u u3 3 = = 2 2
R6 R
1
2
7
R 7
P2 u2 = 2
s
1
1 4
u 2 = 2 P2 t
P3
u3 = 2
C4 1
P3
• An integral flow in the constructed flow network corresponds to a feasible “partial” council (some clubs might not have their representatives).
• It is possible to select a full balanced council (Properties 1 & 2), if, and only
if, the maximum flow value is equal to q (the number of clubs).
6CCS3OME/7CCSMOME, Lecture 4: Network flow problems; Ford-Fulkerson method 5 / 40
Other flow problems
• Flow-Feasibility problem (Transshipment problem): multiple sources and sinks with specified supplies and demands.
Find a feasible flow, that is, a flow which satisfies the edge capacities and the specified supply/demand values at the nodes.
(6)
(4)
(1) (8)
(2) (3)
(3) (2)
(3)
+8 (5)
−6
(3)
(2)
(4)
(4)
(4)
This problem is “equivalent” to the maximum flow problem. • Minimum-cost flow problems.
Multicommodity flow problems. These problems are more difficult
than the maximum flow problem. 6CCS3OME/7CCSMOME, Lecture 4: Network flow problems; Ford-Fulkerson method
6 / 40
(1)
+5
−4 (1)
−3
Flows – formal definition
• We assume, for convenience, that if (u,v) ∈ E, then (v,u) ̸∈ E.
uv
If there are “antiparallel” edges (u, v) and (v, u)
in a given application, we can convert the network into an equivalent one with no antiparallel edges.
uv
• Aflowisafunctionf:E→R, wheref(u,v)≥0istheflow on edge (u, v), that has the following properties:
• Capacity constraints:
For each edge (u,v) ∈ E, 0 ≤ f(u,v) ≤ c(u,v).
0 <= f(u,v) <= c(u,v) . uv
• Flow conservation: For each node v ∈ V − {s, t},
the total flow into v is equal to
the total flow out of v. 2 In other words: the net flow into v is equal to 0.
3
v
8
4
6CCS3OME/7CCSMOME, Lecture 4: Network flow problems; Ford-Fulkerson method
7 / 40
new vertex
1
Flow conservation
Foreachnodev∈V −{s,t}:
• Theflowintovisequal a
v d
flow in = flow out:
to the flow out of v:
b
c
.
f(x,v) = f(v,z). (x,v)∈E (v,z)∈E
• The net flow into v is equal to 0:
a
vd
net flow into v:
f(x,v)− f(v,z)=0. (x,v)∈E (v,z)∈E
6CCS3OME/7CCSMOME, Lecture 4: Network flow problems; Ford-Fulkerson method
8 / 40
b
c
.
e
a+b+c = d+e
e
a+b+c−d−e = 0
The maximum flow problem (formally)
• The value of a flow f is the net flow from the source, which is equal to the net flow into the sink, due to the flow conservation condition:
|f| =
def
s f(s,v) − f(u,s)
=
f(x,t) − f(t,z) (x,t)∈E (t,z)∈E
(s,v)∈E (u,s)∈E
• Maximum flow problem: For a given flow network, find a flow of the maximum possible value (maximizes the net flow from the source).
Such a flow is called a maximum flow. (Not necessarily unique.)
• For a given flow f, if f(v,u) = c(v,u), then we say that flow f saturates edge (v, u), and edge (v, u) is a saturated edge.
6CCS3OME/7CCSMOME, Lecture 4: Network flow problems; Ford-Fulkerson method
9 / 40
t
From flows to paths
• G = (V,E,c,s,t): a flow network; f: a flow in G.
• Flow f can be “decomposed” into at most m paths from s to t and cycles,
where m is the number of edges in G.
• Example (no flow cycles here). Decompose the following flow
into paths (the numbers on the
edges are the edge flows): s
a
b 35
• Algorithm: keep selecting and
removing (from the current flow)
“maximal” s–t path flows.
Each path removes all remaining
flow from at least one edge, so at most m paths.
4
• This algorithm can be extended to the case when there are flow cycles.
• One flow path (or cycle) can be found in O(n) time, and there are at most m paths/cycles selected, so the total running time is O(nm).
This is less than the time needed to find a maximum flow.
6CCS3OME/7CCSMOME, Lecture 4: Network flow problems; Ford-Fulkerson method
10 / 40
11
4
3
7
3
c
d
5 2 9
5
t
The Flow-Feasibility problem (formally)
(6)
(4)
(1) (8)
(2) (3)
(3) (2)
(3)
+8 (5)
−6
(3)
(2)
(4)
(4)
(4)
(1)
Assume: v∈V d(v) = 0, that is, total supply = total demand.
• Find a feasible flow f, that is, a flow within the edge capacities and
such that for each node v ∈ V , the net flow from v equals d(v):
f(v,x)− f(z,v) = d(v). (v,x)∈E (z,v)∈E
+5
−4 (1)
−3
• Input: G = (V, E, c, d), where V and E are the sets of nodes and edges; for each (v,u) ∈ E, c(v,u) ≥ 0 is the capacity of edge (v,u);
for each v ∈ V , d(v) indicates the supply/demand at node v.
d(v) > 0: supply of d(v) units at v; d(v) < 0: demand of |d(v)| units at v; d(v)=0: a“transitional”node(flowonlypassesthrough).
• The above condition is the flow conservation property for this problem. 6CCS3OME/7CCSMOME, Lecture 4: Network flow problems; Ford-Fulkerson method 11 / 40
Reduction from flow-feasibility to maximum-flow
s
(2)
(3)
(3)
(5)
(3)
(8)
(1) (8)
(2)
(6)
+8 (5)
(2)
−6
(1)
(6)
(3)
+5 (2)
−4 (1)
(4)
(4)
(4)
(4)
−3
• For a given input G = (V, E, c, d) of the flow feasibility problem, construct the following input G′ = (V ′, E′, c′, s, t) for the maximum flow problem:
• V′ =V ∪{s,t},wheresandtaretwonewnodes;
• E′ =E∪{(s,v):v∈V, d(v)>0}∪{(u,t):u∈V, d(u)<0};
• c′(v, u) = c(v, u); c′(s, v) = d(v); c′(u, t) = −d(u).
6CCS3OME/7CCSMOME, Lecture 4: Network flow problems; Ford-Fulkerson method
12 / 40
(3)
t
Reduction from flow-feasibility to maximum-flow (cont.)
• Compute a maximum flow f′ in G′. (5)
3 (3)
+5 −4
5
1 (3)
s (2) 2
(2)
81 1(2)4
(8)
(3) 3(4)
(4) 6(6)
(6) 4
(2) 2 (8) −3
+8 (5)
−6
4 (4)
3 (4)
• A maximum flow in G′ saturates all edges outgoing from s, if and only if, there is a feasible flow in G.
• If a maximum flow f′ in G′ saturates all edges outgoing from s, then remove the added nodes and edges to get a feasible flow in G.
• If f is a feasible flow in G, then saturate all edges outgoing from s and all edges incoming to t to get a maximum flow in G′.
6CCS3OME/7CCSMOME, Lecture 4: Network flow problems; Ford-Fulkerson method
13 / 40
3(3) (1) 1(1)
(1)
1t
3
(3)
Residual capacities
• Let f be a flow in a flow network G = (V,E,c,s,t).
• The residual capacity of an edge (u, v) ∈ E is defined as:
cf (u, v) = c(u, v) − f (u, v). 3 (4)
(1)
x (y)
flow capacity
u
v
u
v
capacity = 4; 3 units of flow
residual capacity = 1
• If for an edge (u,v) ∈ E, f(u,v) > 0, then the residual capacity of a reverse edge (v, u) is defined as: cf (v, u) = f (u, v).
u
v
u
v
3 (4)
(1)
0 < f(u,v) < c(u,v)
positive residual capacities in both directions
• The positive residual capacity of the reverse edge (v, u) represents possibility of decreasing the current positive flow f (u, v).
6CCS3OME/7CCSMOME, Lecture 4: Network flow problems; Ford-Fulkerson method
14 / 40
(3)
Residual networks
• If cf(u,v) > 0, then (u,v) is a residual edge.
• Let Ef denote the set of all residual edges.
m = |E| ≤ |Ef | ≤ 2|E| = 2m
• The residual network of G induced by flow f is the flow network
Gf = (V,Ef,cf,s,t),
where cf are the residual capacities and Ef is the set of residual edges.
6CCS3OME/7CCSMOME, Lecture 4: Network flow problems; Ford-Fulkerson method
15 / 40
Increase the flow using the residual network: example
input
1 (1)
(1)
(3)
network G
and flow f (3) of value 7
2 (5) 4 (4)
residual
(3) network Gf
flow f’
(2) (3)
of value 1
1 (3)
(2) s
1 (3)
in residual
(2) s
4 (4)
3 (3)
and flow h = f f’
(1)
a 1 (3) b a (2) b
(2) s
(2) s
1 (1)
a (2) b
a (3) b
(1)
1 (3)
1 (1)
3 (5)
input network G
(4) fctct
network G
1 (3)
1 (3)
of value 7+1 = 8.
6CCS3OME/7CCSMOME, Lecture 4: Network flow problems; Ford-Fulkerson method
16 / 40
3 (3)
(3)
(2)
(4) ctct
(3)
(3)
.
Augmenting the current flow by a flow in the residual network
• Iff isaflowinGandf′ isaflowintheresidualnetworkGf,thenwecan augment f by f′ to get a new greater flow h in G.
• Thenewflowh=f ↑f′ inGisdefinedinthefollowingway: h(u,v)= f(u,v)+f′(u,v)−f′(v,u) if(u,v)∈E,
u
u
v
3 (7)
2 (4)
v u 0 (3) v
5 (7)
in the input network in the residual network
combined (in the input network)
u
u
v
3 (7)
0 (4)
v u 2 (3) v
1 (7)
0 otherwise.
in the input network in the residual network
• This definition of f ↑ f′ works also if both f′(u,v) and f′(v,u) are positive.
• |f ↑f′|=|f|+|f′|, thatisthevalueofflowf ↑f′ (thenetflowfromthe source) is equal to the sum of the values of flows f and f′.
6CCS3OME/7CCSMOME, Lecture 4: Network flow problems; Ford-Fulkerson method 17 / 40
combined (in the input network)
A general approach to finding a maximum flow
• Start with the zero flow and keep iteratively increasing the flow by flows in the residual network:
f← zeroflow {f(u,v)=0,foreach(u,v)∈E} loop
(1) Construct the residual network Gf
(2) Find a nonzero flow f′ in Gf ,
If there is no such a flow, then exit
(3) f ← f ↑ f′ { augmentation: augment flow f with flow f′ }
end of loop
• Most of the max-flow algorithms which follow this general approach compute in each iteration a path flow f′, that is, a flow along one residual path from s to t.
6CCS3OME/7CCSMOME, Lecture 4: Network flow problems; Ford-Fulkerson method 18 / 40
Augmenting paths and path flows
G = (V,E,c,s,t) – a flow network; f – flow in G.
• Residual path: a simple path in the residual network Gf .
Augmenting path: a residual path from s to t.
• The residual capacity of an augmenting path p is the maximum amount of
flow that can be sent along path p:
cf(p) = min{cf(u,v) | (u,v) is an edge on p}.
s (5) (7) (3) (4) (3) (7) t
bottleneck capacity
• Let p be an augmenting path in Gf . The (path) flow fp in Gf is: fp(u,v) = cf(p), if (u,v) is on p,
• Thevalueofflowfp is |fp|=cf(p)>0. 6CCS3OME/7CCSMOME, Lecture 4: Network flow problems; Ford-Fulkerson method
19 / 40
0. otherwise.
Ford-Fulkerson method
FORD-FULKERSON(G) { G=(V,E,c,s,t) }
f← zeroflow {f(u,v)=0 foreach (u,v)∈E} loop (1) Construct the residual network Gf
(*)
(3) f ← f ↑ fp { path augmentation } end of loop
(2) Find an augmenting path p in Gf ,
If there is no augmenting path in Gf , then exit
Below, the highlighted edges have positive flow, the other edges – zero flow.
current f
y> q z = q t sqqqqqqt
fp new f
+q t
20 / 40
s
s +q
6CCS3OME/7CCSMOME, Lecture 4: Network flow problems; Ford-Fulkerson method
x >q
x−q
y−q
0
+q
Ford-Fulkerson method (cont.)
FORD-FULKERSON(G) { G=(V,E,c,s,t) }
f← zeroflow {f(u,v)=0 foreach (u,v)∈E}
• •
Does this algorithm compute a maximum flow in G?
loop (1)
t
end of loop
Construct the residual network Gf (2) Find an augmenting path p in Gf ,
If there is no augmenting path in Gf , then exit (3) f ← f ↑ fp { path augmentation }
(100)
(100) (1)
What is the running time?
• The running time of one iteration is O(m): construct Gf : Θ(m), or O(n), if incrementally; search Gf to find an augmenting path: O(m); updatetheflow: O(n).
(n – number of nodes; m – number of edges)
s
• The number of iterations depends on the selection strategy in step (2).
6CCS3OME/7CCSMOME, Lecture 4: Network flow problems; Ford-Fulkerson method
21 / 40
(100)
(100)
Cuts
• Acut(S,T)inanetworkG: S⊆V, T =V −S, s∈S, t∈T.
That is, a cut is a partitioning of the set of nodes V into two disjoint sets S andT suchthatthesourcenodesisinsetS andthesinknodetisinsetT.
• The capacity of a cut (S,T) is the sum of the capacities of the edges from S to T :
T
c(S,T) = c(u,v). (u,v)∈E: u∈S,v∈T
S s
t
• Iff isaflow,then
the net flow across the cut (S, T ) is:
f(S,T) = f(u,v) − (u,v)∈E: u∈S,v∈T
f(x,y). (x,y)∈E: x∈T,y∈S
• For each cut (S,T), f(S,T) = |f|,
that is, the net flow across the cut is equal to the net flow into the sink t. This follows from the flow conservation constraints.
6CCS3OME/7CCSMOME, Lecture 4: Network flow problems; Ford-Fulkerson method 22 / 40
Cuts: example
(4)
1 (1)
2 (2)
(1)
S
(8) (2)
t 5 (5)
1 (1)
1(9) s 1(3)
1(1)
For this cut (S,T) and this flow f:
• c(S,T) = 4+7+7+1+6 = 25.
• f(S,T) = 7+3+1−2 = 9 = |f|.
6CCS3OME/7CCSMOME, Lecture 4: Network flow problems; Ford-Fulkerson method
23 / 40
7(7) 2(2) 3(7)
1 (4)
(6)
(2)
Cuts (cont.)
• For any flow f and any cut (S,T): |f| = f(S,T) ≤ c(S,T).
(The net flow across a cut cannot be greater than the capacity of this cut.)
• Therefore, the value of a maximum flow is not greater than the minimum capacity of a cut.
max{|f| : f isaflowinG} ≤ min{c(S,T): (S,T) isacutinG}.
(4) 1(9) s 1(3)
2 (2)
1(1)
(8) 5 (5)
(2) 2(2) 3(7)
1 (1)
7(7) 1 (1)
1 (4)
(1)
• Thiscut(S,T)isaminimumcapacitycut, c(S,T)=5+2+2+1=10,so the maximum value of flow for this network is not greater than 10.
6CCS3OME/7CCSMOME, Lecture 4: Network flow problems; Ford-Fulkerson method 24 / 40
(6)
T
t
(2)
The Max-flow Min-cut theorem
• Theorem 1. (Max-flow Min-cut theorem)
The maximum value of a flow equals to the minimum capacity of a cut:
max{|f| : f isaflowinG} = min{c(S,T) : (S,T) isacutinG}.
• Theorem 2.
For a flow f in G, the following three conditions are equivalent. (a) f is a maximum flow in G.
(b) There is no augmenting path in the residual network Gf . (c) For some cut (S,T) in G, |f| = c(S,T).
• Theorem 2 can be proven by showing implications: (a) ⇒ (b) ⇒ (c) ⇒ (a).
• Theorem 1 follows from Theorem 2:
(a) ⇒ (c), so for a maximum flow f, there is a cut (S,T) such that
|f| = f(S,T) = c(S,T) ≥ min{c(S′,T′) : (S′,T′) is a cut in G}.
• Correctness of the FORD-FULKERSON method: When this method terminates, then for the computed flow f, there is no augmenting path in the residual network Gf , so f is a maximum flow (by Theorem 2, (b) ⇒ (a)).
6CCS3OME/7CCSMOME, Lecture 4: Network flow problems; Ford-Fulkerson method 25 / 40
Max-flow Min-cut (cont.)
• Theorem 2.
For a flow f in G, the following three conditions are equivalent. (a) f is a maximum flow in G.
(b) There is no augmenting path in the residual network Gf . (c) For some cut (S,T) in G, |f| = c(S,T).
• (a) ⇒ (b). Assume f is a maximum flow in G.
If there is an augmenting path, then the flow cannot be maximum because
we can use such a path to increase the value of flow.
T
• (b) ⇒ (c). Assume no augmenting path in Gf . Let S be the set of nodes reachable from s
S s
t
in the residual network Gf . t is not in S. AlledgesfromStoT =V −Sare
saturated. All edges from T to S have zero flow.
Therefore, |f| = f(S,T) = c(S,T).
• (c)⇒(a). Let(S,T)beacutasin(c).
|f| = f(S,T) = c(S,T), but there is no flow of value greater than c(S,T), so
f is a maximum flow.
6CCS3OME/7CCSMOME, Lecture 4: Network flow problems; Ford-Fulkerson method 26 / 40
Number of iterations in Ford-Fulkerson
• Depends on the strategy of selecting an augmenting path p in each iteration.
• If FORD-FULKERSON is run on a network such that all edge capacities are integral:
• The residual capacities are integral throughout the computation, so the value of the current total flow in G increases in each iteration by some integer, that is, by at least 1.
• Thus, if f∗ denotes a maximum flow, then the number of iterations is at most |f∗|.
• Hence the total running time is O(|f∗|m).
• Note that this bound does not depend on the selection strategy used.
• There is no general bound on the number of iterations which would depend only on the size of the network (on numbers n and m).
6CCS3OME/7CCSMOME, Lecture 4: Network flow problems; Ford-Fulkerson method 27 / 40
The Edmonds-Karp algorithm
The Edmonds-Karp algorithm is the Ford-Fulkerson method with the following strategy for selecting augmenting paths:
In each iteration select a shortest augmenting path (that is, a path with the fewest number of edges).
EDMONDS-KARP(G)
f ← zeroflowinG (f(u,v)=0,foreach(u,v)∈E) loop
1) Construct residual network Gf
2) BFS in Gf from s to find a shortest augmenting path p
3) If there is no augmenting path in Gf , then exit
(the current flow is optimal)
4) Let p be the selected augmenting path
f ← f ↑ fp (augment the current flow with flow fp) end of loop
6CCS3OME/7CCSMOME, Lecture 4: Network flow problems; Ford-Fulkerson method
28 / 40
The running time of Edmonds-Karp
• Each iteration takes O(m) time and there are O(nm) iterations, so the total running time is O(nm2).
• This O(nm2) bound does not depend on the values of the edge capacities, and does not depend on the maximum value of a flow.
• The bound O(nm) on the number of iterations follows from the following claim.
Claim: Let q denote the number of iterations in EDMONDS-KARP, and let k1, k2, k3, . . . , kq denote the lengths of the augmenting paths selected in iterations 1,2,3,…,q. We have:
(a) 1≤k1 ≤k2 ≤k3 ≤…kq ≤n−1,
(b) the same length appears in the sequence < k1,k2,...,kq > at most m times.
• This claim immediately implies that the number of iterations q ≤ nm.
• We omit the proof of this claim.
6CCS3OME/7CCSMOME, Lecture 4: Network flow problems; Ford-Fulkerson method 29 / 40
Other maximum-flow algorithms
• “Augmenting paths” algorithms:
• Modified Edmonds-Karp algorithm – O(n2m)
(by achieving the average time of O(n) per one iteration)
• Dinic’s algorithm – O(n3)
• fastest known “blocking flow” algorithm – O(nm log n)
• “Preflow-push” algorithms (not part of this module, but see textbook CLRS, if interested):
• the generic preflow-push algorithm – O(n2m)
• the lift-to-front algorithm – O(n3)
• if special data structure used – O(nm log n)
6CCS3OME/7CCSMOME, Lecture 4: Network flow problems; Ford-Fulkerson method 30 / 40
Resource assignment & Maximum bipartite matching
• Consider the following problem (an example of “resource assignment” problems):
• We have a number of employees E1,E2,…,Ep and a number of tasks T1,T2,…,Tq which should be done.
• Each employee Ei can do some of the tasks, depending on the employee’s skills and the skills required by individual tasks.
• We want to allocate tasks to employees in such a way that:
• each employee gets at most one task;
• each task is given to at most one employee;
• each employee can get only a task which this employee can do;
• the largest possible number of tasks are allocated.
• This problem can be modeled as
the maximum bipartite matching problem.
6CCS3OME/7CCSMOME, Lecture 4: Network flow problems; Ford-Fulkerson method
31 / 40
Maximum bipartite matching (cont.)
• Construct a bipartite graph with nodes E1, E2, . . . , Ep on one side and nodes T1,T2,…,Tq on the other side.
An edge (T i, Ej) means that task T i can be done by employee Ej.
T1 T2 T3 Ti
T1 T2 T3 Ti
E1 E2
E3
Ej
E1 E2
E3
Ej
• A matching in a bipartite graph is a subset of edges M such that each node belongs to at most one edge in M.
• In our application, a matching is a feasible allocation (each employee gets at most one task, each task is given to at most one employee, and each employee can get only a task which this employee can do).
• Thus maximising the number of allocated tasks is equivalent to finding in the corresponding bipartite graph a matching of the maximum size.
6CCS3OME/7CCSMOME, Lecture 4: Network flow problems; Ford-Fulkerson method 32 / 40
Solving the maximum bipartite matching as the maximum flow problem
• For a given bipartite graph B, construct the following flow network G, where all edge capacities are equal to 1:
bipartite graph B
• There is a one-to-one correspondence between
flow network G
matchings in B and integral flows in G:
an edge (v, u) in a given matching
corresponds to a path flow of value 1
from s to t which passes over edge (v, u). 6CCS3OME/7CCSMOME, Lecture 4: Network flow problems; Ford-Fulkerson method
33 / 40
s
t
Solving the maximum bipartite matching as the maximum flow (cont.)
• For a matching M in B and the corresponding integral flow f in G, the size of the matching M is equal to the value of the flow f.
• Thus finding a maximum-size matching in B is equivalent to finding a maximum integral flow in G.
• Use the Ford-Fulkerson method to find a maximum flow in G. Since the edge capacities in G are integral, the computed maximum flow is integral. The calculated maximum flow gives a maximum-size matching in B.
• The running time is O(mn), where n and m are the number of nodes and
the number of edges in B: at most n iterations (since the value of a
maximum flow in G is at most n), and each iteration takes O(m) time. 6CCS3OME/7CCSMOME, Lecture 4: Network flow problems; Ford-Fulkerson method 34 / 40
s
t
Examples and Exercises – LGT
1. Assume that the flow in the right diagram on slide 5 is the flow at the end of some iteration of the execution of the Ford-Fulkerson method. Continue this method to obtain a maximum flow.
6CCS3OME/7CCSMOME, Lecture 4: Network flow problems; Ford-Fulkerson method 35 / 40
Examples and Exercises – LGT (cont.)
2. Trace the computation of the Edmonds-Karp maximum-flow algorithm on the input given below.
For each iteration, show the residual network at the beginning of the iteration, the selected augmenting path, and the total flow at the end of the iteration
Iteration 1
s
bd (1)
t
(7) ap
(8)
(3) (4) (5)
(2)
(5)
(2)
(3) h
c
(3)
The residual network is the same as the input network. Show on the diagram above the selected augmenting path (which gives the total flow at the end of this iteration).
6CCS3OME/7CCSMOME, Lecture 4: Network flow problems; Ford-Fulkerson method 36 / 40
(1)
(3)
Exercises (cont.)
Iteration 2
ap
Show all residual edges and their residual capacities. Show the selected augmenting path.
s
b
d
t
Show the total flow at the end (7) ap
of this iteration.
Continue, until the computation terminates. 6CCS3OME/7CCSMOME, Lecture 4: Network flow problems; Ford-Fulkerson method
37 / 40
s
bd (1)
t
c
h
(8)
(3) (4) (5)
(2)
(5)
(2)
(3) h
c
(3)
(1)
(3)
Exercises (cont.)
3. Decompose the computed maximum flow into paths.
4. Show a minimum cut in this network. Is the minimum cut unique?
5. If we want to modify the network so that the maximum flow increases by 1 unit, how many edge capacities do we have to increase?
6CCS3OME/7CCSMOME, Lecture 4: Network flow problems; Ford-Fulkerson method 38 / 40
Exercises – SGT
1. Trace the computation of the Ford-Fulkerson maximum-flow method on the input given below (the same flow network as in the LGT). In each iteration select the augmenting path which has maximum capacity.
For each iteration, show the residual network at the beginning of the iteration, the selected augmenting path, and the total flow at the end of the iteration
s
t
6CCS3OME/7CCSMOME, Lecture 4: Network flow problems; Ford-Fulkerson method
39 / 40
(8)
(3) b
(3)
(7) ap
(2)
(5)
(4) d (5)
(2)
(3)
c
(3)
(1)
(1) h
Exercises – SGT (cont.)
2. The following diagram shows who (employees E1, E2, . . . , E6) can execute which tasks (T1,T2,…,T6).
(E1, E5, E6).
Show the computed allocation of tasks.
6CCS3OME/7CCSMOME, Lecture 4: Network flow problems; Ford-Fulkerson method
40 / 40
T1 T2 T3 T4 T5
T6
E1
E2 E3 E4 E5 E6
Trace the execution of the Edmonds-Karp algorithm when applied to calculate a maximum allocation of tasks to employees in this example. Whenever you need to break a tie between vertices, assume that the vertex corresponding to T (or E) with the lower index comes first. For example, the order of the adjacency list of the vertex T4 will be