CS代写 Algorithms & Data Structures (Winter 2022) Graphs

Algorithms & Data Structures (Winter 2022) Graphs – Flow Network 2

Announcements

• Introduction.
• Topological Sort. / Strong Connected Components
• Network Flow 1. • Introduction
• Ford-Fulkerson
• Network Flow 2. • Min-cuts
• Shortest Path.
• Minimum Spanning Trees. • Bipartite Graphs.

Flow Network
G = (V, E) directed.
Each edge (u, v) has a capacity c(u, v) ≥ 0.
If (u,v) Ï E, then c(u,v) = 0.
Source vertex s, sink vertex t, assume s v
c(u,v) is a non-negative integer. If (u,v) ⍷ E, then (u,v) Ï E.
No incoming edges in source. No outcoming edges in sink.
t for all v ∈ V. 4

Ford-Fulkerson algorithm – correctness
Claim: The Ford-Fulkerson algorithm terminates. O(C ∙ |E|)
• The capacities and flows are
strictly positive integers.
• The sum of capacities leaving
s is finite.
• Bottleneck values β are strictly
positive integers.
• The flow increase by β after each
iteration of the loop.
• The flow is an increasing sequence of integers that is bounded.
• How do we know that when the algorithm terminates, we have actually found a
maximum flow?
• The max-flow min-cut theorem, tells us that a flow is maximum if and only if
its residual network contains no augmenting path.
• We must first explore the notion of a cut of a flow network.
while (there is a s-t path in Gf) {
f.augment(P)
update Gf based on new f

A graph cut is a partition of the graph vertices into two disjoint sets.
ThecrossingedgesfromStoV-Sare{(u,v)| u∈S,v∈ V-S }, also called the cut set. 6

Cuts in flow networks
Definition: An s-t cut of a flow network is a cut A, B such that: • 𝑠∈𝐴and𝑡∈𝐵
Notation: We write cut(A,B) the set of edges from A to B.
Definition: The capacity of an s-t cut is e∈cut(A,B)

Cuts in flow networks

Minimum cut problem
• The minimum cut problem is to compute an (s, t)-cut whose capacity is as small as possible.
• Intuitively, the minimum cut is the cheapest way to disrupt all flow from s to t.
The bottleneck
How to cut supplies!

Flow through a cut
Claim: Given a flow network. Let f be a flow and A, B be a s-t cut. Then, the net flow is defined to be:
f= ∑ f(e)− ∑ f(e) e∈cut(A,B) e∈cut(B,A)
Notation: |f| = fout(A) – fin(A)

Flow through a cut – Upper bound
Claim: For any network flow f, and any s-t cut(A,B) f≤ ∑c(e)
f =fout(A)−fin(A)
≤ ∑ c(e) e∈cut(A,B)
• The asymmetry between the definitions of flow and capacity of a cut is intentional and important.
• Right-hand side is independent of any particular flow f
• The value of every flow is upper- bounded by the capacity of every cut
• The value of a maximum flow in a
network is bounded from above by the
capacity of a minimum cut of the
e∈cut(A,B)

Flow through a cut – Observations
• Some cuts have greater capacities than others.
• Some flows are greater than others.
• But every flow must be ≤ capacity of every s-t cut. • if we exhibit any s-t cut in G of some value c∗, we know that there
cannot be an s-t flow in G of value greater than c∗.
• Conversely, if we exhibit any s-t flow in G of some value ν∗, we know
that there cannot be an s-t cut in G of value less than ν∗.
• Thus, the value of the maximum flow is less than
capacity of the minimum cut.
• The max-flow min-cut theorem, says that the value of a maximum flow
is in fact equal to the capacity of a minimum cut.

Value of flow in Ford- (Max-flow min-cut theorem)
If f is a flow in a flow network G = (V,E) with source s and sink t , then the following conditions are equivalent:
1. f is a maximum flow in G.
2. The residual network Gf contains no augmenting paths. 3. |f| = c(S,T) for some cut (S, T) of G.

Value of flow in Ford-Fulkerson
• Ford-Fulkerson terminates when there is no augmenting path in the residual graph Gf.
• Let A be the set of vertices reachable from s in Gf, and B=V-A.
• A,Bisas-tcutinGf.
• A,B is an s-t cut in G (G and Gf have the same vertices).
• |f|=fout(A)-fin(A)
• Wewanttoshow: f = ∑ c(e)
• And in particular:
e∈cut(A,B)
1 fout(A)= ∑ c(e) 2 e∈cut(A,B)
f in (A) = 0 14

Value of flow in Ford-Fulkerson
(A∗, B∗) is indeed an s-t cut. It is clearly a partition of V. t ∉ A∗ by the assumption that there is no s-t path in the residual graph; hence t ∈ B∗ as desired.
our assumption that v ∈
Suppose that e = (u, v) is an edge in G for which u ∈ A∗ and v ∈ B∗. We claim that f(e) = ce. For if not, e would be a forward edge in the residual graph Gf , and since u ∈ A∗, there is an s-u path in Gf ; appending e to this path, we would obtain an s-v path in G , contradicting

Value of flow in Ford-Fulkerson
(A∗, B∗) is indeed an s-t cut. It is clearly a partition of V. t ∉ A∗ by the assumption that there is no s-t path in the residual graph; hence t ∈ B∗ as desired.
Suppose that e’ = (u’, v’)
u’ ∈ B∗ and v’ ∈ A∗. We
is an edge in G for which
claim that f(e’) = 0. For if
not, e’ would give rise to
a backward edge e’’ =
graph G , and since v’ ∈ f
this path, we would obtain an s-u’ path in Gf , contradicting our assumption that u’ ∈ B∗.
(v’, u’) in the residual
A∗, there is an s-v’ path in Gf; appending e’’ to

Value of flow in Ford- all edges out of A∗ are completely saturated with flow, while all edges
into A∗ are completely unused.

Max flow = Min cut
• Ford-Fulkerson terminates when there is no path s-t in the residual graph Gf
• This defines a cut in A,B in G (A = nodes reachable from s)
f =fout(A)−fin(A)
= ∑ f(e)− ∑ f(e)
e∈cut(A,B) e∈cut(B,A)
• Ford-Fulkerson flow = ∑
= capacity of cut(A,B)
c(e)−0 e∈cut(A,B)

Computing the min-cut
Q: Given a flow network, how can we compute a minimum cut?
• Run Ford-Fulkerson to compute a maximum flow (it gives us Gf)
• RunBFSorDFSofs.
• The reachable vertices define the set A for the cut

Computing the min-cut – Ford-fulkerson
(1) Initial flow net G
(2) Compute max flow (FF)
(3) Compute Gf and vertices accessible from s
3/4 2/2 2/4
(4) Vertices accessible from s in Gf determine the min cut
1 3 2/3 3/3
2/3 s231 ts 1/4 t
1 2 2 3/4 2/2 2/4

程序代写 CS代考加微信: powcoder QQ: 1823890830 Email: powcoder@163.com

Related Posts