§ Flows (TODO)

§ Canonical Transformation

§ Notation: Net flow / flow

§ Implicit summation notation

The value of a flow ff denoted as f|f| (cardinality of ff), is denoted as:
ff(s,V)=vf(s,v) |f| \equiv f(s, V) = \sum_v f(s, v)

§ Properties of flow

§ Theorem: fequivf(s,V)=f(V,t)|f| equiv f(s, V) = f(V, t)

Recall that f=f(s,V)|f| = f(s, V). We want to show that f=f(s,V)=f(V,t)|f| = f(s, V) = f(V, t). So whatever gets pushed out gets pushed in.
ff(s,V)f(s,V)+f(Vs,V)=f(V,V)=0f(s,V)=f(Vs,V)f(s,V)=f(Vst,V)+f(t,V)f(s,V)=f(t,V)f(Vst,V)[any vertex in Vst is an intermediate vertex, which has 0 net flow]f(s,V)=f(t,V)0f(s,V)=f(t,V) \begin{aligned} &|f| \equiv f(s, V) \\ & f(s, V) + f(V - s, V) = f(V, V) = 0 \\ & f(s, V) = f(V - s, V) \\ & f(s, V) = f(V - s - t, V) + f(t, V) \\ & f(s, V) = f(t, V) - f(V - s - t, V)\\ & [\text{any vertex in $V - s - t$ is an intermediate vertex, which has 0 net flow}] \\ & f(s, V) = f(t, V) - 0 \\ & f(s, V) = f(t, V) \\ \end{aligned}

§ Cut:

A partition of the network into two parts, such that the source is in one part and sink in the other. (S,T)(S, T) is a cut of a flow network GG is a partition of VV such that sS,tTs \in S, t \in T. If ff is a flow on GG then the flow across the cut is f(S,T)f(S, T).

§ Capacity of a cut and its relationship to flow

c(S,T)=sS,tTc(s,t)c(S, T) = \sum_{s \in S, t \in T} c(s, t)
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 ff and any cut (S,T)(S, T) we have that f=f(S,T)|f| = f(S, T). 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.
f(S,T)=f(S,V)f(S,S)f(S,T)=f(S,V)0f(S,T)=f(s,V)+f(Ss,V) \begin{aligned} &f(S, T) = f(S, V) - f(S, S) \\ &f(S, T) = f(S, V) - 0 \\ &f(S, T) = f(s, V) + f(S - s, V) \\ \end{aligned}
As SsS - s does not contain tt, by flow conservation, we must have that f(Ss,V)=0f(S - s, V) = 0. Thus we get:
f(S,T)=f(s,V)=f \begin{aligned} f(S, T) = f(s, V) = |f| \end{aligned}
So, I can know the capacity of any cut (S,T)(S, T) 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. Gf(V,Ef)G_f(V, E_f) contains all those edges that have positive (greater than zero) residual capacity. Edges in EfE_f admit more flow. If (v,u)∉E(v, u) \not \in E, then c(v,u)=0c(v, u) = 0, but f(v,u)=f(u,v)f(v, u) = -f(u, v). So we will have extra edges in the residual network that don't exist in the original network. If I have a flow 1-1 due to a back-edge with capacity 00, I can in fact send more flow to make it 00! So I can have "back edges" in the residual network for edges whose flow has to shrink.

§ Augmenting path in GfG_f

Sid question: A path from ss to tt in GfG_f. Why does the existence of an augmenting path in GfG_f 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 ss to tt which tells us how to change our flow in a way that we still respect capacity constraints.