Rado–Edmondsの定理(Rado–Edmonds theorem)とは、有限集合上の独立系について、それがマトロイドであることと、すべての正の重みに対し貪欲法の出力が重み最大の独立集合であることが同値だという定理である。証明は、貪欲法の出力が各段で極大な独立集合であることと、Abel の総和法による重みの比較による。独立系一般では、貪欲法の出力の重みは最大値の階数商倍以上で、階数商が 1 であることとマトロイドであることは同値である。
重みの大きいものから順に、制約を満たす限り採用していく。この貪欲法(貪欲アルゴリズム)がどんな重みでも最適解を返す独立系は、ちょうどマトロイドである。Rado–Edmondsの定理はこの同値を述べるもので、マトロイドの公理は「貪欲法が正しく動く条件」として最適化の側から再発見できる。
組合せ最適化 には同じ主張の短い形がある。この記事では、量化を正の重みと「ある順」まで弱めた形で証明し、独立系一般での貪欲法の出来を測る階数商の定理と、マトロイド多面体の記述までを扱う。
$E$ を有限集合とする。$\mathcal I\subset2^E$ が空でなく、部分集合をとる操作で閉じているとき、$(E,\mathcal I)$ を 独立系 といい、$\mathcal I$ の元を独立集合という。マトロイド は マトロイド の通り、さらに
$$ \lvert I\rvert< \lvert J\rvert\ \Longrightarrow\ \text{ある }e\in J\setminus I\text{ で }I+e\in\mathcal I $$
をみたす独立系である(これを増加公理とよぶ)。
独立系 $(E,\mathcal I)$ と重み $w\colon E\to\mathbb{R}_{\ge0}$ に対し、$E$ を $w(e_1)\ge\dots\ge w(e_m)$ と並べる(等しい重みの順は 1 つ選ぶ)。$Z_0=\emptyset$ とし、$Z_{i-1}+e_i\in\mathcal I$ なら $Z_i=Z_{i-1}+e_i$、そうでなければ $Z_i=Z_{i-1}$ とする。$Z:=Z_m$ を 貪欲法の出力 という。
以下 $w_k:=w(e_k)$、$w_{m+1}:=0$、$E_k:=\{e_1,\dots,e_k\}$ とする。証明の全部は次の 2 つの事実で動く。
どの独立系でも、どの $k$ についても $Z\cap E_k$ は $E_k$ の中で極大な独立集合である。
$j\le k$ で $e_j\notin Z$ とする。$e_j$ が捨てられた理由は $Z_{j-1}+e_j\notin\mathcal I$ である。$Z_{j-1}\subset Z\cap E_k$ なので、独立系が部分集合で閉じていることから $(Z\cap E_k)+e_j\notin\mathcal I$ である。$\square$
どの部分集合 $S\subset E$ についても、Abel の総和法から
$$ w(S)=\sum_{k=1}^m(w_k-w_{k+1})\,\lvert S\cap E_k\rvert $$
であり、右辺の係数はすべて $0$ 以上である。
つまり重みの比較は、$E_k$ のそれぞれの段で「$S$ が何個取っているか」の比較に帰着する。
独立系 $(E,\mathcal I)$ について、次は同値である。
(a) $(E,\mathcal I)$ はマトロイドである。
(b) すべての重み $w\colon E\to\mathbb{R}_{\ge0}$ と、等しい重みのすべての並べ方について、貪欲法の出力は $\mathcal I$ の中で重み最大である。
(c) すべての正の重み $w\colon E\to\mathbb{R}_{>0}$ について、等しい重みのある並べ方で、貪欲法の出力は $\mathcal I$ の中で重み最大である。
(a) から (b):$I\in\mathcal I$ を任意に取る。マトロイドでは マトロイド の補題「極大な独立部分集合の大きさ」により、$E_k$ の中の極大な独立集合の大きさはすべて階数 $r(E_k)$ に等しい。lem-maximal-in-level から $\lvert Z\cap E_k\rvert=r(E_k)\ge\lvert I\cap E_k\rvert$ である。fml-abel の両辺を比べて $w(Z)\ge w(I)$ を得る。
(b) から (c) は明らかである。
(c) から (a):マトロイドでないとして、(c) が成り立たない重みを作る。増加公理が成り立たないので、独立集合 $Y,X$ で $\lvert Y\rvert< \lvert X\rvert$ かつ、どの $e\in X\setminus Y$ についても $Y+e\notin\mathcal I$ となるものがある。$X$ の元を減らして $\lvert Y\rvert=k$、$\lvert X\rvert=k+1$ としてよい。
$\delta>0$ を $\delta\lvert E\rvert< 1$ となるように取り、
$$ w(e)=\begin{cases}k+2&(e\in Y)\\ k+1&(e\in X\setminus Y)\\ \delta&(\text{その他})\end{cases} $$
とする($\delta< k+1$ なので順は階段の通りになる)。どの並べ方でも貪欲法はまず $Y$ を全部採用し、次に $X\setminus Y$ を全部捨てるから
$$ w(Z)\le k(k+2)+\delta\lvert E\rvert< (k+1)^2\le w(X) $$
である。よって出力は重み最大でない。$\square$
(c) から (a) で作った重みは 3 段の階段である。$\delta$ を 0 にできれば話は簡単だが、(c) は正の重みに限っているので、$\delta$ の小ささで処理している。主張の形は Oxl03 Theorem 4.8 が正の重みで、LR82 Theorem 1 が Rado の名で述べる。歴史的には、DW22 の整理では、マトロイドなら最適という向きを Rado に、逆向きを Edmonds に帰している(Edm71)。上の証明は階段の和による形に書き直したものである。
マトロイドと $w\colon E\to\mathbb{R}$ について:
(1) $w$ の大きい順に貪欲法を走らせると、基の中で重み最大のものが得られる。
(2) $w(e)>0$ の元だけで貪欲法を走らせると、独立集合の中で重み最大のものが得られる。
マトロイドでなければ貪欲法は間違えるが、どのくらい間違えるかは 1 つの数で測れる。
$A\subset E$ の中の極大な独立集合の大きさの最小を $\mathrm{lr}(A)$、最大を $\mathrm{ur}(A)$ とする。独立系の 階数商 を
$$ q:=\min_{\mathrm{ur}(A)>0}\frac{\mathrm{lr}(A)}{\mathrm{ur}(A)}\quad(\mathcal I=\{\emptyset\}\text{ のときは }q:=1) $$
と定める。
どの独立系、どの $w\ge0$、どの並べ方についても $w(Z)\ge q\cdot\max_{I\in\mathcal I}w(I)$ である。また $\mathcal I\ne\{\emptyset\}$ なら、等号が成り立ち最大値が正である $w$ と並べ方がある。とくに $q=1$ であることと、マトロイドであることは同値である。
$I$ を重み最大の独立集合とする。lem-maximal-in-level と $q$ の定義から
$$ \lvert Z\cap E_k\rvert\ge\mathrm{lr}(E_k)\ge q\,\mathrm{ur}(E_k)\ge q\,\lvert I\cap E_k\rvert $$
なので、fml-abel から $w(Z)\ge q\,w(I)$ である。ここで $\mathrm{ur}(E_k)=0$ のときは両端が 0 である。
等号を達成するには、$q=\mathrm{lr}(A)/\mathrm{ur}(A)$ となる $A$ を取り、$A$ の上で $w=1$、外で $w=0$ とする。大きさ $\mathrm{lr}(A)$ の極大な独立集合 $L\subset A$ の元を先頭に、続いて $A$ の残り、最後に $A$ の外を並べる。出力の $A$ の部分は $L$ なので $w(Z)=\mathrm{lr}(A)$、最大値は $\mathrm{ur}(A)$ である。
最後の主張を示す。増加公理があれば同じ $A$ の中の極大な独立集合の大きさは等しいので $q=1$ である。逆に増加公理を満たさない $Y,X$ があれば、$A:=X\cup Y$ で $Y$ を含む極大な独立集合は $Y$ 自身なので $\mathrm{lr}(A)< \mathrm{ur}(A)$ である。$\square$
DW22 は、近似比が $1/q$ 以下であること(上の不等式)を Jenkyns に、それが改善できないこと(等号)を Korte–Hausmann に帰している。$q=1$ の場合は主定理の (a) と (b) の同値を含む。
$E$ 上のマトロイド $\mathcal I_1,\dots,\mathcal I_p$ の共通部分 $\mathcal I=\bigcap_i\mathcal I_i$ は独立系で、$q\ge1/p$ をみたす。
$J$ を $A$ の中で極大な $\mathcal I$ の独立集合、$I\subset A$ を $\mathcal I$ の独立集合とする。$\lvert I\rvert\le p\lvert J\rvert$ を示せばよい。$S_i:=\{e\in I\setminus J:J+e\notin\mathcal I_i\}$ とおくと、$J$ の極大性から $\bigcup_iS_i=I\setminus J$ である。
$\mathcal I_i$ の中で、$J$ は $J\cup S_i$ の極大な独立集合である。$(I\cap J)\cup S_i\subset I$ も $\mathcal I_i$ で独立で $J\cup S_i$ に含まれるので、マトロイドの極大な独立集合の大きさの一定性から $\lvert I\cap J\rvert+\lvert S_i\rvert\le\lvert J\rvert$、つまり $\lvert S_i\rvert\le\lvert J\setminus I\rvert$ である。和をとって $\lvert I\setminus J\rvert\le p\lvert J\setminus I\rvert$ を得るから
$$ \lvert I\rvert=\lvert I\cap J\rvert+\lvert I\setminus J\rvert\le\lvert I\cap J\rvert+p\lvert J\setminus I\rvert\le p\lvert J\rvert. \quad\square $$
二部グラフ の マッチング(グラフ理論) は、左の頂点ごとに辺を 1 本までとする分割マトロイドと、右の頂点についての分割マトロイドの共通部分である。したがって $q\ge1/2$ である。3 辺の道 $a,b,c$($b$ が真ん中)では、$A=E$ の極大な独立集合は $\{b\}$ と $\{a,c\}$ なので $q=1/2$ で、等号が成り立つ。
重みを $w(a)=w(c)=2$、$w(b)=3$ とすれば貪欲法の出力は $\{b\}$ で重み 3、最適は $\{a,c\}$ で重み 4 である。重みをすべて 1 にして $b$ を先頭に置けば比はちょうど $1/2$ になる。
$E=\{e_0,e_1,\dots,e_n\}$ とし、独立集合を $\{e_0\}$ と $\{e_1,\dots,e_n\}$ の部分集合に限る。$A=E$ の極大な独立集合の大きさは 1 と $n$ なので $q=1/n$ である。重みを $w(e_0)=1+\varepsilon$、ほかを 1 とすると貪欲法は $1+\varepsilon$ しか取れず、最大値は $n$ である。
階段の和は 線形計画法 の双対解そのものである。マトロイドの階数関数 $r$ について
$$ P:=\{x\in\mathbb{R}^E_{\ge0}: x(A)\le r(A)\ \ (A\subset E)\},\qquad x(A):=\sum_{e\in A}x_e $$
とおく。
$P$ は独立集合の指示ベクトル $\mathbf 1_I$($I\in\mathcal I$)の凸包に等しく、これらは $P$ の頂点のすべてである。さらに $w\ge0$ に対し $\max_{x\in P}w\cdot x=w(Z)$ である。
$\mathbf 1_I\in P$ は $\lvert I\cap A\rvert\le r(A)$ からである。$w\ge0$ と $x\in P$ について、fml-abel と同じ変形で
$$ w\cdot x=\sum_k(w_k-w_{k+1})\,x(E_k)\le\sum_k(w_k-w_{k+1})\,r(E_k)=w(Z) $$
である。最後の等号は $\lvert Z\cap E_k\rvert=r(E_k)$ による。$\mathbf 1_Z\in P$ なので最大値は $w(Z)$ である。
一般の実数の $w$ については、$w\cdot x\le w^+\cdot x\le w^+(Z)$ であり、$Z':=Z\cap\{w>0\}$ で $w\cdot\mathbf 1_{Z'}=w^+(Z)$ である。よってどの $w$ についても $P$ 上の最大値はある $\mathbf 1_I$ で達成される。$P$ が凸包より真に大きければ、分離する $w$ でこれに矛盾するので、$P$ は凸包に等しい。
各 $\mathbf 1_I$ が頂点であることは、$I$ の上で $+1$、外で $-1$ の $w$ を取ると $w\cdot\mathbf 1_J=\lvert J\cap I\rvert-\lvert J\setminus I\rvert\le\lvert I\rvert$ で、等号が $J=I$ に限ることから分かる。$\square$
$y_{E_k}:=w_k-w_{k+1}$(他の $A$ では $y_A:=0$)は双対問題の許容解で、その目的関数の値は $\sum_ky_{E_k}r(E_k)=w(Z)$ である。最適性の証明書が貪欲法の走りから自動で出てくる点が、多面体 の側から見たこの定理の中身である。
| 外す仮定 | 例 | 起きること | 種類 |
|---|---|---|---|
| 増加公理 | 道のマッチング(ex-matching) | (b) が偽 | 主張が成り立たない |
| 部分集合で閉じること | ex-non-hereditary | 増加公理があっても貪欲法が失敗 | 主張が成り立たない |
| 重みが非負 | 1 元のマトロイドと重み $-1$ | 貪欲法の出力が最適でない | 主張が成り立たない |
| (c) の「すべての重み」 | 1 つの重みだけに限る(ex-one-weight) | マトロイドでなくても最適 | 主張が成り立たない |
$E=\{1,2\}$、$\mathcal I=\{\emptyset,\{1\},\{1,2\}\}$ とする。増加公理はみたされるが $\{2\}\notin\mathcal I$ である。$w(2)=2$、$w(1)=1$ とすると、貪欲法は先に $2$ を見て捨て、次に $1$ を取って止まる。出力の重みは 1 で、最大は $\{1,2\}$ の 3 である。独立系という前提を外すと (a) ならば (b) という含意が成り立たない。
$E=\{e\}$、$\mathcal I=2^E$ はマトロイドである。$w(e)=-1$ とすると、同じ手順の貪欲法は $e$ を取り重み $-1$ を返すが、最大は $\emptyset$ の $0$ である。cor-real-weights の (2) が正の元だけで走らせるのはこのためである。
ex-matching の道はマトロイドでないが、重み $w(a)=w(c)=3$、$w(b)=1$ では貪欲法は $\{a,c\}$ を返して最適である。また重みがすべて 1 のとき、$a,c$ を先に並べれば最適で、$b$ を先に並べると最適でない。定理の (c) で全部の正の重みを動かしているのは本質的である。
ナップサック問題 の可能な解の族は独立系だが、一般にはマトロイドでない。大きさ 3 の品物 1 個と大きさ 2 の品物 2 個、容量 4 なら、極大な解の大きさは 1 と 2 である。こうした問題では貪欲法は 近似アルゴリズム の出発点にとどまる。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する