組合せ最適化
概要
組合せ最適化（combinatorial optimization）とは、最短路・最小全域木・最大マッチング・最大流・巡回セールスマン問題のように、有限個の候補（グラフの道や部分グラフ、集合の族の元）の中から目的の量を最大または最小にするものを選ぶ問題と、その解き方、最適性の証明を調べる分野である。候補は有限個なので最適解はいつも存在するが、個数が爆発的に増えるため、すべてを比べずに最適性がわかる構造が中心になる。その典型が、ネットワークの最大流の流量は最小カットの容量に等しく、容量が整数なら整数値の最大流があるという最大流最小カット定理であり、二部グラフの最大マッチングと最小頂点被覆の大きさが等しいことはその帰結である。また、価値の大きい順に取る貪欲法がどの非負の重みでも最適になるのは、制約がマトロイドをなすときに限る。
前提知識: グラフ, 有向グラフ, マッチング(グラフ理論), マトロイド
道路網で 2 地点を結ぶ最短の道を選ぶ、通信網を最小の費用でつなぐ、仕事と人をできるだけ多く組み合わせる、配管網でできるだけ多く流す。どれも、有限個の候補の中から、ある量を最大または最小にするものを選ぶ問題である。このような問題を 組合せ最適化問題 といい、その解き方と、解が最適であることの証明を調べる分野を 組合せ最適化 という。
候補が有限個なので最適解はいつも存在し、すべての候補を比べれば原理的には見つかる。しかし候補の個数は入力の大きさとともに爆発的に増える。組合せ最適化の中心にあるのは、すべてを比べなくても最適性がわかる構造である。この記事では、その典型として 2 つの定理を証明する。ネットワークを流れる量の最大値が、ネットワークを切る辺の容量の最小値に等しいという 最大流最小カット定理（thm-combopt-maxflow-mincut）と、価値の大きいものから順に取る 貪欲法 がどんな重みに対しても最適解を与えるのは、制約が マトロイド をなすときに限るという定理（thm-combopt-greedy-matroid）である。前者から、二部グラフの最大マッチングの大きさと最小頂点被覆の大きさが等しいことも導く（prop-combopt-bipartite）。
定義
空でない有限集合 $\mathcal{F}$ と写像 $c\colon\mathcal{F}\to\mathbb{R}$ の組 $(\mathcal{F},c)$ を 組合せ最適化問題（combinatorial optimization problem）の例（インスタンス）という。$\mathcal{F}$ の元を 実行可能解、$c$ を 目的関数 という。$c(x^*)=\max_{x\in\mathcal{F}}c(x)$ となる $x^*\in\mathcal{F}$ を求めることを最大化問題、$\min$ のときを最小化問題といい、$x^*$ を 最適解、$c(x^*)$ を 最適値 という。
よく使う形は次のものである。有限集合 $E$（台集合）、$E$ の部分集合の空でない族 $\mathcal{F}\subset 2^E$、重み $w\colon E\to\mathbb{R}$ をとり、$F\in\mathcal{F}$ について $w(F):=\sum_{e\in F}w(e)$ を目的関数とする。
$\mathcal{F}$ は有限で空でないので、最適解はいつも存在する。たとえば、グラフの全域木全体を $\mathcal{F}$、辺の重みの和を目的関数とすれば最小全域木問題、マッチング全体と辺の本数なら最大マッチング問題になる。「問題」というときは、入力（グラフと重みなど）ごとに 1 つの例が定まる例の族を指すことが多い。入力の大きさの多項式で抑えられる回数の基本操作で最適解を求める手順を、多項式時間の算法という。
直感
最適解を見つけることと、それが最適だと納得させることは別の仕事である。最大化問題で「これより大きい解はない」ことを示すには、すべての解の値を上から抑える量が要る。最大流最小カット定理は、流れの量をカットの容量が上から抑え、しかも最良のカットではちょうど等号になることを主張する。こうして、最大流とそれに等しい容量のカットを並べて示せば、他の候補を 1 つも調べずに最適性が確かめられる。
貪欲法は「今いちばん得なものを取る」手順で、多くの問題では最適解を与えないが、最小全域木のように最適になる問題もある。その違いが、制約の族の「交換」の性質（マトロイドの増加公理）で説明される。
代表的な問題
| 問題 | 実行可能解 | 目的 | 最適性を支える定理 |
|---|---|---|---|
| 最短路 | 2 頂点を結ぶ道 | 辺の長さの和を最小 | 重み付きグラフの最短経路 の定理「Dijkstra 法の正しさ」 |
| 最小全域木 | 全域木 | 辺の重みの和を最小 | 全域木 の定理「Kruskal法の正しさ」、thm-combopt-greedy-matroid |
| 最大マッチング | マッチング | 辺の本数を最大 | マッチング(グラフ理論) の定理「Berge の定理」、prop-combopt-bipartite |
| 最大流 | フロー | 流量を最大 | thm-combopt-maxflow-mincut |
| 最大カット | 頂点の 2 分割 | 横切る辺の本数を最大 | 離散数学 の定理「辺の半分以上を横切る分割」（最適値の半分を保証） |
| 巡回セールスマン | 完全グラフの Hamilton 閉路 | 辺の重みの和を最小 | 実行可能解は $(n-1)!/2$ 個（ex-combopt-brute-force） |
$n$ 頂点の完全グラフ $K_n$ の全域木は $n^{n-2}$ 個ある（Cayleyの公式 の定理「Cayley の公式」）。$n\ge3$ のとき $K_n$ の Hamilton 閉路は $(n-1)!/2$ 個ある。頂点の並べ方 $n!$ 通りのそれぞれが 1 つの Hamilton 閉路を定め、同じ閉路は出発点の選び方 $n$ 通りと向き 2 通りの $2n$ 通りの並べ方から得られる（$n\ge3$ なら 2 つの向きの並べ方は異なる）からである。$n=20$ ではそれぞれ $20^{18}\approx2.6\times10^{23}$ 個、$19!/2\approx6.1\times10^{16}$ 個である。グラフが Hamilton 路をもつかどうかの判定は NP 完全な問題の例であり、一般に効率よく判定する方法は知られていない（Lev §2.4.3, p. 145）。
最大流最小カット定理
ネットワーク $N=(V,A,s,t,c)$ とは、有限集合 $V$ を頂点集合、$A$ を有向辺（弧）の有限集合とするループのない有向グラフ（同じ向きの平行な弧も許す）と、相異なる 2 頂点 $s$（入口）、$t$（出口）、および 容量 $c\colon A\to\mathbb{R}_{\ge0}$ の組である。頂点の集合 $S\subset V$ について、$S$ から出て $V\setminus S$ に入る弧の集合を $\delta^+(S)$、$V\setminus S$ から $S$ に入る弧の集合を $\delta^-(S)$ と書き、$\delta^{\pm}(v):=\delta^{\pm}(\{v\})$、$g(B):=\sum_{a\in B}g(a)$ とする。
- 写像 $f\colon A\to\mathbb{R}$ が フロー であるとは、すべての弧で $0\le f(a)\le c(a)$（容量制約）、$s,t$ 以外のすべての頂点 $v$ で $f(\delta^-(v))=f(\delta^+(v))$（保存則）が成り立つことをいう。$\operatorname{val}(f):=f(\delta^+(s))-f(\delta^-(s))$ を $f$ の 流量 という。流量が最大のフローを 最大流 という。
- $s\in S$、$t\notin S$ となる $S\subset V$ を カット といい、$c(S):=c(\delta^+(S))$ をその 容量 という。容量が最小のカットを 最小カット という。
すべての弧で $0$ をとる写像はフローなので、フローはいつも存在する。カットは有限個なので、最小カットもいつも存在する。
任意のフロー $f$ と任意のカット $S$ について
$$
\operatorname{val}(f)=f(\delta^+(S))-f(\delta^-(S))\le c(S)
$$
が成り立つ。
保存則により、$v\in S\setminus\{s\}$ では $f(\delta^+(v))-f(\delta^-(v))=0$ である（$t\notin S$ に注意）。よって
$$
\operatorname{val}(f)=\sum_{v\in S}\bigl(f(\delta^+(v))-f(\delta^-(v))\bigr)
$$
である。右辺で、両端が $S$ にある弧 $a$ は、始点の項で $+f(a)$、終点の項で $-f(a)$ として現れて打ち消し合う。残るのは $S$ から出る弧の $+f(a)$ と $S$ に入る弧の $-f(a)$ だけなので、右辺は $f(\delta^+(S))-f(\delta^-(S))$ に等しい。容量制約から $f(\delta^+(S))\le c(\delta^+(S))=c(S)$、$f(\delta^-(S))\ge0$ である。$\square$
流量を増やす手がかりは、次の道である。
フロー $f$ について、相異なる頂点の列 $s=v_0,v_1,\dots,v_k$ と弧 $a_1,\dots,a_k$ で、各 $a_i$ が次のどちらかであるものを $f$ の未飽和道 という。
- 順方向の弧：$a_i$ は $v_{i-1}$ から $v_i$ への弧で、$f(a_i)< c(a_i)$。
- 逆方向の弧：$a_i$ は $v_i$ から $v_{i-1}$ への弧で、$f(a_i)>0$。
$v_k=t$ である未飽和道を 増加道（augmenting path）という。
$P$ を $f$ の増加道とし、$\varepsilon>0$ を、順方向の弧の $c(a_i)-f(a_i)$ と逆方向の弧の $f(a_i)$ の最小値とする。$f'$ を、順方向の弧で $f+\varepsilon$、逆方向の弧で $f-\varepsilon$、それ以外の弧で $f$ と定めると、$f'$ はフローで $\operatorname{val}(f')=\operatorname{val}(f)+\varepsilon$ である。
頂点が相異なるので弧 $a_1,\dots,a_k$ も相異なり、$\varepsilon$ の選び方から容量制約は保たれる。内側の頂点 $v_i$（$1\le i\le k-1$）に接する $P$ の弧は $a_i$ と $a_{i+1}$ だけである。両方とも順方向なら、$v_i$ に入る量も出る量も $\varepsilon$ 増える。$a_i$ が順方向で $a_{i+1}$ が逆方向なら、どちらも $v_i$ に入る弧で、一方が $+\varepsilon$、他方が $-\varepsilon$ である。$a_i$ が逆方向で $a_{i+1}$ が順方向なら、どちらも $v_i$ から出る弧で、同様に打ち消す。両方とも逆方向なら、入る量も出る量も $\varepsilon$ 減る。いずれの場合も保存則は保たれる。$s$ に接する $P$ の弧は $a_1$ だけで、順方向なら $s$ から出る量が $\varepsilon$ 増え、逆方向なら $s$ に入る量が $\varepsilon$ 減るので、どちらでも流量は $\varepsilon$ 増える。$\square$
ネットワーク $N$ では最大流が存在し、
$$
\max_f\operatorname{val}(f)=\min_S c(S)
$$
が成り立つ（左辺はフロー全体、右辺はカット全体にわたる）。さらに、フロー $f$ について次は同値である。
(a) $f$ は最大流である。
(b) $f$ の増加道は存在しない。
(c) $\operatorname{val}(f)=c(S)$ となるカット $S$ が存在する。
最大流の存在。 フロー全体の集合 $\Phi\subset\mathbb{R}^A$ は、不等式 $0\le f(a)\le c(a)$ と保存則の等式で定まるので閉集合であり、各成分が $[0,c(a)]$ に入るので有界である。コンパクト空間 の定理「有界閉集合とコンパクト性の一致」により $\Phi$ はコンパクトで、零フローを含むので空でない。$\operatorname{val}$ は一次式なので連続であり、同じ記事の定理「最大値・最小値の存在」により $\Phi$ 上で最大値をとる。
(a)⇒(b)。 増加道があれば、lem-combopt-augment により流量のより大きいフローがあり、$f$ は最大流でない。
(b)⇒(c)。 $f$ の未飽和道で到達できる頂点（$s$ 自身を含む）全体を $S$ とする。増加道がないので $t\notin S$ であり、$S$ はカットである。$a\in\delta^+(S)$ を $u\in S$ から $v\notin S$ への弧とする。$u$ への未飽和道は $S$ の頂点だけを通るので $v$ を通らない。もし $f(a)< c(a)$ なら、その道に $a$ を順方向の弧として付け加えると $v$ への未飽和道になり、$v\notin S$ に反する。よって $f(a)=c(a)$ である。同様に、$a\in\delta^-(S)$ が $v\notin S$ から $u\in S$ への弧なら、$f(a)>0$ だと $a$ を逆方向の弧として付け加えられるので、$f(a)=0$ である。lem-combopt-weak-duality の等式から $\operatorname{val}(f)=c(\delta^+(S))-0=c(S)$ である。
(c)⇒(a)。 任意のフロー $f'$ について、lem-combopt-weak-duality により $\operatorname{val}(f')\le c(S)=\operatorname{val}(f)$ である。
等式。 最大流 $f$ をとると、(a)⇒(b)⇒(c) によりカット $S$ で $\operatorname{val}(f)=c(S)$ となるものがある。lem-combopt-weak-duality によりどのカットの容量も $\operatorname{val}(f)$ 以上なので、$c(S)$ は最小で、両辺は等しい。$\square$
この定理は Ford と Fulkerson による（BM76 Theorem 11.3, p. 198。同書は容量とフローを整数値に限って述べ、増加道による証明を Theorem 11.2, p. 197 で与えている）。最大流と、それと同じ容量のカットを並べて示すことが、最適性の短い証明書になる。
容量がすべて整数のネットワークには、すべての弧で整数値をとる最大流がある。さらに、零フローから始めて、増加道があるかぎり lem-combopt-augment の改善を繰り返すと、高々 $c(\delta^+(s))$ 回で止まり、止まったときのフローは整数値の最大流である。
$f$ が整数値のフローなら、増加道の $\varepsilon$ は正の整数の最小値なので $1$ 以上の整数であり、改善後の $f'$ も整数値である。零フローは整数値なので、手順中のフローはすべて整数値で、流量は 1 回ごとに $1$ 以上増える。一方、カット $\{s\}$ について lem-combopt-weak-duality から流量は $c(\delta^+(s))$ 以下である。よって改善は高々 $c(\delta^+(s))$ 回で、その後は増加道がない。thm-combopt-maxflow-mincut の (b)⇒(a) により、止まったときのフローは最大流である。$\square$
増加道は、$s$ から未飽和道で到達できる頂点を順に印を付けていく探索で、見つかるか、ないことがわかる。ないときには印の付いた頂点の集合が、そのまま thm-combopt-maxflow-mincut の証明の最小カット $S$ になる（KT17 Algorithm 13.11, pp. 268–269）。
頂点 $s,a,b,t$ と、弧 $s\to a$（容量 $3$）、$s\to b$（$2$）、$a\to b$（$1$）、$a\to t$（$2$）、$b\to t$（$3$）からなるネットワークを考える。$f(s\to a)=3$、$f(a\to t)=2$、$f(a\to b)=1$、$f(s\to b)=2$、$f(b\to t)=3$ は、$a$ で入る量 $3$ と出る量 $2+1$、$b$ で入る量 $2+1$ と出る量 $3$ が等しいのでフローで、流量は $5$ である。カット $S=\{s\}$ の容量は $3+2=5$ なので、thm-combopt-maxflow-mincut の (c) によりこれは最大流である。カット $\{s,a\}$（$2+1+2=5$）と $\{s,a,b\}$（$2+3=5$）も最小カットで、$\{s,b\}$ の容量は $3+3=6$ である。最小カットは一意とは限らない。
応用：二部グラフのマッチング
最大流最小カット定理は、ほかの問題をネットワークに置き換えることで多くの最小最大定理を生む。最も基本的な例が二部グラフのマッチングである。グラフ $G$ の 頂点被覆 とは、どの辺も少なくとも一方の端点がそこに入るような頂点の集合のことで、その最小の大きさを $\tau(G)$、マッチング数（最大マッチングの大きさ）を $\nu(G)$ と書く（マッチング(グラフ理論) の定義「辺集合のマッチング」）。
$G$ を二部分割 $(X,Y)$ をもつ有限二部グラフとする。新しい頂点 $s,t$ を加え、弧 $s\to x$（$x\in X$）、辺 $xy\in E(G)$ ごとの弧 $x\to y$（$x\in X$、$y\in Y$）、弧 $y\to t$（$y\in Y$）をすべて容量 $1$ で張ったネットワークを $N_G$ とする。このとき
(1) $N_G$ の最大流の流量は $\nu(G)$ に等しい。
(2) $N_G$ の最小カットの容量は $\tau(G)$ 以上である。
したがって $\nu(G)=\tau(G)$ である。
- マッチング $M$ に対し、$xy\in M$ ごとに $s\to x\to y\to t$ の 3 本の弧で $1$、ほかの弧で $0$ とおくと、$M$ の辺は端点を共有しないので保存則が成り立ち、流量 $\lvert M\rvert$ のフローになる。逆に、thm-combopt-integrality により整数値の最大流 $f$ がとれる。容量が $1$ なので $f$ の値は $0$ か $1$ である。$x\in X$ に入る弧は $s\to x$ だけなので、$x$ から出る弧で値 $1$ のものは高々 1 本であり、同様に $y\in Y$ に入る弧で値 $1$ のものは高々 1 本である。よって値 $1$ の弧 $x\to y$ に対応する辺の集合 $M_f$ はマッチングで、$x$ ごとの保存則から $\operatorname{val}(f)=\sum_xf(s\to x)=\lvert M_f\rvert$ である。以上から最大流の流量は $\nu(G)$ に等しい。
- カット $S$ について、$C:=(X\setminus S)\cup(Y\cap S)\cup\{x\in X\cap S\mid x\text{ はある }y\in Y\setminus S\text{ と隣接する}\}$ とおく。$\delta^+(S)$ は、$x\in X\setminus S$ ごとの弧 $s\to x$、$y\in Y\cap S$ ごとの弧 $y\to t$、$x\in S$、$y\notin S$ となる辺ごとの弧 $x\to y$ からなるので、$c(S)\ge\lvert C\rvert$ である。$C$ は頂点被覆である。辺 $xy$ について、$x\notin S$ なら $x\in C$、$x\in S$ かつ $y\in S$ なら $y\in C$、$x\in S$ かつ $y\notin S$ なら $x\in C$ だからである。よって $c(S)\ge\tau(G)$ である。
最後の主張：thm-combopt-maxflow-mincut と (1)(2) から $\nu(G)=\max\operatorname{val}=\min c(S)\ge\tau(G)$ である。逆に、マッチングの辺は端点を共有しないので、頂点被覆はマッチングの各辺から別々の頂点を含み、$\nu(G)\le\tau(G)$ である。$\square$
$\nu(G)=\tau(G)$ は マッチング(グラフ理論) の定理「二部グラフの最大マッチングと最小頂点被覆」であり、そちらでは交互道を使って証明されている。ここでの証明は、最大流最小カット定理からの帰着である（BM76 Exercise 11.4.2, p. 206 も同じ結論を最大流の議論から導くことを問うている。ネットワークによる二部マッチングの計算は KT17 §14.2, pp. 280–284）。
貪欲法とマトロイド
有限集合 $E$ と部分集合の族 $\mathcal{I}\subset2^E$ の組 $(E,\mathcal{I})$ が 独立系 であるとは、$\emptyset\in\mathcal{I}$ であり、$I\in\mathcal{I}$、$J\subset I$ なら $J\in\mathcal{I}$ であることをいう（マトロイド の定義「マトロイド」の (I1)(I2)）。重み $w\colon E\to\mathbb{R}$ について、$E$ の元を重みの大きい順（等しい重みの順は任意）に $e_1,\dots,e_m$ と並べ、$I_0:=\emptyset$、
$$
I_k:=\begin{cases}I_{k-1}\cup\{e_k\}&(I_{k-1}\cup\{e_k\}\in\mathcal{I}),\\ I_{k-1}&(\text{それ以外})\end{cases}
$$
として $I_m$ を出力する手順を 貪欲法（greedy algorithm）という。
独立系 $(E,\mathcal{I})$ について、次は同値である。
(a) $(E,\mathcal{I})$ はマトロイドである。すなわち増加公理 (I3)「$I,J\in\mathcal{I}$、$\lvert I\rvert<\lvert J\rvert$ ならある $e\in J\setminus I$ で $I\cup\{e\}\in\mathcal{I}$」が成り立つ。
(b) どの重み $w\colon E\to\mathbb{R}_{\ge0}$ についても、貪欲法の出力 $Z$ は $w(Z)=\max_{I\in\mathcal{I}}w(I)$ を満たす。
(a)⇒(b)。 出力を、選ばれた順に $Z=\{g_1,\dots,g_k\}$ とする。並べ方から $w(g_1)\ge\cdots\ge w(g_k)$ である。
まず $Z$ は極大な独立集合である。$Z\cup\{e\}\in\mathcal{I}$ となる $e\notin Z$ があったとすると、$e$ を調べた時点の $I$ は $Z$ の部分集合なので、$I\cup\{e\}\subset Z\cup\{e\}$ も独立であり、$e$ は選ばれたはずだからである。
$J=\{h_1,\dots,h_l\}\in\mathcal{I}$ を、$w(h_1)\ge\cdots\ge w(h_l)$ となるように番号付ける。$l>k$ なら (I3) によりある $e\in J\setminus Z$ で $Z\cup\{e\}\in\mathcal{I}$ となり、$Z$ の極大性に反するので、$l\le k$ である。次に、$i\le l$ のすべてで $w(g_i)\ge w(h_i)$ であることを示す。そうでない最小の $i$ をとり、$A:=\{g_1,\dots,g_{i-1}\}$、$B:=\{h_1,\dots,h_i\}$ とおく。$\lvert A\rvert<\lvert B\rvert$ なので、(I3) によりある $h_j\in B\setminus A$ で $A\cup\{h_j\}\in\mathcal{I}$ となる。$w(h_j)\ge w(h_i)>w(g_i)$ なので、並びの中で $h_j$ は $g_i$ より前にあり、$h_j$ を調べた時点の $I$ は、それまでに選ばれた $g_1,\dots,g_r$（$r\le i-1$）である。$I\cup\{h_j\}\subset A\cup\{h_j\}$ は独立なので $h_j$ は選ばれ、$g_i$ より前に選ばれたので $h_j\in A$ となる。これは $h_j\notin A$ に反する。
重みは $0$ 以上なので、$w(Z)=\sum_{i=1}^kw(g_i)\ge\sum_{i=1}^lw(g_i)\ge\sum_{i=1}^lw(h_i)=w(J)$ である。
(b)⇒(a)。 (I3) が成り立たないとし、$I,J\in\mathcal{I}$、$p:=\lvert I\rvert<\lvert J\rvert=:q$ で、どの $e\in J\setminus I$ についても $I\cup\{e\}\notin\mathcal{I}$ とする。$\varepsilon:=\frac1{2(p+1)}$ とし、$w$ を $I$ の元で $1+\varepsilon$、$J\setminus I$ の元で $1$、それ以外で $0$ と定める。貪欲法はまず $I$ の元を調べ、$I$ の部分集合はすべて独立なので $I$ の元をすべて選ぶ。次に重み $1$ の $J\setminus I$ の元を調べるが、その時点の集合は $I$ で、$I\cup\{e\}\notin\mathcal{I}$ なのでどれも選ばない。残りの元は重み $0$ である。よって $w(Z)=p(1+\varepsilon)=p+\frac{p}{2(p+1)}< p+1$ である。一方 $w(J)\ge q\ge p+1$ なので、$Z$ は最適でなく、(b) に反する。$\square$
グラフ $G$ の辺集合 $E$ と、閉路を含まない辺の部分集合の族はマトロイドである（マトロイド の命題「グラフ的マトロイド」）。連結グラフでは極大な独立集合は全域木であり、十分大きい定数 $M$ について重みを $M-w(e)\ge0$ に替えれば、thm-combopt-greedy-matroid から、重みの小さい順に閉路を作らない辺を取る Kruskal 法が最小全域木を与えることが従う（全域木 の定理「Kruskal法の正しさ」では直接証明されている）。
道 $v_1v_2v_3v_4$ の辺 $e_1=v_1v_2$、$e_2=v_2v_3$、$e_3=v_3v_4$ に重み $2,3,2$ を与え、マッチング全体を $\mathcal{I}$ とする。$\mathcal{I}$ は独立系である。貪欲法はまず $e_2$ を選び、その後 $e_1,e_3$ はどちらも $e_2$ と端点を共有するので選べず、出力の重みは $3$ である。最適解は $\{e_1,e_3\}$ で重み $4$ である。実際、$I=\{e_2\}$、$J=\{e_1,e_3\}$ は (I3) を破っている。満たす性質は「独立系」、満たさない性質は「増加公理」で、thm-combopt-greedy-matroid の (a) が成り立たないので (b) も成り立たない。
反例：条件を外すと崩れること
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| 増加公理 (I3) | 道の 3 辺に重み $2,3,2$、制約はマッチング（ex-combopt-greedy-matching） | 貪欲法の出力が最適 |
| 重みが $0$ 以上 | $E=\{e\}$、$\mathcal{I}=\{\emptyset,\{e\}\}$、$w(e)=-1$ | 貪欲法の出力が最適 |
| 逆方向の弧の利用 | 菱形のネットワーク | 「改善できなければ最大流」 |
| 容量が整数 | 容量 $\frac12$ の弧 1 本 | 整数値の最大流の存在 |
| 二部グラフ | 三角形 $K_3$ | $\nu(G)=\tau(G)$ |
- $E=\{e\}$、$\mathcal{I}=\{\emptyset,\{e\}\}$ はマトロイドである。$w(e)=-1$ なら貪欲法は $\{e\}$ を出力し重みは $-1$ だが、$\emptyset$ の重みは $0$ である。thm-combopt-greedy-matroid の (b) は重みが $0$ 以上のときの主張で、この仮定は外せない。
- 頂点 $s,a,b,t$、弧 $s\to a$、$s\to b$、$a\to b$、$a\to t$、$b\to t$（容量はすべて $1$）のネットワークで、$s\to a\to b\to t$ に $1$ を流す。このあと、順方向の弧だけからなる増加道はない（$s\to a$ と $b\to t$ が満杯で、$s\to b$ の先の $b$ から出る弧も $b\to t$ だけである）。しかし流量 $1$ は最大でない。逆方向の弧 $a\to b$ を使った増加道 $s\to b\leftarrow a\to t$ で改善すると、$s\to a\to t$ と $s\to b\to t$ に $1$ ずつの流量 $2$ のフローになり、カット $\{s\}$ の容量 $2$ に等しいので最大流である。def-combopt-augmenting で逆方向の弧を許さないと、thm-combopt-maxflow-mincut の (b)⇒(a) が成り立たなくなる。
- 弧 $s\to t$ が 1 本で容量 $\frac12$ なら、最大流の流量は $\frac12$ で、整数値の最大流はない。thm-combopt-integrality は容量が整数であることを使っている。
- 三角形 $K_3$ は二部グラフでなく、$\nu(K_3)=1$ だが $\tau(K_3)=2$ である（マッチング(グラフ理論) の例「反例：二部性・偶数頂点・有限性」）。prop-combopt-bipartite のネットワークは二部分割がなければ作れない。
補足：線形計画と計算量
最大流問題は、フローの各弧の値を変数とし、容量制約と保存則を一次の制約とする線形計画問題の特別な場合である。整数の係数の線形計画問題では一般に整数の最適解があるとは限らないが、ネットワークの最大流は容量が整数なら整数の最適解をもつ（KT17 §13.6, pp. 273–274。thm-combopt-integrality はその証明を与える）。
組合せ最適化の問題は、効率のよい解法の有無で大きく 2 つに分かれる。最短路、最小全域木、二部グラフの最大マッチングは、重み付きグラフの最短経路、全域木、上の prop-combopt-bipartite の手順のように、入力の大きさに応じた手数で最適解が求まる。一方、巡回セールスマン問題は Hamilton 閉路の有無の判定を含む。グラフ $G$ の辺に重み $1$、それ以外の頂点の対に重み $2$ を与えた $K_n$ の巡回セールスマン問題の最適値が $n$ になるのは、$G$ が Hamilton 閉路をもつときに限るからである。Hamilton 路の有無の判定は NP 完全な問題の例である（ex-combopt-brute-force）。そのような問題では、最適値の一定倍を保証する近似の手順が研究される。最も簡単な例は、離散数学 の定理「辺の半分以上を横切る分割」の証明に現れる、頂点を 1 つずつ動かす手順である。
関連項目
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
