9.6. 最大フロー最小カット定理の応用
これまでに言及してこなかった最大フロー最小カット定理の応用をいくつか示す:
-
行列の要素を丸める操作に関する次の興味深い事実: \(A\) を \(m \times n\) の実行列とする。\(A\) の任意の列の和と任意の行の和が全て整数だと仮定する。このとき、\(A\) の任意の列の和と任意の行の和を変えないように \(A\) の整数でない要素を整数に丸める (実数 \(x\) を \(\lceil x \rceil\) または \(\lfloor x \rfloor\) に置き換える) ことができる (行列を表す有向グラフに対する命題が [Schrij17, Exercise 4.13] にある)。
-
「混合グラフ (mixed graph)」 (無向辺と有向弧の両方を持つことができる、一般性が増したグラフの概念) にオイラー回路が存在するかどうかを判定する Euler–Hierholzer 条件に似た条件 [ForFul74, § II.7]
-
Erdős–Gallai の定理の証明: この定理は \(n\) 個の広義単調減少な非負整数列 \(d_{1}, d_{2}, \ldots, d_{n}\) \(\left( d_{1}\geq d_{2}\geq\cdots\geq d_{n}\right) \) が与えられたときに、次数が \(d_{1},d_{2},\ldots,d_{n}\) である \(n\) 頂点の単純グラフが存在するのは、和 \(d_{1}+d_{2}+\cdots+d_{n}\) が偶数かつ任意の \(i\in\left\{ 1,2,\ldots,n\right\} \) が次の条件を満たすとき、かつそのときに限ると主張する:
\[ \sum_{i=1}^{k}d_{i}\leq k\left( k-1\right) +\sum_{i=k+1}^{n}\min\left\{d_{i},k\right\} \]
次の練習問題は最大フロー最小カット定理を使っても使わなくても解くことができる。両方の解法を考えてみるとよいだろう。
多重有向グラフ \(D=\left( V,A,\psi\right) \)、入口 \(s \in V\)、出口 \(t \in V\)、容量関数 \(c\colon A\rightarrow\mathbb{N}\) から構成されるネットワークを \(N\) とする。
\(V\) の部分集合 \(S\) が \(s \in S\) と \(t \notin S\) を満たすとき、\(S\) を \(s\)-\(t\)-切断部分集合 (\(s\)-\(t\)-cutting subset) と呼ぶ。
全ての \(s\)-\(t\)-切断部分集合 \(S\) を考えたときの \(c\left( S,\overline{S}\right) \) の最小値を \(m\) とする。
\(s\)-\(t\)-切断部分集合 \(S\) が \(c\left( S,\overline{S}\right) =m\) を満たすとき、\(S\) をカット最小 (cut-minimal) と呼ぶことにする。
\(X\) と \(Y\) を二つのカット最小な \(s\)-\(t\)-切断部分集合とする。このとき \(X\cap Y\) と \(X\cup Y\) もカット最小な \(s\)-\(t\)-切断部分集合だと示せ。