Courses

# Maximum Flow Applications Notes | EduRev

## : Maximum Flow Applications Notes | EduRev

``` Page 1

Princeton University  •  COS 423  •  Theory of Algorithms  •  Spring 2001  •  Kevin Wayne
Maximum Flow Applications
2
Maximum Flow Applications Contents
Max flow extensions and applications.
¦ Disjoint paths and network connectivity.
¦ Bipartite matchings.
¦ Circulations with upper and lower bounds.
¦ Census tabulation (matrix rounding).
¦ Airline scheduling.
¦ Image segmentation.
¦ Project selection (max weight closure).
¦ Baseball elimination.
3
Disjoint path network:  G = (V, E, s, t).
¦ Directed graph (V, E), source s, sink t.
¦ Two paths are edge-disjoint if they have no arc in common.
Disjoint path problem: find max number of edge-disjoint s-t paths.
¦ Application:  communication networks.
s
2
3
4
Disjoint Paths
5
6
7
t
4
Disjoint path network:  G = (V, E, s, t).
¦ Directed graph (V, E), source s, sink t.
¦ Two paths are edge-disjoint if they have no arc in common.
Disjoint path problem: find max number of edge-disjoint s-t paths.
s
2
3
4
Disjoint Paths
5
6
7
t
Page 2

Princeton University  •  COS 423  •  Theory of Algorithms  •  Spring 2001  •  Kevin Wayne
Maximum Flow Applications
2
Maximum Flow Applications Contents
Max flow extensions and applications.
¦ Disjoint paths and network connectivity.
¦ Bipartite matchings.
¦ Circulations with upper and lower bounds.
¦ Census tabulation (matrix rounding).
¦ Airline scheduling.
¦ Image segmentation.
¦ Project selection (max weight closure).
¦ Baseball elimination.
3
Disjoint path network:  G = (V, E, s, t).
¦ Directed graph (V, E), source s, sink t.
¦ Two paths are edge-disjoint if they have no arc in common.
Disjoint path problem: find max number of edge-disjoint s-t paths.
¦ Application:  communication networks.
s
2
3
4
Disjoint Paths
5
6
7
t
4
Disjoint path network:  G = (V, E, s, t).
¦ Directed graph (V, E), source s, sink t.
¦ Two paths are edge-disjoint if they have no arc in common.
Disjoint path problem: find max number of edge-disjoint s-t paths.
s
2
3
4
Disjoint Paths
5
6
7
t
5
Max flow formulation: assign unit capacity to every edge.
Theorem. There are k edge-disjoint paths from s to t if and only if the
max flow value is k.
Proof.  ¦ Suppose there are k edge-disjoint paths P
1
, . . . , P
k
.
¦ Set f(e) = 1 if e participates in some path P
i
;  otherwise, set f(e) = 0.
¦ Since paths are edge-disjoint, f is a flow of value k.
Disjoint Paths
s t
1
1
1
1
1
1
1
1
1
1
1
1
1
1
6
Max flow formulation: assign unit capacity to every edge.
Theorem. There are k edge-disjoint paths from s to t if and only if the
max flow value is k.
Proof.   ¦ Suppose max flow value is k.  By integrality theorem, there exists
{0, 1} flow f of value k.
¦ Consider edge (s,v) with f(s,v) = 1.
– by conservation, there exists an arc (v,w) with f(v,w) = 1
– continue until reach t, always choosing a new edge
¦ Produces k (not necessarily simple) edge-disjoint paths.
Disjoint Paths
s t
1
1
1
1
1
1
1
1
1
1
1
1
1
1
7
Network connectivity network:  G = (V, E, s, t) .
¦ Directed graph (V, E), source s, sink t.
¦ A set of edges F ? E disconnects t from s if all s-t paths uses at
least on edge in F.
Network connectivity: find min number of edges whose removal
disconnects t from s.
Network Connectivity
s
2
3
4
5
6
7
t
8
Network connectivity network:  G = (V, E, s, t) .
¦ Directed graph (V, E), source s, sink t.
¦ A set of edges F ? E disconnects t from s if all s-t paths uses at
least on edge in F.
Network connectivity: find min number of edges whose removal
disconnects t from s.
Network Connectivity
s
2
3
4
5
6
7
t
Page 3

Princeton University  •  COS 423  •  Theory of Algorithms  •  Spring 2001  •  Kevin Wayne
Maximum Flow Applications
2
Maximum Flow Applications Contents
Max flow extensions and applications.
¦ Disjoint paths and network connectivity.
¦ Bipartite matchings.
¦ Circulations with upper and lower bounds.
¦ Census tabulation (matrix rounding).
¦ Airline scheduling.
¦ Image segmentation.
¦ Project selection (max weight closure).
¦ Baseball elimination.
3
Disjoint path network:  G = (V, E, s, t).
¦ Directed graph (V, E), source s, sink t.
¦ Two paths are edge-disjoint if they have no arc in common.
Disjoint path problem: find max number of edge-disjoint s-t paths.
¦ Application:  communication networks.
s
2
3
4
Disjoint Paths
5
6
7
t
4
Disjoint path network:  G = (V, E, s, t).
¦ Directed graph (V, E), source s, sink t.
¦ Two paths are edge-disjoint if they have no arc in common.
Disjoint path problem: find max number of edge-disjoint s-t paths.
s
2
3
4
Disjoint Paths
5
6
7
t
5
Max flow formulation: assign unit capacity to every edge.
Theorem. There are k edge-disjoint paths from s to t if and only if the
max flow value is k.
Proof.  ¦ Suppose there are k edge-disjoint paths P
1
, . . . , P
k
.
¦ Set f(e) = 1 if e participates in some path P
i
;  otherwise, set f(e) = 0.
¦ Since paths are edge-disjoint, f is a flow of value k.
Disjoint Paths
s t
1
1
1
1
1
1
1
1
1
1
1
1
1
1
6
Max flow formulation: assign unit capacity to every edge.
Theorem. There are k edge-disjoint paths from s to t if and only if the
max flow value is k.
Proof.   ¦ Suppose max flow value is k.  By integrality theorem, there exists
{0, 1} flow f of value k.
¦ Consider edge (s,v) with f(s,v) = 1.
– by conservation, there exists an arc (v,w) with f(v,w) = 1
– continue until reach t, always choosing a new edge
¦ Produces k (not necessarily simple) edge-disjoint paths.
Disjoint Paths
s t
1
1
1
1
1
1
1
1
1
1
1
1
1
1
7
Network connectivity network:  G = (V, E, s, t) .
¦ Directed graph (V, E), source s, sink t.
¦ A set of edges F ? E disconnects t from s if all s-t paths uses at
least on edge in F.
Network connectivity: find min number of edges whose removal
disconnects t from s.
Network Connectivity
s
2
3
4
5
6
7
t
8
Network connectivity network:  G = (V, E, s, t) .
¦ Directed graph (V, E), source s, sink t.
¦ A set of edges F ? E disconnects t from s if all s-t paths uses at
least on edge in F.
Network connectivity: find min number of edges whose removal
disconnects t from s.
Network Connectivity
s
2
3
4
5
6
7
t
9
Disjoint Paths and Network Connectivity
Menger’s Theorem (1927). The max number of edge-disjoint s-t paths is
equal to the min number of arcs whose removal disconnects t from s.
s
2
3
4
5
6
7
t s
2
3
4
5
6
7
t
10
Disjoint Paths and Network Connectivity
Menger’s Theorem (1927). The max number of edge-disjoint s-t paths is
equal to the min number of arcs whose removal disconnects t from s.
Proof.   ¦ Suppose the removal of F ? E disconnects t from s, and |F| = k.
¦ All s-t paths use at least one edge of F. Hence, the number of edge-
disjoint paths is at most k.
s
2
3
4
5
6
7
t s
2
3
4
5
6
7
t
11
s
2
3
4
5
6
7
t s
2
3
4
5
6
7
t
Disjoint Paths and Network Connectivity
Menger’s Theorem (1927). The max number of edge-disjoint s-t paths is
equal to the min number of arcs whose removal disconnects t from s.
Proof.   ¦ Suppose max number of edge-disjoint paths is k.
¦ Then max flow value is k.
¦ Max-flow min-cut   cut (S, T) of capacity k.
¦ Let F be set of edges going from S to T.
¦ |F| = k, and definition of cut implies F disconnects t from s.
12
Matching.
¦ Input:  undirected graph G = (V, E).
¦ M ? E is a matching if each node appears in at most edge in M.
¦ Max matching:  find a max cardinality matching.
Matching
Page 4

Princeton University  •  COS 423  •  Theory of Algorithms  •  Spring 2001  •  Kevin Wayne
Maximum Flow Applications
2
Maximum Flow Applications Contents
Max flow extensions and applications.
¦ Disjoint paths and network connectivity.
¦ Bipartite matchings.
¦ Circulations with upper and lower bounds.
¦ Census tabulation (matrix rounding).
¦ Airline scheduling.
¦ Image segmentation.
¦ Project selection (max weight closure).
¦ Baseball elimination.
3
Disjoint path network:  G = (V, E, s, t).
¦ Directed graph (V, E), source s, sink t.
¦ Two paths are edge-disjoint if they have no arc in common.
Disjoint path problem: find max number of edge-disjoint s-t paths.
¦ Application:  communication networks.
s
2
3
4
Disjoint Paths
5
6
7
t
4
Disjoint path network:  G = (V, E, s, t).
¦ Directed graph (V, E), source s, sink t.
¦ Two paths are edge-disjoint if they have no arc in common.
Disjoint path problem: find max number of edge-disjoint s-t paths.
s
2
3
4
Disjoint Paths
5
6
7
t
5
Max flow formulation: assign unit capacity to every edge.
Theorem. There are k edge-disjoint paths from s to t if and only if the
max flow value is k.
Proof.  ¦ Suppose there are k edge-disjoint paths P
1
, . . . , P
k
.
¦ Set f(e) = 1 if e participates in some path P
i
;  otherwise, set f(e) = 0.
¦ Since paths are edge-disjoint, f is a flow of value k.
Disjoint Paths
s t
1
1
1
1
1
1
1
1
1
1
1
1
1
1
6
Max flow formulation: assign unit capacity to every edge.
Theorem. There are k edge-disjoint paths from s to t if and only if the
max flow value is k.
Proof.   ¦ Suppose max flow value is k.  By integrality theorem, there exists
{0, 1} flow f of value k.
¦ Consider edge (s,v) with f(s,v) = 1.
– by conservation, there exists an arc (v,w) with f(v,w) = 1
– continue until reach t, always choosing a new edge
¦ Produces k (not necessarily simple) edge-disjoint paths.
Disjoint Paths
s t
1
1
1
1
1
1
1
1
1
1
1
1
1
1
7
Network connectivity network:  G = (V, E, s, t) .
¦ Directed graph (V, E), source s, sink t.
¦ A set of edges F ? E disconnects t from s if all s-t paths uses at
least on edge in F.
Network connectivity: find min number of edges whose removal
disconnects t from s.
Network Connectivity
s
2
3
4
5
6
7
t
8
Network connectivity network:  G = (V, E, s, t) .
¦ Directed graph (V, E), source s, sink t.
¦ A set of edges F ? E disconnects t from s if all s-t paths uses at
least on edge in F.
Network connectivity: find min number of edges whose removal
disconnects t from s.
Network Connectivity
s
2
3
4
5
6
7
t
9
Disjoint Paths and Network Connectivity
Menger’s Theorem (1927). The max number of edge-disjoint s-t paths is
equal to the min number of arcs whose removal disconnects t from s.
s
2
3
4
5
6
7
t s
2
3
4
5
6
7
t
10
Disjoint Paths and Network Connectivity
Menger’s Theorem (1927). The max number of edge-disjoint s-t paths is
equal to the min number of arcs whose removal disconnects t from s.
Proof.   ¦ Suppose the removal of F ? E disconnects t from s, and |F| = k.
¦ All s-t paths use at least one edge of F. Hence, the number of edge-
disjoint paths is at most k.
s
2
3
4
5
6
7
t s
2
3
4
5
6
7
t
11
s
2
3
4
5
6
7
t s
2
3
4
5
6
7
t
Disjoint Paths and Network Connectivity
Menger’s Theorem (1927). The max number of edge-disjoint s-t paths is
equal to the min number of arcs whose removal disconnects t from s.
Proof.   ¦ Suppose max number of edge-disjoint paths is k.
¦ Then max flow value is k.
¦ Max-flow min-cut   cut (S, T) of capacity k.
¦ Let F be set of edges going from S to T.
¦ |F| = k, and definition of cut implies F disconnects t from s.
12
Matching.
¦ Input:  undirected graph G = (V, E).
¦ M ? E is a matching if each node appears in at most edge in M.
¦ Max matching:  find a max cardinality matching.
Matching
13
Bipartite Matching
Bipartite matching.
¦ Input:  undirected, bipartite graph G = (L ¨ R, E).
¦ M ? E is a matching if each node appears in at most edge in M.
¦ Max matching:  find a max cardinality matching.
1
3
5
1’
3’
5’
2
4
2’
4’
Matching
1-2’, 3-1’, 4-5’
R L
14
Bipartite Matching
Bipartite matching.
¦ Input:  undirected, bipartite graph G = (L ¨ R, E).
¦ M ? E is a matching if each node appears in at most edge in M.
¦ Max matching:  find a max cardinality matching.
1
3
5
1’
3’
5’
2
4
2’
4’
Matching
1-1’, 2-2’, 3-3’, 4-4’
R L
15
Max flow formulation.
¦ Create directed graph G’ = (L ¨ R ¨ {s, t},  E’ ).
¦ Direct all arcs from L to R, and give infinite (or unit) capacity.
¦ Add source s, and unit capacity arcs from s to each node in L.
¦ Add sink t, and unit capacity arcs from each node in R to t.
Bipartite Matching
s
1
3
5
1’
3’
5’
t
2
4
2’
4’
1
1
¥ R L
16
Claim. Matching in G of cardinality k induces flow in G’ of value k.
¦ Given matching M = { 1 - 2’, 3 - 1’, 4 - 5’ } of cardinality 3.
¦ Consider flow that sends 1 unit along each of 3 paths:
s -1 -2’ -t, s -3 -1’ -t, s -4 -5’ -t.
¦ f is a flow, and has cardinality 3.
Bipartite Matching:  Proof of Correctness
s
1
3
5
1’
3’
5’
t
2
4
2’
4’
1 1
¥ 1
3
5
1’
3’
5’
2
4
2’
4’
Page 5

Princeton University  •  COS 423  •  Theory of Algorithms  •  Spring 2001  •  Kevin Wayne
Maximum Flow Applications
2
Maximum Flow Applications Contents
Max flow extensions and applications.
¦ Disjoint paths and network connectivity.
¦ Bipartite matchings.
¦ Circulations with upper and lower bounds.
¦ Census tabulation (matrix rounding).
¦ Airline scheduling.
¦ Image segmentation.
¦ Project selection (max weight closure).
¦ Baseball elimination.
3
Disjoint path network:  G = (V, E, s, t).
¦ Directed graph (V, E), source s, sink t.
¦ Two paths are edge-disjoint if they have no arc in common.
Disjoint path problem: find max number of edge-disjoint s-t paths.
¦ Application:  communication networks.
s
2
3
4
Disjoint Paths
5
6
7
t
4
Disjoint path network:  G = (V, E, s, t).
¦ Directed graph (V, E), source s, sink t.
¦ Two paths are edge-disjoint if they have no arc in common.
Disjoint path problem: find max number of edge-disjoint s-t paths.
s
2
3
4
Disjoint Paths
5
6
7
t
5
Max flow formulation: assign unit capacity to every edge.
Theorem. There are k edge-disjoint paths from s to t if and only if the
max flow value is k.
Proof.  ¦ Suppose there are k edge-disjoint paths P
1
, . . . , P
k
.
¦ Set f(e) = 1 if e participates in some path P
i
;  otherwise, set f(e) = 0.
¦ Since paths are edge-disjoint, f is a flow of value k.
Disjoint Paths
s t
1
1
1
1
1
1
1
1
1
1
1
1
1
1
6
Max flow formulation: assign unit capacity to every edge.
Theorem. There are k edge-disjoint paths from s to t if and only if the
max flow value is k.
Proof.   ¦ Suppose max flow value is k.  By integrality theorem, there exists
{0, 1} flow f of value k.
¦ Consider edge (s,v) with f(s,v) = 1.
– by conservation, there exists an arc (v,w) with f(v,w) = 1
– continue until reach t, always choosing a new edge
¦ Produces k (not necessarily simple) edge-disjoint paths.
Disjoint Paths
s t
1
1
1
1
1
1
1
1
1
1
1
1
1
1
7
Network connectivity network:  G = (V, E, s, t) .
¦ Directed graph (V, E), source s, sink t.
¦ A set of edges F ? E disconnects t from s if all s-t paths uses at
least on edge in F.
Network connectivity: find min number of edges whose removal
disconnects t from s.
Network Connectivity
s
2
3
4
5
6
7
t
8
Network connectivity network:  G = (V, E, s, t) .
¦ Directed graph (V, E), source s, sink t.
¦ A set of edges F ? E disconnects t from s if all s-t paths uses at
least on edge in F.
Network connectivity: find min number of edges whose removal
disconnects t from s.
Network Connectivity
s
2
3
4
5
6
7
t
9
Disjoint Paths and Network Connectivity
Menger’s Theorem (1927). The max number of edge-disjoint s-t paths is
equal to the min number of arcs whose removal disconnects t from s.
s
2
3
4
5
6
7
t s
2
3
4
5
6
7
t
10
Disjoint Paths and Network Connectivity
Menger’s Theorem (1927). The max number of edge-disjoint s-t paths is
equal to the min number of arcs whose removal disconnects t from s.
Proof.   ¦ Suppose the removal of F ? E disconnects t from s, and |F| = k.
¦ All s-t paths use at least one edge of F. Hence, the number of edge-
disjoint paths is at most k.
s
2
3
4
5
6
7
t s
2
3
4
5
6
7
t
11
s
2
3
4
5
6
7
t s
2
3
4
5
6
7
t
Disjoint Paths and Network Connectivity
Menger’s Theorem (1927). The max number of edge-disjoint s-t paths is
equal to the min number of arcs whose removal disconnects t from s.
Proof.   ¦ Suppose max number of edge-disjoint paths is k.
¦ Then max flow value is k.
¦ Max-flow min-cut   cut (S, T) of capacity k.
¦ Let F be set of edges going from S to T.
¦ |F| = k, and definition of cut implies F disconnects t from s.
12
Matching.
¦ Input:  undirected graph G = (V, E).
¦ M ? E is a matching if each node appears in at most edge in M.
¦ Max matching:  find a max cardinality matching.
Matching
13
Bipartite Matching
Bipartite matching.
¦ Input:  undirected, bipartite graph G = (L ¨ R, E).
¦ M ? E is a matching if each node appears in at most edge in M.
¦ Max matching:  find a max cardinality matching.
1
3
5
1’
3’
5’
2
4
2’
4’
Matching
1-2’, 3-1’, 4-5’
R L
14
Bipartite Matching
Bipartite matching.
¦ Input:  undirected, bipartite graph G = (L ¨ R, E).
¦ M ? E is a matching if each node appears in at most edge in M.
¦ Max matching:  find a max cardinality matching.
1
3
5
1’
3’
5’
2
4
2’
4’
Matching
1-1’, 2-2’, 3-3’, 4-4’
R L
15
Max flow formulation.
¦ Create directed graph G’ = (L ¨ R ¨ {s, t},  E’ ).
¦ Direct all arcs from L to R, and give infinite (or unit) capacity.
¦ Add source s, and unit capacity arcs from s to each node in L.
¦ Add sink t, and unit capacity arcs from each node in R to t.
Bipartite Matching
s
1
3
5
1’
3’
5’
t
2
4
2’
4’
1
1
¥ R L
16
Claim. Matching in G of cardinality k induces flow in G’ of value k.
¦ Given matching M = { 1 - 2’, 3 - 1’, 4 - 5’ } of cardinality 3.
¦ Consider flow that sends 1 unit along each of 3 paths:
s -1 -2’ -t, s -3 -1’ -t, s -4 -5’ -t.
¦ f is a flow, and has cardinality 3.
Bipartite Matching:  Proof of Correctness
s
1
3
5
1’
3’
5’
t
2
4
2’
4’
1 1
¥ 1
3
5
1’
3’
5’
2
4
2’
4’
17
Claim. Flow f of value k in G’ induces matching of cardinality k in G.
¦ By integrality theorem, there exists {0, 1}-valued flow f of value k.
¦ Consider M = set of edges from L to R with f(e) = 1.
– each node in L and R participates in at most one edge in M
– |M| = k:  consider cut (L ¨ s, R ¨ t)
Bipartite Matching:  Proof of Correctness
s
1
3
5
1’
3’
5’
t
2
4
2’
4’
1 1
¥ 1
3
5
1’
3’
5’
2
4
2’
4’
18
Perfect matching.
¦ Input:  undirected graph G = (V, E).
¦ A matching M ? E is perfect if each node appears in exactly one
edge in M.
Perfect bipartite matching.
¦ Input:  undirected, bipartite graph G = (L ¨ R, E),  |L| = |R| = n.
¦ Can determine if bipartite graph has perfect matching by running
matching algorithm.
Is there an easy way to convince someone that a bipartite graph does
not have a perfect matching?
¦ Need good characterization of such graphs.
Perfect Matching
19
Let X be a subset of nodes, and let N(X) be the set of nodes adjacent
to nodes in x.
Observation. If a bipartite graph G = (L ¨ R, E), has a perfect
matching, then |N(X)| ‡ |X| for every X ? L.
¦ Each node in X has to be matched to a different node in N(X).
Perfect Matching
1
3
5
1’
3’
5’
2
4
2’
4’
R L
No perfect matching:
X = {2, 4, 5}, N(X) = {2’, 5’}.
20
Hall’s Theorem. Let G = (L ¨ R, E) be a bipartite graph with |L| = |R|.
Then, either
¦ (i)  G either has a perfect matching, or
¦ (ii) There exists a subset X ? L such that |N(X)| < |X|.
Perfect Matching
1
3
5
1’
3’
5’
2
4
2’
4’
R L
```
Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!