> [!definition|*] Flows > On a directed graph $G=(E,V)$, a **flow** $f$ is a function $V \to \mathbb{R}^{+}$. Except for a **source** $s$ and a **sink** $t$ ($s,t \in V$, $s \ne t$), any vertex has no net flow: $\sum_{y \in N_{-}(x)} f(\overrightarrow{yx})=\sum_{y \in N_{+}(x)}f(\overrightarrow{xy}),$where $N_{\pm}(x)$ are the neighbors of $x$ with edges going into/out from $x$. - Equivalently, $f:V^{2}\to \mathbb{R}^{+}$ where $f(x,y) :=: f(\overrightarrow{xy})$ if $\overrightarrow{xy} \in E(G)$ and $0$ otherwise. > [!theorem|*] Value of a Flow > The **value** of a feasible flow is the amount leaving $s$ and arriving at $t$, where the two must be equal: $v(f):= I_{f}(s)= -I_{f}(t).$ > > > [!proof]- > > Let $U=V-\{ s,t \}$ and sum over $U$: $\begin{align*} > 0 &= \sum_{x \in U} v(x)\\ > &= \sum_{x \in U} \left( \sum_{y \in U}f(\overrightarrow{xy}) - \sum_{y \in U}f(\overrightarrow{yx})+\sum_{y \in \{ s,t \}}f(\overrightarrow{xy}) - \sum_{y \in \{ s,t \}}f(\overrightarrow{yx}) \right) \\ > &= 0 + \sum_{x \in U} f(\overrightarrow{xs}) +\sum_{x \in U} f(\overrightarrow{xt}) - \sum_{x \in U} f(\overrightarrow{sx}) - \sum_{x \in U} f(\overrightarrow{tx}). > \end{align*}$Therefore, adding the extra flow between $s,t$: $I_{f}(s)=\sum_{x \in V} f(\overrightarrow{xs})-\sum_{x \in V} f(\overrightarrow{sx})=\sum_{x \in V} f(\overrightarrow{xt})-\sum_{x \in V} f(\overrightarrow{tx})=I_{f}(t).$ > ## Maximum Feasible Flows > [!definition|*] Capacity and Feasible Flows > A **(edge) capacity** function $c: E \to \mathbb{R}^{+}$ requires $\forall e \in E, c(e) \ge f(e)$ (i.e. there cannot be more flow in an edge than what its capacity allows). > > A flow that satisfies such requirement is called **feasible**. > [!lemma|*] Slack Paths Imply Non-Maximality > An edge $e=\overrightarrow{xy}$ is **slack** if $f(\overrightarrow{xy}) < c(\overrightarrow{xy})$ or $f(\overrightarrow{yx})>0$. A path is slack if all its edges are slack. > > If a flow $f$ has a slack path $(s=x_{0},x_{1},\dots,x_{k}= t)$, then it cannot be maximal in value. > > [!proof]- > > Suppose the path is $\epsilon$-slack, then we can change $f$ by increasing $f(x_{i},x_{i+1})$ by $\epsilon$ if $\overrightarrow{x_{i}x_{i+1}} \in E$, or decreasing $f(x_{i+1},x_{i})$ by $\epsilon$ if $\overrightarrow{x_{i+1}x_{i}} \in E$. > > > > This still gives a flow since for any $x_{i} \ne s,t$, the change in $I_{f}(x)$ cancel out, but the value is increased by $\epsilon$. > [!theorem|*] Max Flow Min Cut > On a directed graph $G=(V, E)$ with capacity function $c$, source $s$ and sink $t$, $\begin{align*} \sup \{ &v(f) ~|~ f \text{ is feasible}\}\\ &= \inf \{ c(S, T) ~|~ S,T \text{ is a cut}\}\\ &= \inf \{ F \subseteq E ~|~ F \text{ separates }s,t \}. \end{align*}$and the supremum is achieved by some flow. > > > [!proof]- Proof of supremum being attained > > > > By definition of the supremum, there is a sequence of flows $(f_{n})$ where $v(f_{n}) \to \mathrm{LHS}$. Now enumerate the edges in $E=(e_{1},\dots)$. > > By taking subsequences, we may assume $(f_{n}(e_{1}))$ converges; now take subsequences again, so that $(f_{n}(e_{2}))$ converges; repeat till $E$ is exhausted ($G$ is finite), and we obtain a subsequence that converges to some function $f: E \to \mathbb{R}^{+}$ given by $f(e_{i}):=\lim_{n \to \infty}f_{n}(e_{i}).$ > > It is a feasible flow since limits preserves $I_{f}(x)=\lim I_{f_{n}}(x)=0$ for any $x \ne s,t$, and $f(e)= \lim f_{n}(e) \le c(e)$ for any $e$. > > > > Lastly, its value attains the supremum simply because the filtered subsequence $(f_{n})$ still has the value-limit $(v(f_{n})) \to \mathrm{LHS}$. > > > [!proof]- Proof of equality > > Firstly, note that any cut has capacity no less than the value of the maximal flow, so we only need to show that there is some cut with capacity equal to it. > > > > Using the maximal flow obtained above, define the partition $S,T$ as $S := \{ x \in V ~|~ \exists \text{ slack path }s \to x\},~~ T:= V-S.$Then it is a cut since $s \in S$, and $t \not \in S$ because the existence of a $s-t$ slack path contradicts maximality. > > > > Moreover, the cut is at max capacity, i.e. $\forall x,y: xy \in E(S,T), f(xy)=c(xy)$because any exception $(x,y)$ allows us to extend the $s \to x$ slack path by $xy$ to get an $s \to y$ slack path, contradicting $y \in T$. > > > > Therefore, there exists a cut with capacity equal to $v(f)=\mathrm{LHS}$. > > [!theorem|*] Integral Max Flow for an Integral Capacity > If the capacity function is **integral**, i.e. only taking integer values, there exists a maximal flow that is integral. > > [!proof]- > > First note that if both $c,f$ are integral, any slack path must be (at least) $1$-slack. > > > > Start with the zero flow $f \equiv 0$, then repeatedly increment it by $1$ by looking for a $1$-slack $s-t$ path. If no such path exists, then we can define the cut $S,T$ like in the max-flow-min-cut theorem to find $c(S,T)=v(f)$, guaranteeing maximality. > > > > This yields an integral flow since for every iteration $f$ only changes by $0$ or $1$. > [!theorem|*] Max Flow Min Cut (Vertices) > If there is a vertex-capacity function $c: V \to \mathbb{R}^{+}$, for which a **vertex-cut** $X \subseteq V-\{ s,t \}$ that separates $s$ and $t$ has capacity $c(X):= \sum_{x \in X}c(x)$, $\begin{align*} \sup \{ &v(f) ~|~ f \text{ is feasible}\}\\ &= \inf \{ c(X) ~|~ X \text{ is a vertex-cut}\}. > \end{align*}$ > > > [!proof]- > > Proof follows by modifying $G$ into another graph $G^{\ast}$: replace $\forall x \ne s,t$ with $x^{+}$ and $x^{-}$ and the edge $x^{-}x^{+}$. $x^{+}$ gets the out-going and $x^{-}$ the incoming edges. Replace the vertex-capacity $c$ with an equal edge capacity on $x^{-}x^{+}$; all other edges have infinite capacity. > > > > Then max-flow-min-cut on edge capacities apply, giving a maximal flow $f^{\ast}$ and minimal cut $(S,T)$. > > - $(S,T)$ can translate into a vertex cut on the original $G$, because $c(S,T)<\infty$ implies that $E(S,T)$ only contains edges $\{ x^{-}x^{+} ~|~ x \in X\}$ for some vertex cut $X \subseteq G$. > > - $f^{\ast}$ corresponds to the flow $f$ where $f(x):= f^{\ast}(x^{-}x^{+})$. ## Connectivity A set of paths are **independent** if they are mutually **vertex disjoint** (except at the start and end). Let $\kappa(x,y)$ denote the minimal number of vertices that need to be removed so that $x,y$ are disconnected. There can't be a set of more than $\kappa(x,y)$ independent $xy$-paths, otherwise at least one of them remain after removing $\kappa(x,y)$ vertices. Moreover, this bound can be achieved: > [!theorem|*] Menger's Theorem (vertex-connectivity) > The largest set of *vertex-disjoint* $xy$-paths has exactly $\kappa(x,y)$ members. > > > [!proof] > > Let $x,y$ be the source and sink respectively, and let the vertex-capacity $c$ give a capacity of $1$ to all other vertices. > > > > Then by max-flow-min-cut (vertex version), there exists an maximal flow $f$ which is also integral (so each vertex has a flow of $0$ or $1$). Moreover, if $S$ is the minimal vertex-cut that separates $x,y$, $\sup\{ v(f) \}=| S |=\kappa(x,y).$Following the paths where the flow is $1$ gives the paths that are independent: no two paths can share a vertex (other than ) since it only has capacity $1$. Similarly, if $\lambda(x,y)$ is the minimal number of edges to be removed so that $x,y$ can be separated, > [!theorem|*] Menger's Theorem (edge connectivity) > The largest set of *edge-disjoint* $xy$-paths has exactly $\lambda(x,y)$ memebers. > > > [!proof] > > Imitate the proof above, let $x$ be a source and $y$ a sink, and give all edges a capacity of $1$. There exists a maximal flow $f$ which is integral, and an edge-cut of capacity (hence size) $v(f)$. > > - By definition of $\lambda$ as the smallest edge cut size, we have $v(f) \ge \lambda(x,y)$. > > - However, $v(f) \le \lambda(x,y)$ because the value of the feasible flow $f$ cannot exceed the capacity of smallest cut (which has capacity $\lambda$). > > > > Therefore $v(f)=\lambda(x,y)$, and an argument similar to the vertex version finds the $xy$-paths. They are edge-disjoint due to capacity issues.