Skip to content

26.1 Flow networks

26.1-1

Show that splitting an edge in a flow network yields an equivalent network. More formally, suppose that flow network $G$ contains edge $(u, v)$, and we create a new flow network $G'$ by creating a new vertex $x$ and replacing $(u, v)$ by new edges $(u, x)$ and $(x, v)$ with $c(u, x) = c(x, v) = c(u, v)$. Show that a maximum flow in $G'$ has the same value as a maximum flow in $G$.

We will prove that for every flow in $G = (V, E)$, we can construct a flow in $G' = (V', E')$ that has the same value as that of the flow in $G$. The required result follows since a maximum flow in $G$ is also a flow. Let $f$ be a flow in $G$. By construction, $V' = V \cup \{x\}$ and $E' = (E - \{(u, v)\}) \cup \{(u, x), (x, v)\}$. Construct $f'$ in $G'$ as follows:

$$ f'(y, z) = \begin{cases} f(y, z) & \text{if $(y, z) \ne (u, x)$ and $(y, z) \ne (x, v)$}, \\ f(u, v) & \text{if $(y, z) = (u, x)$ or $(y, z) = (x, v)$}. \end{cases} $$

Informally, $f'$ is the same as $f$, except that the flow $f(u, v)$ now passes through an intermediate vertex $x$. The vertex $x$ has incoming flow (if any) only from $u$, and has outgoing flow (if any) only to vertex $v$.

We first prove that $f'$ satisfies the required properties of a flow. It is obvious that the capacity constraint is satisfied for every edge in $E'$ and that every vertex in $V' - \{u, v, x\}$ obeys flow conservation.

To show that edges $(u, x)$ and $(x, v)$ obey the capacity constraint, we have

$$ \begin{aligned} f'(u, x) = f(u, v) & \le c(u, v) = c(u, x), \\ f'(x, v) = f(u, v) & \le c(u, v) = c(x, v). \end{aligned} $$

We now prove flow conservation for $u$. Assuming that $u \ne \{s, t\}$, we have

$$ \begin{aligned} \sum_{y \in V'} f'(u, y) & = \sum_{y \in V' - \{x\}} f'(u, y) + f'(u, x) \\ & = \sum_{y \in V - \{v\}} f(u, y) + f(u, v) \\ & = \sum_{y \in V} f(u, y) \\ & = \sum_{y \in V} f(y, u) \quad \text{(because $f$ obeys flow conservation)} \\ & = \sum_{y \in V'} f'(y, u). \end{aligned} $$

For vertex $v$, a symmetric argument proves flow conservation.

For vertex $x$, we have

$$ \begin{aligned} \sum_{y \in V'} f'(y, x) & = f'(u, x) \\ & = f'(x, v) \\ & = \sum_{y \in V'} f'(x, y). \end{aligned} $$

Thus, $f'$ is a valid flow in $G'$.

We now prove that the values of the flow in both cases are equal. If the source $s$ is not in $\{u, v\}$, the proof is trivial, since our construction assigns the same flows to incoming and outgoing edges of $s$. If $s = u$, then

$$ \begin{aligned} |f'| & = \sum_{y \in V'} f'(u, y) - \sum_{y \in V'} f'(y, u) \\ & = \sum_{y \in V' - \{x\}} f'(u, y) - \sum_{y \in V'} f'(y, u) + f'(u, x) \\ & = \sum_{y \in V - \{v\}} f(u, y) - \sum_{y \in V} f(y, u) + f(u, v) \\ & = \sum_{y \in V} f(u, y) - \sum_{y \in V} f(y, u) \\ & = |f|. \end{aligned} $$

The case when $s = v$ is symmetric. We conclude that $f'$ is a valid flow in $G'$ with $|f'| = |f|$.

26.1-2

Extend the flow properties and definitions to the multiple-source, multiple-sink problem. Show that any flow in a multiple-source, multiple-sink flow network corresponds to a flow of identical value in the single-source, single-sink network obtained by adding a supersource and a supersink, and vice versa.

Capacity constraint: for all $u, v \in V$, we require $0 \le f(u, v) \le c(u, v)$.

Flow conservation: for all $u \in V - S - T$, we require $\sum_{v \in V} f(v, u) = \sum_{v \in V} f(u, v)$.

26.1-3

Suppose that a flow network $G = (V, E)$ violates the assumption that the network contains a path $s \leadsto v \leadsto t$ for all vertices $v \in V$. Let $u$ be a vertex for which there is no path $s \leadsto u \leadsto t$. Show that there must exist a maximum flow $f$ in $G$ such that $f(u, v) = f(v, u) = 0$ for all vertices $v \in V$.

