京都大学 情報学研究科 数理工学専攻 2020年8月実施 グラフ理論

标签：

• Kyoto-University
• Maximum-Flow

Author

祭音Myyura

Description

日本語版

$G = (V, E)$ を節点集合 $V$, 枝集合 $E$ から成る単純有向グラフとし，$N = [G, c]$ を $G$ の各枝 $e \in E$ に実数値の容量 $c(e) > 0$ を与えて得られるネットワークとする． 節点の部分集合 $X, Y \subseteq V$ に対し，$X$ 内の点から $Y$ 内の点へ向かう枝の集合を $E(X, Y)$ と記す． 非負実数全体の集合を $\mathbb{R}_+$ で表す． 指定された二点 $s, t \in V$ に対し，流量保存則 $\sum_{e\in E(\{v\}, V \setminus \{v\})} f(e) - \sum_{e \in E(V \setminus \{v\}, \{v\})} f(e) = 0, \forall v \in V \setminus \{s, t\}$ および容量制約 $f(e) \le c(e), \forall e \in E$ を満たす関数 $f: E \rightarrow \mathbb{R}_+$ を $(s, t)$ フローと呼び，その流量 $\text{val}(f)$ を

$$\sum_{e\in E(\{s\}, V \setminus \{s\})} f(e) - \sum_{e \in E(V \setminus \{s\}, \{s\})} f(e)$$

で定める．また，$s \in X, t \in V \setminus X$ を満たす節点の部分集合 $X \subseteq V$ を $(s, t)$ カットと呼び，その容量 $\text{cap}(X)$ を

$$\sum_{e \in E(X, V \setminus X)} c(e)$$

で定める．以下の問いに答えよ．

(i) 任意の $(s, t)$ フロー $f$ と $(s, t)$ カット $X$ に対し，等式

$$\text{val}(f) = \sum_{e \in E(X, V \setminus X)} f(e) - \sum_{e \in E(V \setminus X, X)} f(e)$$

が成り立つことを証明せよ．

(ii) 与えられた $(s, t)$ フロー $f$ に対して定められる残余ネットワーク $N_f = [G_f = (V, E_f), c_f]$ の作り方を説明せよ．

(iii) 残余ネットワーク $N_f$ において，$s$ から $t$ への有向路が存在するとき，そのひとつを $P$ とする．$P$ 上の枝の $N_f$ における容量の最小値を $\Delta$ とするとき，$N$ には流量が $\text{val}(f) + \Delta$ である $(s, t)$ フローが存在することを証明せよ．

(iv) 残余ネットワーク $N_f$ が $s$ から $t$ への有向路をもたないとき，$N_f$ において $s$ から到達可能な節点の集合を $S$ とする．このとき，$s \in A$ である任意の集合 $A \subsetneq S$ に対し $\text{cap}(A) > \text{cap}(S)$ が成り立つことを証明せよ．

English Version

Let $G = (V, E)$ be a simple directed graph with a vertex set $V$ and an edge set $E$, and let $N = [G, c]$ be a network obtained from $G$ by assigning a real value $c(e) > 0$ to each edge $e \in E$ as its capacity. For vertex subsets $X, Y \subseteq V$, let $E(X, Y)$ denote the set of edges that leave a vertex in $X$ and enter a vertex in $Y$. Let $\mathbb{R}_+$ denote the set of nonnegative reals. For two designated vertices $s, t \in V$ , an $(s, t)$-flow is defined to be a mapping $f : E → \mathbb{R}_+$ which satisfies $\sum_{e\in E(\{v\}, V \setminus \{v\})} f(e) - \sum_{e \in E(V \setminus \{v\}, \{v\})} f(e) = 0, \forall v \in V \setminus \{s, t\}$ (flow conservation law) and $f(e) \le c(e), \forall e \in E$ (capacity constraint), and its flow value $\text{val}(f)$ is defined to be

$$\sum_{e\in E(\{s\}, V \setminus \{s\})} f(e) - \sum_{e \in E(V \setminus \{s\}, \{s\})} f(e)$$

An $(s, t)$-cut is defined to be a vertex subset $X \subseteq V$ such that $s \in X$ and $t \in V \setminus X$, and its capacity $\text{cap}(X)$ is defined to be

$$\sum_{e \in E(X, V \setminus X)} c(e)$$

Answer the following questions.

(i) Prove that for any $(s, t)$-flow $f$ and any $(s, t)$-cut $X$

$$\text{val}(f) = \sum_{e \in E(X, V \setminus X)} f(e) - \sum_{e \in E(V \setminus X, X)} f(e)$$

holds.

(ii) For a given $(s, t)$-flow $f$, show how to construct its residual network $N_f = [G_f = (V, E_f), c_f]$.

(iii) For an $(s, t)$-flow $f$ in $N$, assume that there is a directed path $P$ from $s$ to $t$ in the residual network $N_f$ . Let $\Delta$ denote the minimum capacity of an edge in $P$ in $N_f$. Prove that $N$ has an $(s, t)$-flow whose flow value is $\text{val}(f) + \Delta$.

