§ Flows (TODO)
§ Canonical Transformation
- No self loops.
- No loops of the form
s -> u -> s. (ie, no 2-vertex loops).
- This allows us to conflate "positive flow" and "net flow".
§ Notation: Net flow / flow
- A flow on is a function such that for all vertices .
- Flow conservation : for all vertices , .
- anti-symmetry : .
§ Implicit summation notation
The value of a flow denoted as (cardinality of ), is denoted as:
§ Properties of flow
- . because self loops are not allowed. for two different vertices, we're going to get by skew symmetry. In general, .
- if .
Recall that . We want to show that .
So whatever gets pushed out gets pushed in.
A partition of the network into two parts, such that the source is in one
part and sink in the other. is a cut of a flow network is
a partition of such that . If is a flow on
then the flow across the cut is .
§ Capacity of a cut and its relationship to flow
See that we only get
positive coefficents here. There is no "negative capacity", only "negative flow".
§ Theorem: upper bound flow across a cut
Value of any flow is upeer bounded by the capacity of any cut. We need
more tools to prove this, as this is basically max-flow-min-cut
§ A different characterization of flow value
Lemma: for any flow and any cut we have that .
It's because we have the source on one side, and the sink on the other side.
That gives us the flow! Everything else cancels by conservation.
As does not contain , by flow conservation, we must have that .
Thus we get:
So, I can know the capacity of any cut bounds the flow of the network!
So if I go look at the min-cut, then I can bound the max flow. We don't know
how to find these min-cuts. That's what we'll need to figure out.
§ Residual network
Network that points us to locations with leftover capacity where we can
push flow. contains all those edges that have positive (greater than zero)
residual capacity. Edges in admit more flow. If , then
, but . So we will have extra edges in the
residual network that don't exist in the original network.
If I have a flow due to a back-edge with capacity , I can in fact
send more flow to make it ! So I can have "back edges" in the residual network
for edges whose flow has to shrink.
§ Augmenting path in
Sid question: A path from to in . Why does the existence of an augmenting path in actually mean that we can increase the flow? even when we have "back edges"? Sid answer : Because at the end of the day, we are picking a path from to which tells us how to change our flow in a way that we still respect capacity constraints.