最大流最小カット定理のLP双対を用いた証明
今回は、グラフ理論分野における超有名定理、最大流最小カット定理の証明について書いてみようと思います。
最大流最小カット定理は証明方法がいくつかありますが、今回は線形計画法の双対を用いた証明を紹介します。この証明方法はFord-Fulkersonのアルゴリズムを用いた証明に比べるとやや煩雑ですが、線形計画問題と整数計画問題の間を行き来する例として勉強になる（？）証明方法です。
1. 線形計画法の復習
まずは線形計画問題の双対について復習です。次の線形計画問題が与えられたとします。
$\mathrm{(P)}$
$$\begin{aligned} \mathrm{max}\ \ &c^{\mathrm{T}}x\\ \mathrm{subject\ to}\ \ &Ax\leq b \end{aligned}$$
これの双対問題は以下のようになります。
$\mathrm{(D)}$
$$\begin{aligned} \mathrm{min}\ \ &b^{\mathrm{T}}y\\ \mathrm{subject\ to}\ \ &A^{\mathrm{T}}y=c\\ &y\geq 0\end{aligned}$$
実は、最大流問題と最小カット問題の双対も、これらの線形計画問題の双対に対応しています。つまり、最大流問題を線形計画問題として表すと、その双対をとった問題は最小カット問題となっているのです！このことを示せば、線形計画問題では主問題と双対問題の最適値が等しい*1ことから、最大流最小カット定理を示すことができます。
2. 最大流最小カット定理の証明
では、最大流最小カット定理を証明していきましょう。任意の有向グラフ$G=(V, A)$と、始点$s$、終点$t$が与えられたとします。各辺$(i, j)\in A$の容量を$c_{ij}$とします。この$G$に十分大きな容量$c_{ts}$を持つ有向辺$(t, s)$を付け加えたグラフを$\tilde{G}$とします。すると、最大流問題は、$\tilde{G}$のすべての頂点で流れ込む流量と出ていく流量が等しくなるようなフローを考えたときに、そのようなフローがとりうる辺$(t, s)$の流量の最大値を求める問題に言い換えることができます。
さて、$\tilde{G}$の接続行列*2を$N$、$\tilde{G}$の各辺$(i, j)$の容量$c_{ij}$を並べたベクトルを$c=(c_{ij})\in R^{|A|+1}$とします。また、各辺$(i, j)$の流量を$x_{ij}$とし、$x_{ij}$を並べたベクトルを$x=(x_{ij})\in R^{|A|+1}$とします。このとき、最大流問題（を先ほど言い換えた問題）は以下のように表現できます。
$\mathrm{(P)}$
$$\begin{aligned} \mathrm{max}\ \ &x_{ts}\\ \mathrm{subject\ to}\ \ &Nx=0\\ &0\leq x\leq c\end{aligned}$$
これを少し変形すると以下のようになります。
$\mathrm{(P)}$
$$\begin{aligned} \mathrm{max}\ \ &x_{ts}\\ \\ \mathrm{subject\ to}\ \ &\left( \begin{array}{ccccc} N \\ -N \\ -I \\ I \end{array} \right) x\leq \left(\begin{array}{c} 0 \\ 0 \\ 0 \\ c \end{array} \right) \end{aligned}$$
これの双対問題は次のようになります。
$\mathrm{(D)}$
$$\begin{aligned} \mathrm{min}\ \ &\left( \begin{array}{ccccc} 0 \\ 0 \\ 0 \\ c \end{array} \right)^{\mathrm{T}} \! \! \! y \\ \\ \mathrm{subject\ to} \ \ &\left( \begin{array}{ccccc} N^{\mathrm{T}} \ -N^{\mathrm{T}} \ -I \ \ \ I \end{array} \right)y=e \\ \\ &y\geq 0 \end{aligned}$$
ただし、$e$は各成分が$\tilde{G}$の各辺に対応している$|A|+1$次元ベクトルであり、辺$(t, s)$に対応する成分は1で、それ以外の成分は0となっています。
ここで、$y$を$-N^{\mathrm{T}}$、$N^{\mathrm{T}}$、$-I$、$I$のそれぞれに対応する部分ごとに分ける、つまり
$$y=\begin{aligned} \left( \begin{array}{ccccc} y_1 \\ y_2 \\ y_3 \\ y_4 \end{array} \right) \end{aligned}$$
と分けます（$y_1, y_2\in R^{\mathrm{|V|}}$、$y_3, y_4\in R^{\mathrm{|A|+1}}$）。
すると、$\mathrm{(D)}$は
$\mathrm{(D)}$
$$\begin{aligned} \mathrm{min}\ \ &c^{\mathrm{T}}y_4\\ \\ \mathrm{subject\ to} \ \ &\left( \begin{array}{ccccc} N^{\mathrm{T}} \ -N^{\mathrm{T}} \ -I \ \ \ I \end{array} \right)\ \left( \begin{array}{ccccc} y_1 \\ y_2 \\ y_3 \\ y_4 \end{array} \right)=e \\ \\ &\left( \begin{array}{ccccc} y_1 \\ y_2 \\ y_3 \\ y_4 \end{array} \right)\geq 0 \end{aligned}$$
となります。
さらに、$z=y_1-y_2$とおくと、$\mathrm{(D)}$は以下のようになります。
$\mathrm{(D)}$
$$\begin{aligned} \mathrm{min}\ \ &c^{\mathrm{T}}y_4\\ \\ \mathrm{subject\ to} \ \ &\left( \begin{array}{ccccc} N^{\mathrm{T}} \ -I \ \ \ I \end{array} \right)\ \left( \begin{array}{ccccc} z \\ y_3 \\ y_4 \end{array} \right)=e \\ \\ &\left( \begin{array}{ccccc} y_3 \\ y_4 \end{array} \right)\geq 0 \end{aligned}$$
つまりこれは
$\mathrm{(D)}$
$$\begin{aligned} \mathrm{min}\ \ &c^{\mathrm{T}}y_4\\ \\ \mathrm{subject\ to} \ \ &\left( \begin{array}{ccccc} N^{\mathrm{T}} \ \ I \end{array} \right)\ \left( \begin{array}{ccccc} z \\ y_4 \end{array} \right)\geq e \\ &y_4\geq 0 \end{aligned}$$
と変形できて、さらに
$\mathrm{(D)}$
$$\begin{aligned} \mathrm{min}\ \ &c^{\mathrm{T}}y_4\\ \\ \mathrm{subject\ to} \ \ &\left( \begin{array}{ccccc} N^{\mathrm{T}} &I \\ 0 &I \end{array} \right)\ \left( \begin{array}{ccccc} z \\ y_4 \end{array} \right)\geq \left( \begin{array}{ccccc} e \\ 0 \end{array} \right) \end{aligned}$$
と変形できます。
さて、この問題$\mathrm{(D)}$が最小カット問題となっていることを説明しましょう。
まず、$\mathrm{(D)}$の制約条件の式は$2(|A|+1)$本ありますが、そのすべてを満たす部分は多面体の内部となります。この多面体の任意の頂点は、$\begin{aligned} &\left( \begin{array}{ccccc} N^{\mathrm{T}} &I \\ 0 &I \end{array} \right) \end{aligned}$が完全単模行列*3*4であることから、座標がすべて整数となります（いくつかの平面の式をまとめて$Ax=b$と表したとき、これらが交わってできる頂点は$x=A^{-1}b$によって求められることを思い出せばわかります）。そして、$\mathrm{(D)}$で最小値を達成するのは、制約条件が表す多面体の頂点のいずれかにおいてなので、$\mathrm{(D)}$の最適解は整数ベクトルとなります。
さて、$\mathrm{(D)}$を整数計画問題に言い換えられたところで、以下のように書き換えます。
$\mathrm{(D')}$
$$\begin{aligned} \mathrm{min}\ \ &c^{\mathrm{T}}y_4 \\ \\ \mathrm{subject\ to}\ \ &N^{\mathrm{T}}z+y_4 \geq e \\ &y_4 \geq 0 \\ &y_4\in Z^{\mathrm{|A|+1}},\ z\in Z^{\mathrm{|V|}} \end{aligned}$$
ここで、頂点$i$に対応する$z$の成分を$z_i$と表し、辺$(i, j)$に対応する$y_4$の成分を$y_{4(i, j)}$と表すことにします。すると、$c_{ts}$が十分大きいことから、$y_{4(t, s)}$は0になる、つまり$$z_t-z_s \geq 1$$が成り立ちます（$e$の辺$(t, s)$に対応する成分は1であることに注意）。これを踏まえて、以下のように頂点集合$U$、$W$を定義します:$$\begin{aligned} \ &U=\{ u\in V\ |\ z_u \leq z_s\} \\ &W=\{ w\in V\ |\ z_s+1 \leq z_w\} \end{aligned}$$
このとき、$U, W$は$V$の分割であり、また$s\in U$、$t\in W$なので、$U, W$は$s, t$を分けるカットとなっています。ここで、$u\in U, w\in W$を満たす辺$(u, w)$について、$$z_u-z_w \leq -1$$なので、$$y_{4(u, w)} \geq -z_u+z_w \geq 1$$が成り立ちます。よって、$$c^{\mathrm{T}}y_4 \geq \sum_{u\in U, w\in W} c_{uw}$$が成り立ちます。ここで、$\sum_{u\in U, w\in W} c_{uw}$は$\tilde{G}$の$U, W$によるカットの容量です。つまり、$c^{\mathrm{T}}y_4$は$\tilde{G}$の最小カットの容量によって下から抑えられることがわかります。一方で、$\tilde{G}$のある最小カット$U, W(s\in U, t\in W)$に対して、$z, y_4$を$$\begin{aligned}z_i &= \begin{cases} 0 &(i\in U) \\ 1&(i\in W) \end{cases} \\ \\ y_{4(i, j)}&=\begin{cases}1&(i\in U, j\in W) \\ 0&(\mathrm{otherwise}) \end{cases} \end{aligned}$$と定めれば、$c^{\mathrm{T}}y_4$は最小カット$U, W$の容量となります。ゆえに、$\mathrm{(D')}$は$\tilde{G}$についての最小カット問題（＝$G$についての最小カット問題）と等価であり、つまり最大流問題を線形計画問題として表したものの双対をとると、最小カット問題となることが示されました。
*1:ただし主問題か双対問題に実行可能解がない場合は除きます。
*2:ここでは有向グラフ$\tilde{G}$を考えているので、接続行列の成分$(i, j)$は、頂点$i$が第$j$列に対応する有向辺の始点であれば1、終点であれば-1、どちらでもなければ0となります。
*3:完全単模行列とは、任意の部分正方行列の行列式が0、-1、1のいずれかであるような行列のことです。
*4:$\begin{aligned} &\left( \begin{array}{ccccc} N^{\mathrm{T}} &I \\ 0 &I \end{array} \right) \end{aligned}$が完全単模行列であることは、接続行列$N$が完全単模行列であることからわかります。接続行列が完全単模行列であることの証明は、例えばhttp://www.misojiro.t.u-tokyo.ac.jp/~murota/lect-surikeikakuhou/integerprogunimod101222.pdfに載っています。