(iv) For an $(s, t)$-flow $f$ in $N$, assume that there is no directed path from $s$ to $t$ in the residual network $N_f$. Let $S$ denote the set of vertices that are reachable from $s$ in $N_f$. Prove that $\text{cap}(A) > \text{cap}(S)$ holds for any set $A \subsetneq S$ with $s \in A$.

题目描述

设 $G=(V,E)$ 为简单有向图，网络 $N=[G,c]$ 给每条边 $e$ 赋予正实容量 $c(e)>0$。对 $X,Y\subseteq V$，记 $E(X,Y)$ 为从 $X$ 中顶点指向 $Y$ 中顶点的边集，$\mathbb R_+$ 为非负实数集。对指定的 $s,t\in V$，若映射 $f:E\to\mathbb R_+$ 满足

$$\sum_{e\in E(\{v\},V\setminus\{v\})}f(e) -\sum_{e\in E(V\setminus\{v\},\{v\})}f(e)=0 \quad(\forall v\in V\setminus\{s,t\})$$

以及 $f(e)\le c(e)$，则称其为 $(s,t)$ 流，其流值定义为

$$\operatorname{val}(f)= \sum_{e\in E(\{s\},V\setminus\{s\})}f(e) -\sum_{e\in E(V\setminus\{s\},\{s\})}f(e).$$

若 $X\subseteq V$ 满足 $s\in X$、$t\notin X$，则称其为 $(s,t)$ 割，容量为

$$\operatorname{cap}(X)=\sum_{e\in E(X,V\setminus X)}c(e).$$

回答：

1. 对任意 $(s,t)$ 流 $f$ 和 $(s,t)$ 割 $X$，证明

   $$\operatorname{val}(f)= \sum_{e\in E(X,V\setminus X)}f(e) -\sum_{e\in E(V\setminus X,X)}f(e).$$

2. 说明如何由给定流 $f$ 构造残量网络 $N_f=[G_f=(V,E_f),c_f]$。

3. 若 $N_f$ 中存在从 $s$ 到 $t$ 的有向路 $P$，令 $\Delta$ 为 $P$ 上残量容量的最小值。证明原网络中存在流值为 $\operatorname{val}(f)+\Delta$ 的 $(s,t)$ 流。

4. 若 $N_f$ 中不存在从 $s$ 到 $t$ 的有向路，令 $S$ 为在 $N_f$ 中从 $s$ 可达的顶点集。证明对任意满足 $s\in A\subsetneq S$ 的集合 $A$，都有 $\operatorname{cap}(A)>\operatorname{cap}(S)$。

Kai

(i)

We can rewrite the flow conservation law for any node $u \in V \setminus \{s, t\}$ as

$$\sum_{v \in V}f(u, v) - \sum_{v \in V} f(v, u) = 0$$

then we have

$$\begin{aligned} \text{val}(f) &= \sum_{e\in E(\{s\}, V \setminus \{s\})} f(e) - \sum_{e\in E(V \setminus \{s\}, \{s\})} f(e) \\ &= \sum_{v \in V} f(s, v) - \sum_{v \in V} f(v, s) + \sum_{u \in X - \{s\}} \Big(\sum_{v \in V} f(u, v) - \sum_{v \in V} f(v, u) \Big) \end{aligned}$$

Expanding the right-hand summation and regrouping terms yields

$$\begin{aligned} \text{val}(f) &= \sum_{v \in V} f(s, v) - \sum_{v \in V}f(v,s) + \sum_{u \in X \setminus \{s\}} \sum_{v \in V} f(u, v) - \sum_{u \in X \setminus \{s\}} \sum_{v \in V} f(v,u) \\ &= \sum_{v \in V} \Big(f(s,v) + \sum_{u \in X \setminus \{s\}}f(u,v) \Big) - \sum_{v \in V} \Big(f(v,s) + \sum_{u\in X \setminus \{s\}} f(v, u) \Big) \\ &= \sum_{v \in V} \sum_{u\in X} f(u, v) - \sum_{v \in V}\sum_{u \in X} f(v, u) \\ &= \sum_{v \in X} \sum_{u\in X} f(u, v) + \sum_{v \in V \setminus X} \sum_{u\in X} f(u, v) - \sum_{v \in X} \sum_{u \in X} f(v, u) - \sum_{v \in V \setminus X} \sum_{u \in X} f(v, u) \end{aligned}$$

The two summations $\sum_{v \in X} \sum_{u\in X} f(u, v)$ and $\sum_{v \in X} \sum_{u \in X} f(v, u)$ are actually the same, since for all vertices $x, y \in V$ , the term $f(x,y)$ appears once in each summation. therefore

$$\begin{aligned} \text{val}(f) &= \sum_{v \in V \setminus X} \sum_{u\in X} f(u, v) - \sum_{v \in V \setminus X} \sum_{u \in X} f(v, u) \\ &= \sum_{e \in E(X, V \setminus X)}f(e) - \sum_{e \in E(V\setminus X, X)} f(e) \end{aligned}$$

(ii)

For every original edge $e=(u,v)\in E$, introduce the following labeled residual edges whenever their capacities are positive:

