THE UNIVERSITY OF NEW SOUTH WALES
5. FLOW NETWORKS
Raveen de Silva,
office: K17 202
Copyright By PowCoder代写 加微信 powcoder
Course Admin: ,
School of Computer Science and Engineering UNSW Sydney
Term 2, 2022
Table of Contents
1. Flow Networks
2. Solving the Maximum Flow Problem 3. Applications of Network Flow
Flow Networks
Definition
A flow network G = (V , E ) is a directed graph in which each edge e = (u,v) ∈ E has a positive integer capacity c(u,v) > 0.
There are two distinguished vertices: a source s and a sink t; no edge leaves the sink and no edge enters the source.
s 104 7 t 9
Flow Networks
Examples of flow networks (possibly with several sources and many sinks):
transportation networks gas pipelines
computer networks
and many more.
Flow Networks
Definition
A flow in G is a function f : E → [0, ∞), f (u, v ) ≥ 0, which satisfies
1. Capacity constraint: for all edges e(u,v) ∈ E we require f(u,v) ≤ c(u,v),
i.e. the flow through any edge does not exceed its capacity. 2. Flow conservation: for all vertices v ∈ V − {s , t } we require
f(u,v)= f(v,w), (u,v )∈E (v ,w )∈E
i.e. the flow into any vertex (other than the source and the sink) equals the flow out of that vertex.
Flow Networks
Definition
The value of a flow is defined as
|f|= f(s,v)= f(v,t),
v:(s,v)∈E v:(v,t)∈E
i.e. the flow leaving the source, or equivalently, the flow arriving at the sink.
Given a flow network, our goal is to find a flow of maximum value.
Maximum Flow
Integrality Theorem
If all capacities are integers (as we assumed earlier), then there is a flow of maximum value such that f(u,v) is an integer for each edge (u,v) ∈ E.
This means that there is always at least one solution entirely in integers. We will only consider integer solutions hereafter.
Maximum Flow
In the following example, f /c represents f units of flow sent through an edge of capacity c.
15/20 7/7 t
The pictured flow has a value of 19 units, and it does not appear possible to send another unit of flow. But we can do better!
Maximum Flow
Here is a flow of value 23 units in the same flow network.
19/20 7/7 t
Maximum Flow
This example demonstrates that the most basic greedy algorithm – send flow one unit at a time along arbitrarily chosen paths – does not always achieve the maximum flow.
What went wrong in the first attempt?
We sent 19 units of flow to vertex v3, only to send four units
back to v2.
It would have been better to send those four units of flow to t directly, but this may not have been obvious at the time this decision was made.
We need a way to correct mistakes! We would like to send flow from v2 back to v3 so as to “cancel out” the earlier allocation.
Residual Flow Network
Definition
Given a flow in a flow network, the residual flow network is the network made up of the leftover capacities.
Flow network
Residual flow network
8/13 4/4 5 4
Residual Flow Network
Suppose the original flow network has an edge from v to w with capacity c, and that f units of flow are being sent through this edge.
The residual flow network has two edges:
1. an edge from v to w with capacity c −f, and 2. an edge from w to v with capacity f .
These capacities represent the amount of additional flow in each direction. Note that sending flow on the “virtual” edge from w to v counteracts the already assigned flow from v to w.
Edgesofcapacityzero(whenf =0orf =c)neednotbe included.
Residual Flow Network
Suppose the original flow network has an edge from v to w with capacity c1 and flow f1 units, and an edge from w to v with capacity c2 and flow f2 units.
What are the corresponding edges in the residual graph? How much flow can be sent from v to w (and vice versa)?
The forward edge allows c1 − f1 additional units of flow, and we can also send up to f2 units to cancel the flow through the reverse edge.
Thus we create edges from v to w with capacity c1 − f1 + f2 and similarly from w to v with capacity c2 − f2 + f1.
Augmenting Paths
Definition
An augmenting path is a path from s to t in the residual flow network.
The residual flow network below corresponds to the earlier example of a flow of value 19 units. An augmenting path is pictured in red.
Augmenting Paths
The capacity of an augmenting path is the capacity of its “bottleneck” edge, i.e., the edge of smallest capacity.
We can now send that amount of flow along the augmenting path, recalculating the flow and the residual capacities for each edge used.
Suppose we have an augmenting path of capacity f , including an edge from v to w. We should:
cancel up to f units of flow being sent from w to v,
add the remainder of these f units to the flow being sent from v to w,
increase the residual capacity from w to v by f , and reduce the residual capacity from v to w by f .
Augmenting Paths
Recall that the augmenting path was as follows.
s v2 v3 t 8 5 15
After sending four units of flow along this path, the new residual flow network is pictured below.
Augmenting Paths
The flow used to be as follows.
15/20 7/7 t
Augmenting Paths
Pictured below is the new flow, after sending four units of flow alongthepaths→v2 →v3 →t.
19/20 7/7 t
Note that the four units of flow previously sent from v3 to v2 have been cancelled out.
Table of Contents
1. Flow Networks
2. Solving the Maximum Flow Problem 3. Applications of Network Flow
Ford-Fulkerson algorithm
Keep adding flow through new augmenting paths for as long as it is possible.
When there are no more augmenting paths, you have achieved the largest possible flow in the network.
Ford-Fulkerson algorithm: Example (1/5)
Ford-Fulkerson algorithm: Example (2/5)
0/20 0/7 t
Ford-Fulkerson algorithm: Example (3/5)
7/20 7/7 t
Ford-Fulkerson algorithm: Example (4/5)
15/20 7/7 t
Ford-Fulkerson algorithm: Example (5/5)
19/20 7/7 t
Ford-Fulkerson algorithm
Why does this procedure terminate?
Why can’t we get stuck in a loop, which keeps adding augmenting paths forever?
If all the capacities are integers, then each augmenting path increases the flow through the network by at least 1 unit.
However, the total flow is finite. In particular, it cannot be larger than the sum of all capacities of all edges leaving the source.
We conclude that the process must terminate eventually.
Ford-Fulkerson algorithm
Even if the procedure does terminate, why does it produce a flow of the largest possible value?
Maybe we have created bottlenecks by choosing bad augmenting paths; maybe better choices of augmenting paths could produce a larger total flow through the network?
This is not at all obvious, and to show that this is not the case we need a mathematical proof!
Cuts in a Flow Network
The proof is based on the notion of a minimal cut in a flow network.
Definition
A cut in a flow network is any partition of the vertices of the underlying graph into two subsets S and T such that:
1. S ∪ T = V
2. S ∩ T = ∅
3. s ∈ S and t ∈ T.
Cuts in a Flow Network
Definition
The capacity c(S,T) of a cut (S,T) is the sum of capacities of all edges leaving S and entering T, i.e.
c(S,T)= {c(u,v):u∈S,v∈T}. (u,v)∈E
Note that the capacities of edges going in the opposite direction, i.e. from T to S, do not count.
Cuts in a Flow Network
Definition
Given a flow f, the flow f(S,T) through a cut (S,T) is the total flow through edges from S to T minus the total flow through edges from T to S, i.e.
f(S,T)= {f(u,v):u∈S,v∈T} (u,v)∈E
− {f(u,v):u∈T,v∈S}. (u,v)∈E
Cuts in a Flow Network
Prove that for any flow f, the flow through any cut (S,T) is equal to the value of the flow, i.e.
f (S , T ) = |f |.
Recall the definition of the value of a flow, and use the property of flow conservation.
Cuts in a Flow Network
An edge from S to T counts its full capacity towards c(S,T), but only the flow through it towards f (S , T ).
An edge from T to S counts zero towards c(S,T), but counts the flow through it in the negative towards f (S , T ).
Therefore f (S , T ) ≤ c (S , T ).
It follows that |f | ≤ c (S , T ), so the value of any flow is at most the capacity of any cut.
Cuts in a Flow Network: Example
15/20 7/7 t
Cuts in a Flow Network: Example
In the above example the net flow across the cut is given by f(S,T) = f(v1,v3)+f(v2,v4)−f(v2,v3) = 12+11−4 = 19.
Note that the flow in the opposite direction (from T to S) is subtracted.
The capacity of the cut c(S,T) is given by
c (S , T ) = c (v1 , v3 ) + c (v2 , v4 ) = 12 + 14 = 26.
As we have mentioned, we add only the capacities of edges from S to T and not of edges in the opposite direction.
The maximal amount of flow in a flow network is equal to the capacity of the cut of minimal capacity.
Let f be a flow. Recall that the value |f | is at most the capacity of any cut: c(S,T).
Thus, if we find a flow f which equals the capacity of some cut (S,T), then such flow must be maximal and the capacity of such a cut must be minimal.
We now show that when the Ford-Fulkerson algorithm terminates, it produces a flow equal to the capacity of an appropriately defined cut.
Assume that the Ford-Fulkerson algorithm has terminated, so there no more augmenting paths from the source s to the sink t in the last residual flow network.
Define S to be the source s and all vertices u such that there is a path in the residual flow network from the source s to that vertex u.
Define T to be the set of all vertices for which there is no such path.
Since there are no more augmenting paths from s to t, clearly the sink t belongs to T.
19/20 7/7 t
All the edges from S to T are fully occupied with flow, and all the edges from T to S are empty.
Suppose an edge (u, v ) from S to T has any additional capacity left. Then in the residual flow network, the path from s to u could be extended to a path from s to v. This contradicts our assumption that v ∈ T .
Suppose an edge (y,x) from T to S has any flow in it. Then in the residual flow network, the path from s to x could be ex- tended to a path from s to y. This contradicts our assumption that y ∈ T.
Since all edges from S to T are occupied with flows to their full capacity, and also there is no flow from T to S, the flow across the cut (S,T) is precisely equal to the capacity of this cut, i.e., f (S , T ) = c (S , T ).
Thus, such a flow is maximal and the corresponding cut is a minimal cut, regardless of the particular way in which the augmenting paths were chosen.
How efficient is the Ford-Fulkerson algorithm?
0/1000 0/1000
s 0/1 t s 1 t
0/1000 1000 1000 ww
0/1000 999
s 1/1 t s 1 t
0/1000 1/1000 1000 ww
1/1000 1/1000 999
s 0/1 t s 1 t
11 1/1000 999 999
1/1000 998
s 1/1 t s 1 t
1/1000 2/1000 999 998 ww
Ford- : Time Complexity
The number of augmenting paths can be up to the value of the max flow, denoted |f |.
Each augmenting path is found in O (V + E ), e.g. by DFS. In any sensible flow network, V ≤ E + 1, so we can write this as simply O(E).
Therefore the time complexity of the Ford-Fulkerson algorithm is O(E|f|).
Ford- : Time Complexity
Recall that the input specifies V vertices and E edges, as well as a capacity for each edge.
If the capacities are all ≤ C , then the length of the input (i.e. the number of bits required to encode it) is O(V + E log C).
However, the value of the maximum flow |f | can be as large as VC in general.
Therefore, the time complexity O(E|f |) can be exponential in the size of the input, which is unsatisfactory.
The Edmonds-Karp algorithm improves the Ford-Fulkerson algorithm in a simple way: always choose the augmenting path which consists of the fewest edges.
At each step, we find the next augmenting path using breadth-first search in O(V + E) = O(E) time.
Note that this choice is somewhat counter-intuitive: augmenting paths are chosen based only on length, so we may end up flowing edges with small capacities before edges with large capacities.
What is the time complexity of the Edmonds-Karp algorithm?
It can be proven (see CLRS pp.727–730) that the number of augmenting paths is O(VE), and since each takes O(E) to find, the time complexity is O(VE2).
Note also that Edmonds-Karp is a specialisation of Ford-Fulkerson, so the original O(E|f |) bound also applies.
Faster max flow algorithms
Faster max flow algorithms exist, e.g. Dinic’s in O(V2E) and Preflow-Push in O(V3), but we will not allow them in assessments in this course.
Max flow algorithms based on augmenting paths tend to perform better in practice than their worst case complexity might suggest, but we can’t rely on this especially in this course.
In March 2022, Chen et al. developed an “almost linear” time algorithm for max flow.
Table of Contents
1. Flow Networks
2. Solving the Maximum Flow Problem 3. Applications of Network Flow
Networks with multiple sources and sinks
Flow networks with multiple sources and sinks are reducible to networks with a single source and single sink by adding a “super-source” and “super-sink” and connecting them to all sources and sinks, respectively, by edges of infinite capacity.
s ∞ s2 t ∞ t 2
Networks with vertex capacities
Sometimes not only the edges but also the vertices vi of the flow graph might have capacities C(vi), which limit the total throughput of the flow coming to the vertex (and, consequently, also leaving the vertex):
f(u,v)= f(v,w)≤C(v). e(u,v)∈E e(v,w)∈E
We can handle this by reducing it to a situation with only edge capacities!
Networks with vertex capacities
Suppose vertex v has capacity C(v). Split v into two vertices vin and vout.
Attach all of v’s incoming edges to vin and all its outgoing edges from vout.
Connect vin and vout with an edge e∗ = (vin,vout) of capacity C(v).
Networks with vertex capacities
Example problem: Movie Rental
Instance: Suppose you have a movie rental agency.
At the moment you have k movies in stock, with mi copies of
There are n customers, who have each specified which subset of the k movies they are willing to see. However, no customer can rent out more than 5 movies at a time.
Task: Design an algorithm which runs in time polynomial in n and k and dispatches the largest possible number of movies.
Example problem: Movie Rental
Construct a flow network with: source s and sink t,
a vertex ui for each customer i and a vertex vj for each movie j,
for each i, an edge from s to ui with capacity 5,
for each customer i, for each movie j that they are willing to
see, an edge from ui to vj with capacity 1.
for each j, an edge from vj to t with capacity mj.
Example problem: Movie Rental
Example problem: Movie Rental
Consider a flow in this graph.
Each customer-movie edge has capacity 1, so we will interpret
a flow of 1 from ui to vj as assigning movie j to customer i. Each customer only receives movies that they want to see.
By flow conservation, the amount of flow sent along the edge from s to ui is equal to the total flow sent from ui to all movie vertices vj , so it represents the number of movies received by customer i. Again, the capacity constraint ensures that this does not exceed 5 as required.
Similarly, the movie stock levels mj are also respected.
Example problem: Movie Rental
Therefore, any flow in this graph corresponds to a valid allocation of movies to customers.
To maximise the movies dispatched, we find the maximum flow using the Edmonds-Karp algorithm.
There are n+k +2 vertices and up to nk +n+k edges, so the time complexity is O((n + k + 2)(nk + n + k)2), which is polynomial in n and k as required.
Since the value of any flow is constrained by the total capacity from s, which in this case is 5n, we can achieve a tighter bound of O(E|f |) = O(n(nk + n + k)) = O(n2k).
Example problem: Cargo Allocation
Instance: The storage space of a ship is in the form of a rectangular grid of cells with n rows and m columns. Some of the cells are taken by support pillars and cannot be used for storage, so they have 0 capacity.
You are given the capacity of every cell; the cell in row i and column j has capacity C(i,j). To ensure the stability of the ship, the total weight in each row i must not exceed Cr(i) and the total weight in each column j must not exceed Cc(j).
Task: Design an algorithm which runs in time polynomial in n and m and allocates the maximum possible weight of cargo without exceeding any of the cell, row or column capacities.
Example problem: Cargo Allocation
row5 col cap
C(5,1) Cc (1)
C(5,2) Cc (2)
C(5,4) Cc (4)
Example problem: Cargo Allocation
Construct a flow network with:
source s and sink t,
a vertex ri for each row i and a vertex cj for each column j,
for each i, an edge from s to ri with capacity Cr(i),
for each cell (i,j) which is not a pillar, an edge from ri to cj with capacity C(i,j).
for each j, an edge from cj to t with capacity Cc(j).
Example problem: Cargo Allocation
Cr(1) r sr3
Example problem: Cargo Allocation
Consider a flow in this graph.
We will interpret the amount of flow sent along the edge from
ri to cj as the weight of cargo stored in cell (i,j).
By the capacity constraint, this weight cannot exceed the edge
capacity C(i,j), so the weight limit of each cell is satisfied.
By flow conservation, the amount of flow sent along the edge from s to ri is equal to the total flow sent from ri to all column vertices cj , so it represents the total weight stored in row i. Again, the capacity constraint ensures that this does not exceed Cr(i) as required.
Similarly, the column capacities Cc(j) are also respected.
Example pr
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com