We show that, given any flow $f'$ in the flow network $G = (V, E)$, we can construct a flow $f$ as stated in the exercise. The result will follow when $f'$ is a maximum flow. The idea is that even if there is a path from $s$ to the connected component of $u$, no flow can enter the component, since the flow has no path to reach $t$. Thus, all the flow inside the component must be cyclic, which can be made zero without affecting the net value of the flow.

Two cases are possible: where $u$ is not connected to $t$, and where $u$ is not connected to $s$. We only analyze the former case. The analysis for the latter case is similar.

Let $Y$ be the set of all vertices that have no path to $t$. Our roadmap will be to first prove that no flow can leave $Y$. We use this result and flow conservation to prove that no flow can enter $Y$. We shall then constuct the flow $f$, which has the required properties, and prove that $|f| = |f'|$.

The first step is to prove that there can be no flow from a vertex $y \in Y$ to a vertex $v \in V - Y$. That is, $f'(y, v) = 0$. This is so, because there are no edges $(y, v)$ in $E$. If there were an edge $(y, v) \in E$, then there would be a path from $y$ to $t$, which contradicts how we defined the set $Y$.

We will now prove that $f'(v, y) = 0$, too. We will do so by applying flow conservation to each vertex in $Y$ and taking the sum over $Y$. By flow conservation, we have

$$\sum_{y \in Y} \sum_{v \in V} f'(y, v) = \sum_{y \in Y} \sum_{v \in V} f'(v, y).$$

Partitioning $V$ into $Y$ and $V - Y$ gives

$$\sum_{y \in Y} \sum_{v \in V - Y} f'(y, v) + \sum_{y \in Y} \sum_{v \in V} f'(y, v) = \sum_{y \in Y} \sum_{v \in V - Y} f'(v, y) + \sum_{y \in Y} \sum_{v \in Y} f'(v, y). \tag{*}$$

But we also have

$$\sum_{y \in Y} \sum_{v \in Y} f'(y, v) = \sum_{y \in Y} \sum_{v \in Y} f'(v, y),$$

since the left-hand side is the same as the right-hand side, except for a change of variable names $v$ and $y$. We also have

$$\sum_{y \in Y} \sum_{v \in V - Y} f'(y, v) = 0,$$

since $f'(y, v) = 0$ for each $y \in Y$ and $v \in V - Y$. Thus, equation $(*)$ simplifies to

$$\sum_{y \in Y} \sum_{v \in V - Y} f'(v, y) = 0.$$

Because the flow function is nonnegative, $f(v, y) = 0$ for each $v \in V$ and $y \in Y$. We conclude that there can be no flow between any vertex in $Y$ and any vertex in $V - Y$.

The same technique can show that if there is a path from $u$ to $t$ but not from $s$ to $u$, and we define $Z$ as the set of vertices that do not have have a path from $s$ to $u$, then there can be no flow between any vertex in $Z$ and any vertex in $V - Z$. Let $X = Y \cup Z$. We thus have $f'(v, x) = f'(x, v) = 0$ if $x \in X$ and $v \ne X$.

We are now ready to construct flow $f$:

$$ f(u, v) = \begin{cases} f'(u, v) & \text{if $u, v \ne X$}, \\ 0 & \text{otherwise}. \end{cases} $$

We note that $f$ satisfies the requirements of the exercise. We now prove that $f$ also satisfies the requirements of a flow function.

The capacity constraint is satisfied, since whenever $f(u, v) = f'(u, v)$, we have $f(u, v) = f'(u, v) \le c(u, v)$ and whenever $f(u, v) = 0$, we have $f(u, v) = 0 \le c(u, v)$.

For flow conservation, let $x$ be some vertex other than $s$ or $t$. If $x \in X$, then from the construction of $f$, we have

$$\sum_{v \in V} f(x, v) = \sum_{v \in V} f(v, x) = 0.$$

Otherwise, if $x \ne X$, note that $f(x, v) = f'(x, v)$ and $f(v, x) = f'(v, x)$ for all vertices $v \in V$. Thus,

