Courses

# Maximum Flow Notes | EduRev

## : Maximum Flow Notes | EduRev

Page 1

Princeton University  •  COS 423  •  Theory of Algorithms  •  Spring 2001  •  Kevin Wayne
Maximum Flow
2
Contents
Contents.
¦ Maximum flow problem.
¦ Minimum cut problem.
¦ Max-flow min-cut theorem.
¦ Augmenting path algorithm.
¦ Capacity-scaling.
¦ Shortest augmenting path.
3
¦ Network reliability.
¦ Security of statistical data.
¦ Distributed computing.
¦ Egalitarian stable matching.
¦ Distributed computing.
¦ Many many more . . .
Maximum Flow and Minimum Cut
Max flow and min cut.
¦ Two very rich algorithmic problems.
¦ Cornerstone problem in combinatorial optimization.
¦ Beautiful mathematical duality.
Nontrivial applications / reductions.
¦ Network connectivity.
¦ Bipartite matching.
¦ Data mining.
¦ Open-pit mining.
¦ Airline scheduling.
¦ Image processing.
¦ Project selection.
¦ Baseball elimination.
4
Max flow network:  G = (V, E, s, t, u) .
¦ (V, E) = directed graph, no parallel arcs.
¦ Two distinguished nodes:  s = source, t = sink.
¦ u(e) = capacity of arc e.
Max Flow Network
Capacity
s
2
3
4
5
6
7
t
15
5
30
15
10
8
15
9
6
10
10
10
15
4
4
Page 2