$$\begin{aligned} e^+=(u,v),&\qquad c_f(e^+)=c(e)-f(e),\\ e^-=(v,u),&\qquad c_f(e^-)=f(e). \end{aligned}$$

The collection of these residual edges is $E_f$; coincident ordered endpoints are kept as distinct residual edges.

(iii)

Let $f': E \rightarrow \mathbb{R}_+$ be defined as follows:

$$f'(e) = \left\{ \begin{aligned} &f(e) + \Delta &\text{ if } e^+ \in P,\\ &f(e) - \Delta &\text{ if } e^- \in P,\\ &f(e) &\text{otherwise.} \end{aligned} \right.$$

We prove that $f'$ is a flow and $\text{val}(f') = \text{val}(f) + \Delta$

First we verify that $f'$ obeys that capacity constraint.

If the path uses the forward residual edge $e^+=(u,v)$, then

$$\begin{aligned} f'(u, v) &= f(u, v) + \Delta \\ &\le f(u, v) + c_f(e^+) \\ &= f(u, v) + c(u, v) - f(u,v) \\ &= c(u, v) \end{aligned}$$

If the path uses the backward residual edge $e^-=(v,u)$ of $e=(u,v)$, then

$$f'(u, v) = f(u, v) - \Delta \le c(u, v)$$

$$\begin{aligned} f'(u, v) &= f(u, v) - \Delta \\ &\ge f(u, v) - c_f(e^-) \\ &= f(u, v) - f(u, v) \\ &= 0 \end{aligned}$$

Hence the capacity constraint holds.

Next we prove the flow conservation constraint. For a vertex $u \in V \setminus \{s, t\}$, obviously the flow conservation constraint holds if $u \notin V(P)$. Hence we focus on the case that $u \in V(P)$.

For a vertex $u \in V(P) \setminus \{s, t\}$, since $P$ is a simple path, there are exactly two edges $(u_1, u)$ and $(u, u_2)$ in $P$ that adjacent to $u$. In the cases below, an edge notation in $E$ specifies which labeled forward or backward residual copy is used by $P$.

if $(u_1, u) \in E$ and $(u, u_2) \in E$, then we have

$$\begin{aligned} \sum_{v \in V} f'(u, v) &= \Big(\sum_{v \in V \setminus \{ u_2\}} f(u, v)\Big) + f'(u, u_2) \\ &= \Big(\sum_{v \in V \setminus \{ u_2\}} f(u, v)\Big) + f(u, u_2) + \Delta \\ &= \Big(\sum_{v \in V} f(u, v)\Big) + \Delta \end{aligned}$$

$$\begin{aligned} \sum_{v \in V} f'(v, u) &= \Big(\sum_{v \in V \setminus \{ u_1\}} f(v, u)\Big) + f'(u_1, u) \\ &= \Big(\sum_{v \in V \setminus \{ u_1\}} f(v, u)\Big) + f(u_1, u) + \Delta \\ &= \Big(\sum_{v \in V} f(v, u)\Big) + \Delta \end{aligned}$$

if $(u_1, u) \in E$ and $(u_2, u) \in E$, then we have

$$\sum_{v \in V} f'(u, v) = \sum_{v \in V} f(u, v)$$

$$\begin{aligned} \sum_{v \in V} f'(v, u) &= \Big(\sum_{v \in V \setminus \{ u_1, u_2\}} f(v, u)\Big) + f'(u_1, u) + f'(u_2, u) \\ &= \Big(\sum_{v \in V \setminus \{ u_1, u_2\}} f(v, u)\Big) + f(u_1, u) + \Delta + f(u_2, u) - \Delta \\ &= \sum_{v \in V} f(v, u) \end{aligned}$$

Similarly for the case $(u, u_1) \in E, (u, u_2) \in E$ and the case $(u, u_1) \in E, (u_2, u) \in E$. Hence the flow conservation constraint holds.

Finlly, we compute the value $\text{val}(f')$. Same as the proof of flow conservation constraint, there are two cases for the edge in $N$ corresponds to the edge adjacent to $s$ in $P$ of $N_f$.

It is easy to compute that in both cases we have

$$\text{val}(f') = \text{val}(f) + \Delta$$

Therefore, $N$ has an $(s, t)$-flow whose flow value is $\text{val}(f) + \Delta$.

(iv)

Because no residual edge leaves $S$, every original edge leaving $S$ is saturated and every original edge entering $S$ carries zero flow. Thus (i) gives $\operatorname{val}(f)=\operatorname{cap}(S)$, so $S$ is a minimum $(s,t)$-cut. Suppose that some $A\subsetneq S$ with $s\in A$ also satisfied $\operatorname{cap}(A)=\operatorname{cap}(S)=\operatorname{val}(f)$. Equality in (i) would force every edge leaving $A$ to be saturated and every edge entering $A$ to carry zero flow. Hence no residual edge could leave $A$.

Every vertex of $S$ is residual-reachable from $s$, so this would imply $S\subseteq A$, a contradiction. Therefore, $\operatorname{cap}(A)>\operatorname{cap}(S)$.