§ Flows (TODO)

• Srinivas Devdas: Flows

§ 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 $G$ is a function $f: V \times V \rightarrow \mathbb R$ such that $f(u, v) \leq c(u, v)$ for all vertices $u, v$.
• Flow conservation : for all vertices $u$, $\sum_v f(u, v) = 0$.
• anti-symmetry : $f(u, v) = -f(v, u)$.

§ Implicit summation notation

The value of a flow $f$ denoted as $|f|$ (cardinality of $f$), is denoted as:

$$|f| \equiv f(s, V) = \sum_v f(s, v)$$

§ Properties of flow

• $f(X, X) = 0$. $f(a, a) = 0$ because self loops are not allowed. for two different vertices, we're going to get $f(a, b) + f(b, a) = 0$ by skew symmetry. In general, $f(X, Y) = -f(Y, X)$.
• $f(X \cup Y, Z) = f(X, Z) \cup f(Y, Z)$ if $X \cap Y = \emptyset$.

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

Recall that $|f| = f(s, V)$. We want to show that $|f| = f(s, V) = f(V, t)$. So whatever gets pushed out gets pushed in.

$$\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)$ is a cut of a flow network $G$ is a partition of $V$ such that $s \in S, t \in T$. If $f$ is a flow on $G$ then the flow across the cut is $f(S, T)$.

§ Capacity of a cut and its relationship to flow

$$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 $f$ and any cut $(S, T)$ we have that $|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.

$$\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 $S - s$ does not contain $t$, by flow conservation, we must have that $f(S - s, V) = 0$. Thus we get:

$$\begin{aligned} f(S, T) = f(s, V) = |f| \end{aligned}$$

So, I can know the capacity of any cut $(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. $G_f(V, E_f)$ contains all those edges that have positive (greater than zero) residual capacity. Edges in $E_f$ admit more flow. If $(v, u) \not \in E$, then $c(v, u) = 0$, but $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$ due to a back-edge with capacity $0$, I can in fact send more flow to make it $0$! So I can have "back edges" in the residual network for edges whose flow has to shrink.

§ Augmenting path in $G_f$

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