$$ \begin{aligned} \sum_{v \in V} f(x, v) & = \sum_{v \in V} f'(x, v) \\ & = \sum_{v \in V} f'(v, x) \quad \text{(because $f'$ obeys flow conservation)} \\ & = \sum_{v \in V} f(v, x). \end{aligned} $$

Finally, we prove that the value of the flow remains the same. Since $s \ne X$, we have $f(s, v) = f'(s, v)$ and $f(v, x) = f'(v, x)$ for all vertices $v \in V$, and so

$$ \begin{aligned} |f| & = \sum_{v \in V} f(s, v) - \sum_{v \in V} f(v, s) \\ & = \sum_{v \in V} f'(s, v) - \sum_{v \in V} f'(v, s) \\ & = |f'|. \end{aligned} $$

26.1-4

Let $f$ be a flow in a network, and let $\alpha$ be a real number. The scalar flow product, denoted $\alpha f$, is a function from $V \times V$ to $\mathbb{R}$ defined by

$$(\alpha f)(u, v) = \alpha \cdot f(u, v).$$

Prove that the flows in a network form a convex set. That is, show that if $f_1$ and $f_2$ are flows, then so is $\alpha f_1 + (1 - \alpha) f_2$ for all $\alpha$ in the range $0 \le \alpha \le 1$.

To see that the flows form a convex set, we show that if $f_1$ and $f_2$ are flows, then so is $\alpha f_1 + (1 - \alpha) f_2$ for all $\alpha$ such that $0 \le \alpha \le 1$.

For the capacity constraint, first observe that $\alpha \le 1$ implies that $1 - \alpha \ge 0$. Thus, for any $u, v \in V$, we have

$$ \begin{aligned} \alpha f_1(u, v) + (1 - \alpha) f_2(u, v) & \ge 0 \cdot f_1(u, v) + 0 \cdot (1 - \alpha) f_2(u, v) \\ & = 0. \end{aligned} $$

Since $f_1(u, v) \le c(u, v)$ and $f_2(u, v) \le c(u, v)$, we also have

$$ \begin{aligned} \alpha f_1(u, v) + (1 - \alpha) f_2(u, v) & \le \alpha c(u, v) + (1 - \alpha) c(u, v) \\ & = (\alpha + (1 - \alpha))c(u, v) \\ & = c(u, v). \end{aligned} $$

For flow conservation, observe that since $f_1$ and $f_2$ obey flow conservation, we have $\sum_{v \in V} f_1(v, u) = \sum_{v \in V} f_1(u, v)$ and $\sum_{v \in V} f_1(v, u) = \sum_{v \in V} f_1(u, v)$ for any $u \in V - \{s, t\}$. We need to show that

$$\sum_{v \in V} (\alpha f_1(v, u) + (1 - \alpha) f_2(v, u)) = \sum_{v \in V} (\alpha f_1(u, v) + (1 - \alpha) f_2(u, v))$$

for any $u \in V - \{s, t\}$. We multiply both sides of the equality for $f_1$ by $\alpha$, multiply both sides of the equality for $f_2$ by $1 - \alpha$, and add the left-hand and right-hand sides of the resulting equalities to get

$$\alpha \sum_{v \in V} f_1(v, u) + (1 - \alpha) \sum_{v \in V} f_2(v, u) = \alpha \sum_{v \in V} f_1(u, v) + (1 - \alpha) \sum_{v \in V} f_2(u, v).$$

Observing that

$$ \begin{aligned} \alpha \sum_{v \in V} f_1(v, u) + (1 - \alpha) \sum_{v \in V} f_2(v, u) & = \sum_{v \in V} \alpha f_1(v, u) + \sum_{v \in V} (1 - \alpha) f_2(v, u) \\ & = \sum_{v \in V} (\alpha f_1(v, u) + (1 - \alpha) f_2(v, u)) \end{aligned} $$

and, likewise, that

$$\alpha \sum_{v \in V} f_1(u, v) + (1 - \alpha) \sum_{v \in V} f_2(u, v) = \sum_{v \in V} (\alpha f_1(u, v) + (1 - \alpha)f_2(u, v))$$

completes the proof that flow conservation holds, and thus that flows form a convex set.

26.1-5

State the maximum-flow problem as a linear-programming problem.

$$ \begin{array}{ll} \max & \sum\limits_{v \in V} f(s, v) - \sum\limits_{v \in V} f(v, s) \\ s.t. & 0 \le f(u, v) \le c(u, v) \\ & \sum\limits_{v \in V} f(v, u) - \sum\limits_{v \in V} f(u, v) = 0 \end{array} $$

26.1-6

Professor Adam has two children who, unfortunately, dislike each other. The problem is so severe that not only do they refuse to walk to school together, but in fact each one refuses to walk on any block that the other child has stepped on that day. The children have no problem with their paths crossing at a corner. Fortunately both the professor's house and the school are on corners, but beyond that he is not sure if it is going to be possible to send both of his children to the same school. The professor has a map of his town. Show how to formulate the problem of determining whether both his children can go to the same school as a maximum-flow problem.

Create a vertex for each corner, and if there is a street between corners $u$ and $v$, create directed edges $(u, v)$ and $(v, u)$. Set the capacity of each edge to $1$. Let the source be corner on which the professor's house sits, and let the sink be the corner on which the school is located. We wish to find a flow of value $2$ that also has the property that $f(u, v)$ is an integer for all vertices $u$ and $v$. Such a flow represents two edge-disjoint paths from the house to the school.

26.1-7

Suppose that, in addition to edge capacities, a flow network has vertex capacities. That is each vertex $v$ has a limit $l(v)$ on how much flow can pass though $v$. Show how to transform a flow network $G = (V, E)$ with vertex capacities into an equivalent flow network $G' = (V', E')$ without vertex capacities, such that a maximum flow in $G'$ has the same value as a maximum flow in $G$. How many vertices and edges does $G'$ have?

We will construct $G'$ by splitting each vertex $v$ of $G$ into two vertices $v_1$, $v_2$, joined by an edge of capacity $l(v)$. All incoming edges of $v$ are now incoming edges to $v_1$. All outgoing edges from $v$ are now outgoing edges from $v_2$.

More formally, construct $G' = (V', E')$ with capacity function $c'$ as follows. For every $v \in V$, create two vertices $v_1$, $v_2$ in $V'$. Add an edge $(v_1, v_2)$ in $E'$ with $c'(v_1, v_2) = l(v)$. For every edge $(u, v) \in E$, create an edge $(u_2, v_1)$ in $E'$ with capacity $c'(u_2, v_1) = c(u, v)$. Make $s_1$ and $t_2$ as the new source and target vertices in $G'$. Clearly, $|V'| = 2|V|$ and $|E'| = |E| + |V|$.

Let $f$ be a flow in $G$ that respects vertex capacities. Create a flow function $f'$ in $G'$ as follows. For each edge $(u, v) \in G$, let $f'(u_2, v_1) = f(u, v)$. For each vertex $u \in V - \{t\}$, let $f'(u_1, u_2) = \sum_{v \in V} f(u, v)$. Let $f'(t_1, t_2) = \sum_{v \in V} f(v, t)$.

We readily see that there is a one-to-one correspondence between flows that respect vertex capacities in $G$ and flows in $G'$. For the capacity constraint, every edge in $G'$ of the form $(u_2, v_1)$ has a corresponding edge in $G$ with a corresponding capacity and flow and thus satisfies the capacity constraint. For edges in $E'$ of the form $(u_1, u_2)$, the capacities reflect the vertex capacities in $G$. Therefore, for $u \in V - \{s, t\}$, we have $f'(u_1, u_2) = \sum_{v \in V} f(u, v) \le l(u) = c'(u_1, u_2)$. We also have $f'(t_1, t_2) = \sum_{v \in V} f(v, t) \le l(t) = c'(t_1, t_2)$. Note that this constraint also enforces the vertex capacities in $G$.

Now, we prove flow conservation. By construction, every vertex of the form $u_1$ in $G'$ has exactly one outgoing edge $(u_1, u_2)$, and every incoming edge to $u_1$ corresponds to an incoming edge of $u \in G$. Thus, for all vertices $u \in V - \{s, t\}$, we have

$$ \begin{aligned} \text{incoming flow to $u_1$} & = \sum_{v \in V'} f'(v, u_1) \\ & = \sum_{v \in V} f(v, u) \\ & = \sum_{v \in V} f(u, v) \qquad \text{(because $f$ obeys flow conservation)} \\ & = f'(u_1, u_2) \\ & = \text{outgoing flow from $u_1$}. \end{aligned} $$

For $t_1$, we have

$$ \begin{aligned} \text{incoming flow} & = \sum_{v \in V'} f'(v, t_1) \\ & = \sum_{v \in V} f(v, u) \\ & = f'(t_1, t_2) \\ & = \text{outgoing flow}. \end{aligned} $$

Vertices of the form $u_2$ have exactly one incoming edge $(u_1, u_2)$, and every outgoing edge of $u_2$ corresponds to an outgoing edge of $u \in G$. Thus, for $u_2 \ne t_2$,

$$ \begin{aligned} \text{incoming flow} & = f'(u_1, u_2) \\ & = \sum_{v \in V} f(u, v) \\ & = \sum_{v \in V'} f'(u_2, v) \\ & = \text{outgoing flow}. \end{aligned} $$

Finally, we prove that $|f'| = |f|$:

$$ \begin{aligned} |f'| & = \sum_{v \in V'} f'(s_1, v) \\ & = f'(s_1, s_2) \qquad \text{(because there are no other outgoing edges from $s_1$)} \\ & = \sum_{v \in V} f(s, v) \\ & = |f|. \end{aligned} $$