Lecture22_NetworkFlows1
Wednesday, October 21, 2020 3:31 PM
Matching problem
Flow Networks
Definition. A flow network is a directed graph G = (V, E) with two distinguished vertices: a source s and a sink t. Each edge (u, v) ∈ E has a nonnegative capacity c(u, v). If (u, v) ∉ E, then c(u, v) = 0.
The flow goes into the vertex should equal to the flow goes out from that vertex
• The flow should not have any “leaks”
• The positive flow is not greater than the capacity
• Flow conservation: in == out
• Sink vertex doesn’t need to have flow conservation
• The nature of the problem: at some edges we are wasting our capacity
➢Find the maximum assignment
Maximum-flow problem: Given a flow network G, find a flow of maximum value on G.
➢The value of the maximum flow of the above graph is 4. Analysis of Algorithms Page 1
➢The value of the maximum flow of the above graph is 4. Flow cancellation
Notational simplification
Equivalence of definitions
• If given a network flow, can we create a flow that satisfies its two properties
Analysis of Algorithms Page 2
➢From summation notation to set notation
Simple properties of flow
• Whatever we send to the network should end up in the sink
Cuts
Definition. A cut (S, T) of a flow network G = (V, E) is a partition of V such that s ∈ S and t ∈ T. If f is a flow on G, then the flow across the cut is f (S, T).
• Split the graph to two side: source to one side, and sink to another side
Analysis of Algorithms Page 3
• Split the graph to two side: source to one side, and sink to another side
Another characterization of flow value
Lemma. For any flow f and any cut (S, T), we have | f | = f (S, T).
•T=v-s
Capacity of a cut
Definition. The capacity of a cut (S, T) is c(S, T).
Upper bound on the maximum flow value
Theorem. The value of any flow is bounded above by the capacity of any cut.
Residual network
Definition. Let f be a flow on G = (V, E). The residual network Gf (V, Ef ) is the graph with strictly positive residual capacities
cf (u,v)=c(u,v)–f(u,v)>0. Edges in Ef admit more flow.
Augmenting paths
Analysis of Algorithms Page 4
• Any path from source to sink found in the residual path.
• The graph above is not entire graph, therefore there are some node without
conservation int the network flow
Max-flow, min-cut theorem
Theorem. The following are equivalent: 1. f is a maximum flow.
2. f admits no augmenting paths. 3. |f|=c(S,T)forsomecut(S,T).
Analysis of Algorithms Page 5