Princeton University  •  COS 423  •  Theory of Algorithms  •  Spring 2001  •  Kevin Wayne
Maximum Flow
2
Contents
Contents.
¦ Maximum flow problem.
¦ Minimum cut problem.
¦ Max-flow min-cut theorem.
¦ Augmenting path algorithm.
¦ Capacity-scaling.
¦ Shortest augmenting path.
3
¦ Network reliability.
¦ Security of statistical data.
¦ Distributed computing.
¦ Egalitarian stable matching.
¦ Distributed computing.
¦ Many many more . . .
Maximum Flow and Minimum Cut
Max flow and min cut.
¦ Two very rich algorithmic problems.
¦ Cornerstone problem in combinatorial optimization.
¦ Beautiful mathematical duality.
Nontrivial applications / reductions.
¦ Network connectivity.
¦ Bipartite matching.
¦ Data mining.
¦ Open-pit mining.
¦ Airline scheduling.
¦ Image processing.
¦ Project selection.
¦ Baseball elimination.
4
Max flow network:  G = (V, E, s, t, u) .
¦ (V, E) = directed graph, no parallel arcs.
¦ Two distinguished nodes:  s = source, t = sink.
¦ u(e) = capacity of arc e.
Max Flow Network
Capacity
s
2
3
4
5
6
7
t
15
5
30
15
10
8
15
9
6
10
10
10
15
4
4
5
An s-t flow is a function  f: E ?´ that satisfies:
¦ For each e ? E: 0  £ f(e)  £ u(e) (capacity)
¦ For each v ? V – {s, t}: (conservation)
Flows
=
v e v e
e f e f
of out   to in
) ( ) (
s
2
3
4
5
6
7
t
15
5
30
15
10
8
15
9
6
10
10
10
15
4
4
4
0
0
0
0
0
0
0
4
4
0
4
0
0
0
Capacity
Flow
=  ? E w v w v e
w v f e f
) , ( : of out
) , ( : ) (  =  ? E v w w v e
v w f e f
) , ( : to in
) , ( : ) (
6
An s-t flow is a function  f: E ?´ that satisfies:
¦ For each e ? E: 0  £ f(e)  £ u(e) (capacity)
¦ For each v ? V – {s, t}: (conservation)
MAX FLOW:  find s-t flow that maximizes net flow out of the source.
Flows
s
2
3
4
5
6
7
t
15
5
30
15
10
8
15
9
6
10
10
10
15
4
4
4
0
0
0
0
0
0
0
4
4
0
4
0
Value = 4
=
s e
e f f
of out
) (
0
0
Capacity
Flow
=
v e v e
e f e f
of out   to in
) ( ) (
7
An s-t flow is a function  f: E ?´ that satisfies:
¦ For each e ? E: 0  £ f(e)  £ u(e) (capacity)
¦ For each v ? V – {s, t}: (conservation)
MAX FLOW:  find s-t flow that maximizes net flow out of the source.
Flows
s
2
3
4
5
6
7
t
15
5
30
15
10
8
15
9
6
10
10
10
15
4
4
10
6
6
11
11
1
10
3
8
8
0
4
0
Value = 24
0
0
Capacity
Flow
=
v e v e
e f e f
of out   to in
) ( ) (
8
An s-t flow is a function  f: E ?´ that satisfies:
¦ For each e ? E: 0  £ f(e)  £ u(e) (capacity)
¦ For each v ? V – {s, t}: (conservation)
MAX FLOW:  find s-t flow that maximizes net flow out of the source.
Flows
s
2
3
4
5
6
7
t
15
5
30
15
10
8
15
9
6
10
10
10
15
4
4
10
9
9
14
14
4
10
4
8
9
1
0
0
Value = 28
0
0
Capacity
Flow
=
v e v e
e f e f
of out   to in
) ( ) (
Page 3

Princeton University  •  COS 423  •  Theory of Algorithms  •  Spring 2001  •  Kevin Wayne
Maximum Flow
2
Contents
Contents.
¦ Maximum flow problem.
¦ Minimum cut problem.
¦ Max-flow min-cut theorem.
¦ Augmenting path algorithm.
¦ Capacity-scaling.
¦ Shortest augmenting path.
3
¦ Network reliability.
¦ Security of statistical data.
¦ Distributed computing.
¦ Egalitarian stable matching.
¦ Distributed computing.
¦ Many many more . . .
Maximum Flow and Minimum Cut
Max flow and min cut.
¦ Two very rich algorithmic problems.
¦ Cornerstone problem in combinatorial optimization.
¦ Beautiful mathematical duality.
Nontrivial applications / reductions.
¦ Network connectivity.
¦ Bipartite matching.
¦ Data mining.
¦ Open-pit mining.
¦ Airline scheduling.
¦ Image processing.
¦ Project selection.
¦ Baseball elimination.
4
Max flow network:  G = (V, E, s, t, u) .
¦ (V, E) = directed graph, no parallel arcs.
¦ Two distinguished nodes:  s = source, t = sink.
¦ u(e) = capacity of arc e.
Max Flow Network
Capacity
s
2
3
4
5
6
7
t
15
5
30
15
10
8
15
9
6
10
10
10
15
4
4
5
An s-t flow is a function  f: E ?´ that satisfies:
¦ For each e ? E: 0  £ f(e)  £ u(e) (capacity)
¦ For each v ? V – {s, t}: (conservation)
Flows
=
v e v e
e f e f
of out   to in
) ( ) (
s
2
3
4
5
6
7
t
15
5
30
15
10
8
15
9
6
10
10
10
15
4
4
4
0
0
0
0
0
0
0
4
4
0
4
0
0
0
Capacity
Flow
=  ? E w v w v e
w v f e f
) , ( : of out
) , ( : ) (  =  ? E v w w v e
v w f e f
) , ( : to in
) , ( : ) (
6
An s-t flow is a function  f: E ?´ that satisfies:
¦ For each e ? E: 0  £ f(e)  £ u(e) (capacity)
¦ For each v ? V – {s, t}: (conservation)
MAX FLOW:  find s-t flow that maximizes net flow out of the source.
Flows
s
2
3
4
5
6
7
t
15
5
30
15
10
8
15
9
6
10
10
10
15
4
4
4
0
0
0
0
0
0
0
4
4
0
4
0
Value = 4
=
s e
e f f
of out
) (
0
0
Capacity
Flow
=
v e v e
e f e f
of out   to in
) ( ) (
7
An s-t flow is a function  f: E ?´ that satisfies:
¦ For each e ? E: 0  £ f(e)  £ u(e) (capacity)
¦ For each v ? V – {s, t}: (conservation)
MAX FLOW:  find s-t flow that maximizes net flow out of the source.
Flows
s
2
3
4
5
6
7
t
15
5
30
15
10
8
15
9
6
10
10
10
15
4
4
10
6
6
11
11
1
10
3
8
8
0
4
0
Value = 24
0
0
Capacity
Flow
=
v e v e
e f e f
of out   to in
) ( ) (
8
An s-t flow is a function  f: E ?´ that satisfies:
¦ For each e ? E: 0  £ f(e)  £ u(e) (capacity)
¦ For each v ? V – {s, t}: (conservation)
MAX FLOW:  find s-t flow that maximizes net flow out of the source.
Flows
s
2
3
4
5
6
7
t
15
5
30
15
10
8
15
9
6
10
10
10
15
4
4
10
9
9
14
14
4
10
4
8
9
1
0
0
Value = 28
0
0
Capacity
Flow
=
v e v e
e f e f
of out   to in
) ( ) (
9
Networks
communication
Network
telephone exchanges,
computers, satellites
Nodes Arcs
cables, fiber optics,
microwave relays
Flow
voice, video,
packets
circuits
gates, registers,
processors
wires current
mechanical joints rods, beams, springs heat, energy
hydraulic
reservoirs, pumping
stations, lakes
pipelines fluid, oil
financial stocks, currency transactions money
transportation
airports, rail yards,
street intersections
highways, railbeds,
airway routes
freight,
vehicles,
passengers
chemical sites bonds energy
10
An s-t cut is a node partition (S, T) such that s ? S, t ? T.
¦ The capacity of an s-t cut (S, T) is:
Min s-t cut:  find an s-t cut of minimum capacity.
Cuts
? ? ? =
T w S v
E w v S e
w v u e u
,
) , ( of out
). , ( : ) (
s
2
3
4
5
6
7
t
15
5
30
15
10
8
15
9
6
10
10
10
15
4
4
Capacity = 30
11
An s-t cut is a node partition (S, T) such that s ? S, t ? T.
¦ The capacity of an s-t cut (S, T) is:
Min s-t cut:  find an s-t cut of minimum capacity.
Cuts
s
2
3
4
5
6
7
t
15
5
30
15
10
8
15
9
6
10
10
10
15
4
4
Capacity = 62
? ? ? =
T w S v
E w v S e
w v u e u
,
) , ( of out
). , ( : ) (
12
An s-t cut is a node partition (S, T) such that s ? S, t ? T.
¦ The capacity of an s-t cut (S, T) is:
Min s-t cut:  find an s-t cut of minimum capacity.
Cuts
s
2
3
4
5
6
7
t
15
5
30
15
10
8
15
9
6
10
10
10
15
4
4
Capacity = 28
? ? ? =
T w S v
E w v S e
w v u e u
,
) , ( of out
). , ( : ) (
Page 4

Princeton University  •  COS 423  •  Theory of Algorithms  •  Spring 2001  •  Kevin Wayne
Maximum Flow
2
Contents
Contents.
¦ Maximum flow problem.
¦ Minimum cut problem.
¦ Max-flow min-cut theorem.
¦ Augmenting path algorithm.
¦ Capacity-scaling.
¦ Shortest augmenting path.
3
¦ Network reliability.
¦ Security of statistical data.
¦ Distributed computing.
¦ Egalitarian stable matching.
¦ Distributed computing.
¦ Many many more . . .
Maximum Flow and Minimum Cut
Max flow and min cut.
¦ Two very rich algorithmic problems.
¦ Cornerstone problem in combinatorial optimization.
¦ Beautiful mathematical duality.
Nontrivial applications / reductions.
¦ Network connectivity.
¦ Bipartite matching.
¦ Data mining.
¦ Open-pit mining.
¦ Airline scheduling.
¦ Image processing.
¦ Project selection.
¦ Baseball elimination.
4
Max flow network:  G = (V, E, s, t, u) .
¦ (V, E) = directed graph, no parallel arcs.
¦ Two distinguished nodes:  s = source, t = sink.
¦ u(e) = capacity of arc e.
Max Flow Network
Capacity
s
2
3
4
5
6
7
t
15
5
30
15
10
8
15
9
6
10
10
10
15
4
4
5
An s-t flow is a function  f: E ?´ that satisfies:
¦ For each e ? E: 0  £ f(e)  £ u(e) (capacity)
¦ For each v ? V – {s, t}: (conservation)
Flows
=
v e v e
e f e f
of out   to in
) ( ) (
s
2
3
4
5
6
7
t
15
5
30
15
10
8
15
9
6
10
10
10
15
4
4
4
0
0
0
0
0
0
0
4
4
0
4
0
0
0
Capacity
Flow
=  ? E w v w v e
w v f e f
) , ( : of out
) , ( : ) (  =  ? E v w w v e
v w f e f
) , ( : to in
) , ( : ) (
6
An s-t flow is a function  f: E ?´ that satisfies:
¦ For each e ? E: 0  £ f(e)  £ u(e) (capacity)
¦ For each v ? V – {s, t}: (conservation)
MAX FLOW:  find s-t flow that maximizes net flow out of the source.
Flows
s
2
3
4
5
6
7
t
15
5
30
15
10
8
15
9
6
10
10
10
15
4
4
4
0
0
0
0
0
0
0
4
4
0
4
0
Value = 4
=
s e
e f f
of out
) (
0
0
Capacity
Flow
=
v e v e
e f e f
of out   to in
) ( ) (
7
An s-t flow is a function  f: E ?´ that satisfies:
¦ For each e ? E: 0  £ f(e)  £ u(e) (capacity)
¦ For each v ? V – {s, t}: (conservation)
MAX FLOW:  find s-t flow that maximizes net flow out of the source.
Flows
s
2
3
4
5
6
7
t
15
5
30
15
10
8
15
9
6
10
10
10
15
4
4
10
6
6
11
11
1
10
3
8
8
0
4
0
Value = 24
0
0
Capacity
Flow
=
v e v e
e f e f
of out   to in
) ( ) (
8
An s-t flow is a function  f: E ?´ that satisfies:
¦ For each e ? E: 0  £ f(e)  £ u(e) (capacity)
¦ For each v ? V – {s, t}: (conservation)
MAX FLOW:  find s-t flow that maximizes net flow out of the source.
Flows
s
2
3
4
5
6
7
t
15
5
30
15
10
8
15
9
6
10
10
10
15
4
4
10
9
9
14
14
4
10
4
8
9
1
0
0
Value = 28
0
0
Capacity
Flow
=
v e v e
e f e f
of out   to in
) ( ) (
9
Networks
communication
Network
telephone exchanges,
computers, satellites
Nodes Arcs
cables, fiber optics,
microwave relays
Flow
voice, video,
packets
circuits
gates, registers,
processors
wires current
mechanical joints rods, beams, springs heat, energy
hydraulic
reservoirs, pumping
stations, lakes
pipelines fluid, oil
financial stocks, currency transactions money
transportation
airports, rail yards,
street intersections
highways, railbeds,
airway routes
freight,
vehicles,
passengers
chemical sites bonds energy
10
An s-t cut is a node partition (S, T) such that s ? S, t ? T.
¦ The capacity of an s-t cut (S, T) is:
Min s-t cut:  find an s-t cut of minimum capacity.
Cuts
? ? ? =
T w S v
E w v S e
w v u e u
,
) , ( of out
). , ( : ) (
s
2
3
4
5
6
7
t
15
5
30
15
10
8
15
9
6
10
10
10
15
4
4
Capacity = 30
11
An s-t cut is a node partition (S, T) such that s ? S, t ? T.
¦ The capacity of an s-t cut (S, T) is:
Min s-t cut:  find an s-t cut of minimum capacity.
Cuts
s
2
3
4
5
6
7
t
15
5
30
15
10
8
15
9
6
10
10
10
15
4
4
Capacity = 62
? ? ? =
T w S v
E w v S e
w v u e u
,
) , ( of out
). , ( : ) (
12
An s-t cut is a node partition (S, T) such that s ? S, t ? T.
¦ The capacity of an s-t cut (S, T) is:
Min s-t cut:  find an s-t cut of minimum capacity.
Cuts
s
2
3
4
5
6
7
t
15
5
30
15
10
8
15
9
6
10
10
10
15
4
4
Capacity = 28
? ? ? =
T w S v
E w v S e
w v u e u
,
) , ( of out
). , ( : ) (
13
L1.  Let f be a flow, and let (S, T) be a cut.  Then, the net flow sent
across the cut is equal to the amount reaching t.
Flows and Cuts
s
2
3
4
5
6
7
t
15
5
30
15
10
8
15
9
6
10
10
10
15
4
4
f e f e f e f
s e S e S e
= = -    of out   to in  of out
) ( ) ( ) (
Value = 24
10
6
6
10
10
0
10
4
8
8
0
4
0
0
0
14
10
6
6
10
10
0
10
4
8
8
0
4
0
0
0
L1.  Let f be a flow, and let (S, T) be a cut.  Then, the net flow sent
across the cut is equal to the amount reaching t.
Flows and Cuts
s
2
3
4
5
6
7
t
15
5
30
15
10
8
15
9
6
10
10
10
15
4
4
f e f e f e f
s e S e S e
= = -    of out   to in  of out
) ( ) ( ) (
Value = 24
15
10
6
6
10
10
0
10
4
8
8
0
4
0
0
L1. Let f be a flow, and let (S, T) be a cut.  Then, the net flow sent
across the cut is equal to the amount reaching t.
Flows and Cuts
s
2
3
4
5
6
7
t
15
5
30
15
10
8
15
9
6
10
10
10
15
4
4
f e f e f e f
s e S e S e
= = -    of out   to in  of out
) ( ) ( ) (
Value = 24
0
16
Let f be a flow, and let (S, T) be a cut.  Then,
Proof by induction on |S|.
¦ Base case:  S = { s }.
¦ Inductive hypothesis:  assume true for |S| < k.
– consider cut (S, T) with |S| = k
– S = S’  ¨ { v } for some v „ s, t,  |S’ | = k-1  cap(S’, T’) = | f |.
– adding v to S’ increase cut capacity by
Flows and Cuts
. ) ( ) (
to in of out
= - S e S e
f e f e f
0 ) ( ) (
to in  of out
= -   v e v e
e f e f
s
v
t
After
s
v
t
S’ Before
S
Page 5

Princeton University  •  COS 423  •  Theory of Algorithms  •  Spring 2001  •  Kevin Wayne
Maximum Flow
2
Contents
Contents.
¦ Maximum flow problem.
¦ Minimum cut problem.
¦ Max-flow min-cut theorem.
¦ Augmenting path algorithm.
¦ Capacity-scaling.
¦ Shortest augmenting path.
3
¦ Network reliability.
¦ Security of statistical data.
¦ Distributed computing.
¦ Egalitarian stable matching.
¦ Distributed computing.
¦ Many many more . . .
Maximum Flow and Minimum Cut
Max flow and min cut.
¦ Two very rich algorithmic problems.
¦ Cornerstone problem in combinatorial optimization.
¦ Beautiful mathematical duality.
Nontrivial applications / reductions.
¦ Network connectivity.
¦ Bipartite matching.
¦ Data mining.
¦ Open-pit mining.
¦ Airline scheduling.
¦ Image processing.
¦ Project selection.
¦ Baseball elimination.
4
Max flow network:  G = (V, E, s, t, u) .
¦ (V, E) = directed graph, no parallel arcs.
¦ Two distinguished nodes:  s = source, t = sink.
¦ u(e) = capacity of arc e.
Max Flow Network
Capacity
s
2
3
4
5
6
7
t
15
5
30
15
10
8
15
9
6
10
10
10
15
4
4
5
An s-t flow is a function  f: E ?´ that satisfies:
¦ For each e ? E: 0  £ f(e)  £ u(e) (capacity)
¦ For each v ? V – {s, t}: (conservation)
Flows
=
v e v e
e f e f
of out   to in
) ( ) (
s
2
3
4
5
6
7
t
15
5
30
15
10
8
15
9
6
10
10
10
15
4
4
4
0
0
0
0
0
0
0
4
4
0
4
0
0
0
Capacity
Flow
=  ? E w v w v e
w v f e f
) , ( : of out
) , ( : ) (  =  ? E v w w v e
v w f e f
) , ( : to in
) , ( : ) (
6
An s-t flow is a function  f: E ?´ that satisfies:
¦ For each e ? E: 0  £ f(e)  £ u(e) (capacity)
¦ For each v ? V – {s, t}: (conservation)
MAX FLOW:  find s-t flow that maximizes net flow out of the source.
Flows
s
2
3
4
5
6
7
t
15
5
30
15
10
8
15
9
6
10
10
10
15
4
4
4
0
0
0
0
0
0
0
4
4
0
4
0
Value = 4
=
s e
e f f
of out
) (
0
0
Capacity
Flow
=
v e v e
e f e f
of out   to in
) ( ) (
7
An s-t flow is a function  f: E ?´ that satisfies:
¦ For each e ? E: 0  £ f(e)  £ u(e) (capacity)
¦ For each v ? V – {s, t}: (conservation)
MAX FLOW:  find s-t flow that maximizes net flow out of the source.
Flows
s
2
3
4
5
6
7
t
15
5
30
15
10
8
15
9
6
10
10
10
15
4
4
10
6
6
11
11
1
10
3
8
8
0
4
0
Value = 24
0
0
Capacity
Flow
=
v e v e
e f e f
of out   to in
) ( ) (
8
An s-t flow is a function  f: E ?´ that satisfies:
¦ For each e ? E: 0  £ f(e)  £ u(e) (capacity)
¦ For each v ? V – {s, t}: (conservation)
MAX FLOW:  find s-t flow that maximizes net flow out of the source.
Flows
s
2
3
4
5
6
7
t
15
5
30
15
10
8
15
9
6
10
10
10
15
4
4
10
9
9
14
14
4
10
4
8
9
1
0
0
Value = 28
0
0
Capacity
Flow
=
v e v e
e f e f
of out   to in
) ( ) (
9
Networks
communication
Network
telephone exchanges,
computers, satellites
Nodes Arcs
cables, fiber optics,
microwave relays
Flow
voice, video,
packets
circuits
gates, registers,
processors
wires current
mechanical joints rods, beams, springs heat, energy
hydraulic
reservoirs, pumping
stations, lakes
pipelines fluid, oil
financial stocks, currency transactions money
transportation
airports, rail yards,
street intersections
highways, railbeds,
airway routes
freight,
vehicles,
passengers
chemical sites bonds energy
10
An s-t cut is a node partition (S, T) such that s ? S, t ? T.
¦ The capacity of an s-t cut (S, T) is:
Min s-t cut:  find an s-t cut of minimum capacity.
Cuts
? ? ? =
T w S v
E w v S e
w v u e u
,
) , ( of out
). , ( : ) (
s
2
3
4
5
6
7
t
15
5
30
15
10
8
15
9
6
10
10
10
15
4
4
Capacity = 30
11
An s-t cut is a node partition (S, T) such that s ? S, t ? T.
¦ The capacity of an s-t cut (S, T) is:
Min s-t cut:  find an s-t cut of minimum capacity.
Cuts
s
2
3
4
5
6
7
t
15
5
30
15
10
8
15
9
6
10
10
10
15
4
4
Capacity = 62
? ? ? =
T w S v
E w v S e
w v u e u
,
) , ( of out
). , ( : ) (
12
An s-t cut is a node partition (S, T) such that s ? S, t ? T.
¦ The capacity of an s-t cut (S, T) is:
Min s-t cut:  find an s-t cut of minimum capacity.
Cuts
s
2
3
4
5
6
7
t
15
5
30
15
10
8
15
9
6
10
10
10
15
4
4
Capacity = 28
? ? ? =
T w S v
E w v S e
w v u e u
,
) , ( of out
). , ( : ) (
13
L1.  Let f be a flow, and let (S, T) be a cut.  Then, the net flow sent
across the cut is equal to the amount reaching t.
Flows and Cuts
s
2
3
4
5
6
7
t
15
5
30
15
10
8
15
9
6
10
10
10
15
4
4
f e f e f e f
s e S e S e
= = -    of out   to in  of out
) ( ) ( ) (
Value = 24
10
6
6
10
10
0
10
4
8
8
0
4
0
0
0
14
10
6
6
10
10
0
10
4
8
8
0
4
0
0
0
L1.  Let f be a flow, and let (S, T) be a cut.  Then, the net flow sent
across the cut is equal to the amount reaching t.
Flows and Cuts
s
2
3
4
5
6
7
t
15
5
30
15
10
8
15
9
6
10
10
10
15
4
4
f e f e f e f
s e S e S e
= = -    of out   to in  of out
) ( ) ( ) (
Value = 24
15
10
6
6
10
10
0
10
4
8
8
0
4
0
0
L1. Let f be a flow, and let (S, T) be a cut.  Then, the net flow sent
across the cut is equal to the amount reaching t.
Flows and Cuts
s
2
3
4
5
6
7
t
15
5
30
15
10
8
15
9
6
10
10
10
15
4
4
f e f e f e f
s e S e S e
= = -    of out   to in  of out
) ( ) ( ) (
Value = 24
0
16
Let f be a flow, and let (S, T) be a cut.  Then,
Proof by induction on |S|.
¦ Base case:  S = { s }.
¦ Inductive hypothesis:  assume true for |S| < k.
– consider cut (S, T) with |S| = k
– S = S’  ¨ { v } for some v „ s, t,  |S’ | = k-1  cap(S’, T’) = | f |.
– adding v to S’ increase cut capacity by
Flows and Cuts
. ) ( ) (
to in of out
= - S e S e
f e f e f
0 ) ( ) (
to in  of out
= -   v e v e
e f e f
s
v
t
After
s
v
t
S’ Before
S
17
L2. Let f be a flow, and let (S, T) be a cut.  Then,  | f | £ cap(S, T).
Proof.
Corollary. Let f be a flow, and let (S, T) be a cut.  If |f| = cap(S, T), then
f is a max flow and (S, T) is a min cut.
Flows and Cuts
T) cap(S,
) (
) (
) ( ) (
of out
of out
to in  of out
=
£ £ - =
S e
S e
S e S e
e u
e f
e f e f f
s
t
S T
7
6
8
4
18
Max Flow and Min Cut
Corollary. Let f be a flow, and let (S, T) be a cut.  If |f| = cap(S, T), then
f is a max flow and (S, T) is a min cut.
s
2
3
4
5
6
7
t
15
5
30
15
10
8
15
9
6
10
10
10
15
4
4
10
9
9
15
15
4
10
4
8
9
1
0
0
Flow value = 28
0
0
Cut capacity = 28
19
Max-Flow Min-Cut Theorem
MAX-FLOW MIN-CUT THEOREM (Ford-Fulkerson, 1956): In any
network, the value of the max flow is equal to the value of the min cut.
¦ "Good characterization."
¦ Proof IOU.
s
2
3
4
5
6
7
t
15
5
30
15
10
8
15
9
6
10
10
10
15
4
4
10
9
9
15
15
4
10
4
8
9
1
0
0
Flow value = 28
0
0
Cut capacity = 28
20
Towards an Algorithm
Find an s-t path where each arc has u(e) > f(e) and "augment" flow
along the path.
s
4
2
5
3 t
4
0
0
0
0
0
0
4
0
4
4
Flow value = 0
10 13 10
Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!