INN701 Lecture 3
Queensland University of Technology
CRICOS No. 00213J
CAB301 Algorithms and Complexity
Lecture 10 – Graph Algorithms -III
Maolin Tang
School of Computer Science
Queensland University of Technology
CRICOS No. 00213J
a university for the worldreal R 2
Aims of this lecture
• In this lecture we study two algorithms that solve graph-based
problems using iterative improvement
– Maximum flow algorithm
– Maximum matching algorithm
CRICOS No. 00213J
a university for the worldreal R 3
References
• A. Levitin. Introduction to the Design and Analysis of Algorithms.
Addison-Wesley, third edition, 2012. Sections 10.2 and 10.3.
• K. A. Berman and J. L. Paul. Algorithms: Sequential, Parallel and
Distributed. Thomson, 2005. Sections 14.1 and 14.2.
CRICOS No. 00213J
a university for the worldreal R
Iterative improvement
• A strategy for designing algorithms for solving optimisation problems
• Starts with a feasible solution (a solution that satisfies all the
constraints of the problem)
• Proceeds to improve the feasible solution by repeated applications
of some simple step, which typically involves a small, localised
change yielding a feasible solution with an improved value of the
objective function
• Returns the last feasible solution as optimal and stops when the
value of the objective function cannot be further improved
• Hill-climbing is a great example of the iterative improvement strategy
4
CRICOS No. 00213J
a university for the worldreal R
MAXIMUM FLOW ALGORITHM
5
CRICOS No. 00213J
a university for the worldreal R
The maximum-flow problem
• To maximum the flow of a material from a source vertex to a sink
vertex through a flow network
6
CRICOS No. 00213J
a university for the worldreal R
The maximum-flow problem
• Applications
– To maximum the flow of traffic through a transportation network
– To maximum the flow of communication through a commination
system
– To maximum the flow of electricity through an electrical
distribution system
7
CRICOS No. 00213J
a university for the worldreal R
The maximum-flow problem
• The flow network is modelled as a directed graph of n vertices
• Two distinguished vertices
– The source (vertex 1)
– The sink (vertex n)
• Each edge (i,j) has a capacity ui,j
• The flow on the edge (i,j) is denoted by xi,j
• Flow conservation requirement – for any intermediate vertex, the
total amount of material entering the vertex must be equal to the
total amount of material leaving the vertex
8
[ ] ∑∑
∈∈
=−∈∀
Ekik
ki
Eijj
ij xxni
),(:
,
),(:
,,1,2
CRICOS No. 00213J
a university for the worldreal R
The maximum-flow problem
• The maximum flow problem can be formulated as the following
optimisation problem:
9
CRICOS No. 00213J
a university for the worldreal R
Ford-Fulkerson method
• A method that computes the maximal flow in a flow network.
• It was proposed by L. R. Ford Jr. and D. R. Fulkerson in 1956.
• It is a method, rather than an algorithm, as it involves a procedure
for finding so-called augmenting paths, but the procedure is not fully
specified in the method.
• There are many different implementations. Edmonds-Karp algorithm
is a specialisation of the Ford-Fulkerson method.
10
CRICOS No. 00213J
a university for the worldreal R
Ford-Fulkerson method
• It starts with the zero flow, which is a feasible solution
• At each iteration, it searches for a so-called augmenting path from
the source vertex to the sink vertex along which it can send a
positive flow from the source vertex to the sink vertex in the residual
graph of the flow graph, and updates the flows assigned to each of
the edges on the argument path according to the capacity of the
augmenting path.
• After each iteration, a better solution is found
• The algorithm terminates when such an augmenting path cannot be
found
11
CRICOS No. 00213J
a university for the worldreal R
Residual graph
• A residual graph is a graph which contains all the vertices and all
the edges in the network graph. The wight of each edge is the
residual capacity of the edge.
12
CRICOS No. 00213J
a university for the worldreal R
Augmenting path
13
1 2
4
5
3 60/2 0/5 0/2
1 2
4
5
3 62 5 2
1 2
4
5
3 62 5 2
Network graph
Residual graph
Augmenting path
CRICOS No. 00213J
a university for the worldreal R
The capacity of an augmenting path
• The capacity C(p) of a path p is given by
where uij is the capacity of the link (i,j)
14
CRICOS No. 00213J
a university for the worldreal R
Updating network graph
15
CRICOS No. 00213J
a university for the worldreal R
Updating residual graph
16
CRICOS No. 00213J
a university for the worldreal R 17
1 2
4
5
3 632 2 2
1 2
4
5
3 632 2 2
Residual graph
Augmenting path
1 2
4
5
3 642 2
1 2
4
5
3 61/52/2 2/2
Residual graph
Network graph
1
CRICOS No. 00213J
a university for the worldreal R
Efficiency degradation of the augmenting path
method
18
CRICOS No. 00213J
a university for the worldreal R
The shortest augmenting path algorithm
• An implementation of the Ford-Fulkerson method for computing the
maximum flow in a flow network.
• It was proposed by Jack Edmonds and Richard Karp in 1972.
• Shortest augmenting path – the path with the fewest number of
edges.
19
CRICOS No. 00213J
a university for the worldreal R 20
CRICOS No. 00213J
a university for the worldreal R 21
CRICOS No. 00213J
a university for the worldreal R
The shortest augmenting path algorithm
22
CRICOS No. 00213J
a university for the worldreal R
The shortest augmenting path algorithm
• The flow increases at least by one unit after each update with an
augmenting path.
• The maximum flow is bounded from above.
• Therefore the algorithm terminates.
• The efficiency of the algorithm is O(nm2), n is the number of the
vertices in the directed graph and m is the number of edges in the
directed graph.
23
CRICOS No. 00213J
a university for the worldreal R
MAXIMUM MATCHING ALGORITHM
24
CRICOS No. 00213J
a university for the worldreal R
Maximum matching in a graph
• A matching in a graph is a subset of the edges such that no edges
in the subset share a vertex.
• A maximum matching is a matching with the maximum number of
edges.
• A perfect matching matches all the vertices of the graph.
• We limit our discussion to bipartite graphs.
25
CRICOS No. 00213J
a university for the worldreal R
Bipartite graph
• A graph is bipartite if all the vertices in the graph can be partitioned
into two disjoint sets V and U, not necessarily of the same size, so
that every edge connects a vertex in one of these sets to a vertex in
the other set.
26
CRICOS No. 00213J
a university for the worldreal R
Maximum bipartite matching algorithm
• An iterative improvement algorithm that is used to find the maximum
matching in a bipartite graph.
• Let M be a matching in a bipartite graph G = ⟨V , U, E⟩. How can we
improve it, i.e., find a new matching with more edges?
• Obviously, if every vertex in either V or U is matched (has a mate),
i.e., serves as an endpoint of an edge in M, this cannot be done and
M is a maximum matching.
• To have a chance at improving the current matching, both V and U
must contain unmatched vertices (free vertices), i.e., vertices that
are not incident to any edge in M.
27
CRICOS No. 00213J
a university for the worldreal R
Maximum bipartite matching algorithm
• It attempts to increase the size of a current matching M by
constructing a simple path from a free vertex in V to a free vertex in
U whose edges are alternately in E−M and in M.
– The first edge of the path does not belong to M, the second one
does, and so on, until the last edge that does not belong to M.
• Such a path is called augmenting with respect to the matching M.
• The length of an augmenting path is always odd.
28
CRICOS No. 00213J
a university for the worldreal R
Augmenting path
29
CRICOS No. 00213J
a university for the worldreal R
Maximum bipartite matching algorithm
• THEOREM A matching M is a maximum matching if and only if
there exists no augmenting path with respect to M.
30
CRICOS No. 00213J
a university for the worldreal R 31
CRICOS No. 00213J
a university for the worldreal R 32
CRICOS No. 00213J
a university for the worldreal R
Maximum bipartite matching algorithm
33
CRICOS No. 00213J
a university for the worldreal R
Maximum bipartite matching algorithm
34
CRICOS No. 00213J
a university for the worldreal R
Maximum bipartite matching algorithm
• The time efficiency of the algorithm is in O(n(n + m)), where n is the
total number of vertices and m is the number of edges.
35
CAB301 Algorithms and Complexity��Lecture 10 – Graph Algorithms -III
Aims of this lecture
References
Iterative improvement
Maximum flow algorithm
The maximum-flow problem
The maximum-flow problem
The maximum-flow problem
The maximum-flow problem
Ford-Fulkerson method
Ford-Fulkerson method
Residual graph
Augmenting path
The capacity of an augmenting path
Updating network graph
Updating residual graph
Slide Number 17
Efficiency degradation of the augmenting path method
The shortest augmenting path algorithm
Slide Number 20
Slide Number 21
The shortest augmenting path algorithm
The shortest augmenting path algorithm
Maximum matching algorithm
Maximum matching in a graph
Bipartite graph
Maximum bipartite matching algorithm
Maximum bipartite matching algorithm
Augmenting path
Maximum bipartite matching algorithm
Slide Number 31
Slide Number 32
Maximum bipartite matching algorithm
Maximum bipartite matching algorithm
Maximum bipartite matching algorithm