PowerPoint Presentation
Faculty of Information Technology,
Monash University
FIT2004: Algorithms and Data Structures
Week 11: Network Flow
These slides are prepared by M. A. Cheema and are based on the material developed by Arun Konagurthu and Lloyd Allison.
Announcements
SETU Feedback and nominations for Teaching Excellence Awards
Links on Moodle (on the right)
Closes 21st June 2020
Real-time anonymous feedback: https://docs.google.com/forms/d/e/1FAIpQLSdAlUwUNPJtccGebDF-fg41oUCWrt-of5A2mg5I7VtEK6vN3A/viewform
FIT2004: Lec-11: Network Flow
Outline
FIT2004: Lec-11: Network Flow
Maximum Flow Problem
Ford-Fulkerson Algorithm
Min-cut Max-flow Theorem
Flow Networks
FIT2004: Lec-11: Network Flow
A flow network is a connected directed graph where
there is a single source vertex and a single sink/destination vertex;
each edge has a given (non-negative) capacity (usually integers)
giving the maximum amount/rate of flow that the edge can carry;
Flow networks model many real-world problems
Water flowing through an assembly of pipes.
Electric current flowing through electrical circuits.
Information flowing through communication networks
Can be applied to many scenarios (unrelated to physical flows).
b
a
d
c
s
3
5
3
5
3
t
3
5
Some basic notations
FIT2004: Lec-11: Network Flow
Set of all incoming edges to a vertex v: denoted as Ein(v)
Ein(b) = s b, c b
Ein(a) = ?
Set of all outgoing edges from a vertex v: denoted as Eout(v)
Eout(b) = b d
Eout(a) = ?
Source Vertex: denoted as s (has no incoming edges)
Sink/target vertex: denoted as t (has no outgoing edges)
b
a
d
c
s
3
5
3
5
3
t
3
5
Flow
FIT2004: Lec-11: Network Flow
Flow is an assignment of how much material is flowing through each edge in the flow network given its stated edge capacity.
Green numbers indicate flow and red indicate capacity. Flow is not shown if 0
b
a
d
c
s
3/3
2/5
3/3
5/5
0/3
t
3/3
5/5
Flow
FIT2004: Lec-11: Network Flow
All vertices (except source and sink) conserve their flow. That is
The total amount flowing into any vertex (through incoming edges)
IS EQUAL TO
the total amount flowing out of that vertex (through outgoing edges).
This key property is called flow conservation.
b
a
d
c
s
3/3
2/5
3/3
5/5
0/3
t
3/3
5/5
Properties of a Flow Network
FIT2004: Lec-11: Network Flow
A flow network must satisfy the following two properties.
Property 1: Capacity Constraint
For each edge e, its flow, denoted as f(e), is bounded by the capacity of its edge, i.e., 0 ≤ f(e) ≤ c(e) where c(e) is the capacity of the edge
Property 2: Flow Conservation
For any vertex v (except source and sink), the total flow coming into the vertex must be equal to the total flow going out from this vertex – formally
FIT2004: Lec-11: Network Flow
b
a
d
c
s
3/3
2/5
3/3
5/5
0/3
t
3/3
5/5
Maximum-flow Problem
FIT2004: Lec-11: Network Flow
Value of a flow in a network:
Given that flow network satisfies the capacity constraint and flow conservation properties, flow of a network is the total flow out of the source vertex. Equivalently, this is the same as the total flow into sink vertex.
What is the flow value in the flow network at bottom left?
What is the flow value in the flow network at bottom right?
b
a
d
c
s
11/16
8/13
0/10
1/4
4/9
11/14
15/20
7/7
t
12/12
4/4
b
a
d
c
s
3/3
2/5
3/3
5/5
0/3
t
3/3
5/5
Maximum-flow Problem
Value of a flow in a network:
Given that flow network satisfies the capacity constraint and flow conservation properties, flow of a network is the total flow out of the source vertex.
Maximum-flow problem
Given a flow network, determine the maximum value of the flow that can be sent from source s to sink t without violating the flow network properties.
b
a
d
c
s
11/16
8/13
0/10
1/4
4/9
11/14
15/20
7/7
t
12/12
4/4
b
a
d
c
s
3/3
2/5
3/3
5/5
0/3
t
3/3
5/5
Outline
FIT2004: Lec-11: Network Flow
Maximum Flow Problem
Ford-Fulkerson Algorithm
Min-cut Max-flow Theorem
Ford Fulkerson Intuition
FIT2004: Lec-11: Network Flow
b
a
d
c
s
0/3
0/5
0/3
0/5
0/3
t
0/3
0/5
Quiz time!
https://flux.qa – RFIBMB
How can we increase the flow in the graph above?
Ford Fulkerson Intuition
FIT2004: Lec-11: Network Flow
b
a
d
c
s
0/3
0/5
0/3
0/5
0/3
t
0/3
0/5
How can we increase the flow in the graph above?
Choose a path from source to sink
Increase flow along it
Seems easy enough!
Ford Fulkerson Intuition
FIT2004: Lec-11: Network Flow
b
a
d
c
s
3/3
2/5
3/3
5/5
0/3
t
3/3
5/5
Can we increase the flow in the above network?
Quiz time!
https://flux.qa – RFIBMB
Ford Fulkerson Intuition
FIT2004: Lec-11: Network Flow
b
a
d
c
s
3/3
2/5
3/3
5/5
0/3
t
3/3
5/5
Can we increase the flow in the above network?
We can!
But there is no path from source to sink with spare capacity…
Ford Fulkerson Intuition
FIT2004: Lec-11: Network Flow
b
a
d
c
s
3/3
2/5
3/3
5/5
0/3
t
3/3
5/5
b
a
d
c
s
3/3
2/5
0/3
5/5
3/3
t
3/3
5/5
There is not path from s to t with spare capacity
Instead, we “redirect” the 3 units on the edge c->b
They are now going to t
Ford Fulkerson Intuition
FIT2004: Lec-11: Network Flow
b
a
d
c
s
3/3
2/5
3/3
5/5
0/3
t
3/3
5/5
b
a
d
c
s
3/3
2/5
0/3
5/5
3/3
t
3/3
5/5
There is not path from s to t with spare capacity
Instead, we “redirect” the 3 units on the edge c->b
They are now going to t
In the second diagram, the flow through b is not conserved
We can send 3 more units along s->b to both increase total flow and conserve flow through b
Ford Fulkerson Intuition
FIT2004: Lec-11: Network Flow
b
a
d
c
s
3/3
2/5
3/3
5/5
0/3
t
3/3
5/5
b
a
d
c
s
3/3
5/5
0/3
5/5
3/3
t
3/3
5/5
There is not path from s to t with spare capacity
Instead, we “redirect” the 3 units on the edge c->b
They are now going to t
This means that we need to send 3 more units into b (because of flow conservation)
In this case, the extra flow comes from s
Ford Fulkerson Intuition
FIT2004: Lec-11: Network Flow
b
a
d
c
s
3/3
2/5
3/3
5/5
0/3
t
3/3
5/5
What actually happened here?
We increased the total flow by 3:
We sent 3 units along s->b, c->t
We “removed” 3 units of flow from c->b
Our path was s->b->c->t, but we had a backwards edge…
b
a
d
c
s
3/3
5/5
0/3
5/5
3/3
t
3/3
5/5
Residual Network
FIT2004: Lec-11: Network Flow
Residual network has the same vertices as the original network.
For every directed edge uv in flow network, we add two edges in the residual network:
Forward edge/Residual edge: An edge in the same direction as uv with the residual/remaining capacity
Backward edge/Reversible flow edge: An edge in the direction opposite to uv (i.e., vu) with weight equal to the current flow of uv in the flow network
Flow Network: Green numbers indicate flow and red indicate capacity. Flow is not shown if 0
b
a
d
c
s
1
2
2
t
2
4
1
5
5
1
b
a
d
c
s
2/3
4/5
1/3
5/5
1/3
t
2/3
5/5
1
Residual Network: Where possible red edges indicate reversible flow and green indicate residual capacity
2
1
Augmenting Path in Residual Network
FIT2004: Lec-11: Network Flow
Augmenting path is any simple path (a path without repeating vertices) from source s to target t.
E.g., s b c t (shown in purple edges)
Residual capacity of a path is the minimum edge weight on this path (e.g., 4 in the example)
For each edge along this path, we can push additional flow equal to the “residual capacity of the path” in the flow network, e.g., 1 along each edge on s b c t
b
a
d
c
s
1
2
2
t
2
2
4
1
5
5
1
b
a
d
c
s
2/3
4/5
1/3
5/5
1/3
t
2/3
5/5
1
1
Flow Network: Green numbers indicate flow and red indicate capacity. Flow is not shown if 0
Residual Network: Where possible red edges indicate reversible flow and green indicate residual capacity
Ford-Fulkerson Method – Worked example (by hand in lecture)
b
a
d
c
s
0/3
0/5
0/3
0/5
0/3
t
0/3
0/5
b
a
d
c
s
5
3
3
t
3
3
5
5
Total flow: 0
Ford-Fulkerson Method – Worked example (by hand in lecture)
b
a
d
c
s
0/3
0/5
0/3
0/5
0/3
t
0/3
0/5
b
a
d
c
s
5
3
3
t
3
3
5
5
Total flow: 0
Ford-Fulkerson Method – Worked example (by hand in lecture)
b
a
d
c
s
0/3
0/5
0/3
0/5
0/3
t
0/3
0/5
b
a
d
c
s
5
3
3
t
3
3
5
5
Path found: capacity = 3
Total flow: 0
Ford-Fulkerson Method – Worked example (by hand in lecture)
b
a
d
c
s
3/3
0/5
3/3
3/5
0/3
t
3/3
3/5
b
a
d
c
s
5
3
3
t
3
3
5
5
Path found: capacity = 3
Total flow: 3
Ford-Fulkerson Method – Worked example (by hand in lecture)
b
a
d
c
s
3/3
0/5
3/3
3/5
0/3
t
3/3
3/5
b
a
d
c
s
5
3
3
t
3
3
5
5
Total flow: 3
Update residual to match new flows
Ford-Fulkerson Method – Worked example (by hand in lecture)
b
a
d
c
s
3/3
0/5
3/3
3/5
0/3
t
3/3
3/5
b
a
d
c
s
5
3
t
2
2
Total flow: 3
Update residual to match new flows
3
3
3
3
3
Ford-Fulkerson Method – Worked example (by hand in lecture)
b
a
d
c
s
3/3
0/5
3/3
3/5
0/3
t
3/3
3/5
b
a
d
c
s
5
3
t
2
2
Total flow: 3
3
3
3
3
3
Path found: capacity = 2
Ford-Fulkerson Method – Worked example (by hand in lecture)
b
a
d
c
s
3/3
2/5
3/3
5/5
0/3
t
3/3
5/5
b
a
d
c
s
5
3
t
2
2
Total flow: 5
3
3
3
3
3
Path found: capacity = 2
Ford-Fulkerson Method – Worked example (by hand in lecture)
b
a
d
c
s
3/3
2/5
3/3
5/5
0/3
t
3/3
5/5
b
a
d
c
s
3
3
t
Total flow: 5
3
3
5
5
3
Update residual to match new flows
2
Ford-Fulkerson Method – Worked example (by hand in lecture)
b
a
d
c
s
3/3
2/5
3/3
5/5
0/3
t
3/3
5/5
b
a
d
c
s
3
3
t
Total flow: 5
3
3
5
5
3
2
Path found: capacity = 3
Ford-Fulkerson Method – Worked example (by hand in lecture)
b
a
d
c
s
3/3
5/5
0/3
5/5
3/3
t
3/3
5/5
b
a
d
c
s
3
3
t
Total flow: 8
3
3
5
5
3
2
Path found: capacity = 3
Ford-Fulkerson Method – Worked example (by hand in lecture)
b
a
d
c
s
3/3
5/5
0/3
5/5
3/3
t
3/3
5/5
b
a
d
c
s
t
Total flow: 8
3
3
5
5
3
5
Update residual to match new flows
3
Ford-Fulkerson Method – Worked example (by hand in lecture)
b
a
d
c
s
3/3
5/5
0/3
5/5
3/3
t
3/3
5/5
b
a
d
c
s
t
Total flow: 8
3
3
5
5
3
5
No more augmenting paths!
3
Complexity Analysis
FIT2004: Lec-11: Network Flow
Cost of finding an augmenting path:
Using BFS, cost is O(V+E) (or just O(E) since the graph is connected)
Augmenting flow along a path:
length of path ≤ V, so cost is O(V)
Updating the residual:
Same amount of work as updating the flows along the augmenting path, O(V)
Total work in one iteration of the loop:
O(V+E) = O(E)
Complexity Analysis
FIT2004: Lec-11: Network Flow
Total work in one iteration of the loop:
O(V+E) = O(E)
How many iterations?
Assuming integer flows and capacities…
Each iteration, flow grows by at least 1
If maximum flow in graph is F
Maximum number of iterations is also F
Total work:
O(EF)
Complexity Analysis
FIT2004: Lec-11: Network Flow
Total work:
O(EF)
Not examinable:
This looks polynomial
It isn’t because F is a number, so its value is exponential in the space required to store it
It can be proven that the complexity is O(VE2) when using BFS to find augmenting paths, which is polynomial
Proof of Correctness
FIT2004: Lec-11: Network Flow
Does the algorithm terminate?
Yes (assuming all capacities are integers), because
the flow always increases by at least 1 and the algorithm terminates when flow is equal to the maximum flow
When the algorithm terminates (i.e., there is no augmenting path in residual network), the flow of the network is the maximum flow.
We will need to understand “min-cut and max-flow” theorem to prove this fact
Outline
FIT2004: Lec-11: Network Flow
Maximum Flow Problem
Ford-Fulkerson Algorithm
Min-cut Max-flow Theorem
Flow and capacity of a cut
FIT2004: Lec-11: Network Flow
A cut (S,T) of a flow network partitions the vertices of the network into two disjoint partitions S and T such that source s is in S and target t is in T.
E.g., S = {s,a,b} and T = {t, c, d}
Cut-set of a cut (S,T) is the set of edges that “cross” the cut, i.e., each edge connects one vertex in S with another in T.
E.g., the cut-set for the example is ac, bd, cb (green edges)
The edges that have direction from a vertex in S to a vertex in T are called outgoing edges of the cut.
E.g., ac and bd are the outgoing edges of the cut
The edges that have direction from a vertex in T to a vertex in S are called incoming edges of the cut.
E.g., cb is an incoming edge of the cut.
b
a
d
c
s
11/16
8/13
10
1/4
4/9
11/14
15/20
7/7
t
12/12
4/4
Flow and capacity of a cut
FIT2004: Lec-11: Network Flow
Capacity of a cut (S,T) is just the total capacity of its outgoing edges
E.g., capacity of the cut in the example is 12 + 14 = 26
Flow of a cut (S,T) is Total flow of outgoing edges – total flow of incoming edges
E.g., flow in the example is 12 + 11 – 4 = 19
Capacity is just flow from the S side to the T side
Flow requires us to subtract the flow going from the T side to the S side
b
a
d
c
s
11/16
8/13
10
1/4
4/9
11/14
15/20
7/7
t
12/12
4/4
Is it true that flow of a cut is always less than or equal to the capacity of the cut?
Yes, because
Flow of an edge ≤ capacity of an edge
Capacity of a cut does not subtract capacities for incoming edges
Flow and capacity of a cut
FIT2004: Lec-11: Network Flow
Capacity of a cut (S,T): the total capacity of its outgoing edges
Flow of a cut (S,T): Total flow of its outgoing edges – total flow of its incoming edges
Assume S = {s, a,b,c,d} and T = {t}.
What is the capacity of this cut?
What is the flow of this cut?
Assume S = {s, a, b,d} and T = {c,t}.
What is the capacity of this cut?
What is the flow of this cut?
Assume S = {s, a} and T = {b,c,d,t}.
What is the capacity of this cut?
What is the flow of this cut?
What is the flow value of this network?
Note: flow of all of the above cuts is 19
which is the same as flow of the network.
I.e., flow of every cut = flow of the network
Let’s prove this formally
b
a
d
c
s
11/16
8/13
10
1/4
4/9
11/14
15/20
7/7
t
12/12
4/4
Flow of a cut = Flow of the network
FIT2004: Lec-11: Network Flow
Let Fout (v) be the total flow going out of a vertex and Fin(v) be the total flow coming in the vertex
Recall that flow of a network is the total flow going out from the source s.
Flow of the network = Fout (s)
Flow conservation property: Fout (v) – Fin (v) = 0 for every vertex except s and t
Flow of the network = Fout (s)
Flow of the network = Fout (s) +
recall S is the cut containing s and excluding t
Since Fin (s) = 0, we can rewrite the flow as.
Flow of the network =
b
a
d
c
s
11/16
8/13
10
1/4
4/9
11/14
15/20
7/7
t
12/12
4/4
Flow of a cut = Flow of the network
FIT2004: Lec-11: Network Flow
Flow of the network =
Each vertex v in S (red vertices) can have two types of edges
Grey edges (the edges that connect the vertex to another vertex in S)
Green edges (the edges that connect the vertex to a vertex in T)
Let be the total flow out from v via grey edges. Similarly, be the total flow coming to v via grey edges.
Let be the total flow out from v via green edges. Similarly, be the total flow coming to v via green edges.
We have + = and + =
b
a
d
c
s
11/16
8/13
10
1/4
4/9
11/14
15/20
7/7
t
12/12
4/4
Flow of a cut = Flow of the network
FIT2004: Lec-11: Network Flow
We have + = and + =
From before, Flow of the network =
Flow of the network = )
Flow of the network =
Note that because each grey edge appears once as an incoming edge for one vertex and once as an outgoing edge for another vertex.
Flow of the network =
Flow of the network
b
a
d
c
s
11/16
8/13
10
1/4
4/9
11/14
15/20
7/7
t
12/12
4/4
Min-cut Max-Flow Theorem
FIT2004: Lec-11: Network Flow
Min-cut of a flow network is the cut with the minimum capacity
We know that
Flow of a cut ≤ capacity of the cut
Flow of every cut = Flow of the network
Therefore, Maximum possible flow of the network ≤ capacity of every cut
Or, Maximum possible flow of the network ≤ capacity of min-cut
What if we can find a cut such that the flow of the network = capacity of the cut
This would mean flow of the network is the maximum possible (we have found maximum possible flow)
The cut is the min-cut of the flow network
Min-cut Max-Flow Theorem
Maximum possible flow of a network = capacity of the min-cut
b
a
d
c
s
11/16
8/13
10
1/4
4/9
11/14
15/20
7/7
t
12/12
4/4
Min-cut Max-Flow Theorem
FIT2004: Lec-11: Network Flow
Capacity of a cut (S,T) is the total capacity of its outgoing edges
Flow of a cut (S,T) = Total flow of its outgoing edges – total flow of its incoming edges
Flow of a cut = capacity of the cut when:
Flow on each outgoing edge of the cut is equal to the capacity of the edge; AND
Flow on each incoming edge of the cut is zero
We show that when the algorithm terminates, there exists a cut for which both of the above two conditions hold which imply that the flow of the cut is equal to its capacity.
This guarantees that the flow is maximum
b
a
d
c
s
11/16
8/13
10
1/4
4/9
11/14
15/20
7/7
t
12/12
4/4
Proof of correctness
Suppose the algorithm has terminated (there does not exist any augmenting path in the residual network).
We define a cut (S,T) such that
S contains every vertex v that is reachable from s in the residual network.
T contains every other vertex. Note t cannot be in S because it is not reachable from S (no augmenting path)
b
a
d
c
s
3/4
5/6
0/3
5/5
3/4
t
3/3
5/6
b
a
d
c
s
t
3
3
5
5
3
5
3
1
1
1
1
Proof of correctness
Flow of this cut = Capacity of this cut because
For each outgoing edge ac, its flow is equal to the capacity of the edge
Otherwise, we would have an edge ac in the residual network which would mean c is reachable from s but we know this is not the case as c is not in S.
For each incoming edge c b, its flow is zero.
Otherwise, there would be an edge bc in the residual network implying c is reachable from s but we know this is not the case as c is not in S.
Therefore, the flow is maximum when the algorithm terminates
b
a
d
c
s
3/4
5/6
0/3
5/5
3/4
t
3/3
5/6
b
a
d
c
s
t
3
3
5
5
3
5
3
1
1
1
1
Summary
FIT2004: Lec-11: Network Flow
Take home message
Maximum flow of a network is equal to its min-cut and can be found using Ford-Fulkerson
Things to do (this list is not exhaustive)
Make sure you understand
the two algorithms
understand why Ford-Fulkerson is correct
Start preparing for the final exam
Coming Up Next
Topological sorting and final exam
Revision – bring any questions you would like to discuss to next week’s lecture!
/docProps/thumbnail.jpeg