マトロイドの最小基問題に対する貪欲アルゴリズムの正当性を示します。
「離散数学のすすめ」という本のマトロイドの章(詳しく証明が書いていない…)を、行間を補完して自分の言葉に書き直しています。
マトロイドとその貪欲アルゴリズムについて軽く知っている前提です。
定義
有限集合$E$とその部分集合族$\mathcal{I} \subseteq 2^E$(冪集合)が以下の(I0)〜(I2)を満たすとき、$M = (E, \mathcal{I})$をマトロイドという。
(I0) $\emptyset \in \mathcal{I}$
(I1) $I \subseteq J \in \mathcal{I} \Longrightarrow I \in \mathcal{I}$
(I2) $I, J \in \mathcal{I}, |I| < |J| \Longrightarrow \exists e \in J \setminus I, I \cup \{e\} \in \mathcal{I}$
マトロイド$M = (E, \mathcal{I})$の$\mathcal{I}$を、独立集合族と呼び、その要素を独立集合という。
独立集合のうち極大なものを基という。
最小基問題
マトロイド$M = (E, \mathcal{I})$と重み関数$w: E \rightarrow \mathbb{R}$に対して、$w(B) = \sum_{e \in B} w(e)$を最小にする基$B$を求める問題。
$E$を辺集合、$\mathcal{I}$を森集合としてあげると最小全域木問題になる。
最小基問題に対する貪欲アルゴリズム
- $I$を空集合、$S$を$E$とする。
- $S$を$w$で昇順に並び替え、$S_1, S_2, \dots, S_{|S|}$とする。
- $i=1, 2, \dots, |S|$について、4を順に行う。
- $I \cup \{S_i\}$が独立集合なら$I$に加える。
終了時の$I$が最小基となっている。
補題1
マトロイド$M=(E, \mathcal{I})$の基の要素数はすべて同じ。
(証明)
ある基$I, J$が存在して$|I| \neq |J|$と仮定する。$|I| < |J|$として一般性を失わない。
このとき(I2)より、ある$e$が存在して$|I| < |I \cup \{e\}|$となる。これは$I$が極大であることに矛盾する。
補題2
要素数$k$の独立集合のうち、$w(I)$を最小にする$I \in \mathcal{I}$を$I_k$とする。$I_{k+1}$が存在するならば、ある$e \in I_{k+1} \setminus I_{k}$が存在して$I_k \cup \{e\} \in \mathcal{I}, w(I_k \cup \{e\}) = w(I_{k+1})$を満たす。
(証明)
(I2)より、ある$e \in I_{k+1} \setminus I_{k}$が存在して$I_k \cup \{e\} \in \mathcal{I}$である。この$e$が$w(I_k \cup \{e\}) = w(I_> {k+1})$を満たすことを示す。
まず、$I_{k+1}$の最小性より$w(I_{k+1}) \leq w(I_k \cup \{e\})$である。
また、(I1)より$I_{k+1} \setminus \{e\}$は要素数$k$の独立集合である。したがって、$I_k$の最小性より、$w(I_{k+1}) = w(I_{k+1} \setminus \{e\}) + w(e) \geq w(I_k) + w(e) = w(I_k \cup \{e\})$。
以上より$w(I_k \cup \{e\}) = w(I_{k+1})$。
正当性の証明
貪欲アルゴリズムは以下のようなアルゴリズムで、最終的に$I$が最小基として得られるというものでした。
- $I$を空集合、$S$を$E$とする。
- $S$を$w$で昇順に並び替え、$S_1, S_2, \dots, S_{|S|}$とする。
- $i=1, 2, \dots, |S|$について、4を順に行う。
- $I \cup \{S_i\}$が独立集合なら$I$に加える。
まず$I$は常に、$I$と要素数が同じ独立集合の中で最小の独立集合である(=Aとします)ことを示します。
(証明)
はじめ$I$は空集合で、(I0)より独立集合なのでAを満たす。
ステップ4を実行する直前に$I$がAを満たすと仮定する。
ステップ4で$S_i$を加えるとき、$S_i$は、$I$の要素でなく$I \cup \{S_i\}$が独立集合であるような最小の$S$の要素の一つである。 そうでないとき、すなわち$S_j (j < i)$が存在して$I \cup \{S_j\}$が独立集合のとき、(I0)より$i = j$のときの$I$についても$I \cup \{S_j\}$は独立> 集合であるから、ステップ4で$I$に加えられているはずであり、矛盾する。
したがって、$S_i$を加えるとき、補題2で$w(I \cup \{S_i\}) = w(I) + w(S_i) \leq w(I) + w(e) = w(I_{|I|+1})$となり、ステップ4実行直後も$I$はAを満たす。$S_i$が$I$に加えられないときも明らかにAを満たすので、ステップ4実行直後も$I$はAを満たす。
以上より帰納的に$I$は常にAを満たす。
補題1より、あとは終了時に$I$が基であることを示せば十分です。
基は極大な独立集合で、独立集合であることは示したので、極大でないと仮定して矛盾を導きます。
(証明)
終了時の$I$が極大でない、すなわち、ある独立集合$K$が存在して$I \subseteq K$と仮定する。
このとき、(I2)よりある独立集合$J$と$e \not\in I$が存在して$J = I \cup \{e\}$かつ$J \subseteq K$を満たす。 ステップ2で$e$が$S_k$と番号をつけられたとき、(I1)より$i=k$のときステップ4の直前で$I \cup \{e\}$は独立集合であり、ステップ4で$I$に追加されているはずである。 したがって$e \not\in I$に矛盾する。
以上から示せました。