マトロイドと貪欲アルゴリズム

$|I|<|J|$と仮定する。このとき、マトロイドの定義よりある$x\in J\setminus I$で$I\cup\{x\}\in\mathcal{I}$となるものが存在する。これは$I$が極大であることに矛盾する。

貪欲アルゴリズムによって得られた解が最適解ではないと仮定する。
貪欲アルゴリズムによって得られる独立集合を$S$とする。また、最適解を$T$とする。このとき、$S$は貪欲アルゴリズムの定め方より独立集合であり、$c$は非負なので$T$は独立である。よって、$|S|=|T|(=n\text{とする})$である。$S$に含まれる$E$の元をコスト関数の値が大きい順に$s_1,\,\dots,\,s_n$とし、同様に$t_1,\,\dots,\,t_n$を定める。貪欲アルゴリズムの定め方より、$s_1,\,\dots,\,s_n$はこの順に$S$に追加されたことがわかる。仮定より$\sum_{i=1}^nc(s_i)<\sum_{i=1}^nc(t_i)$なので、ある$1\leq j\leq n$が存在して$c(s_1)\geq c(t_1),\,\dots,\,c(s_{j-1})\geq c(t_{j-1})$かつ$c(s_j)< c(t_j)$である。$S_{j-1}=\{s_1,\,\dots,\,s_{j-1}\},\ T_{j}=\{t_1,\,\dots,\,t_j\}$とする。このとき、マトロイドの定義よりある$t\in T_{j}\setminus S_{j-1}$が存在して$S_{j-1}\cup\{t\}\in\mathcal{I}$である。このとき、$c(t)\geq c(t_j)\geq c(s_j)$となる。貪欲アルゴリズムにおいて$S_{j-1}$に次に追加された$E$の元は$s_j$であったが、これは$S_{j-1}$に追加しても独立集合となる$E\setminus S_{j-1}$の元のうちコスト関数の値が最大であるものではなく、アルゴリズムの定め方に反し矛盾する。
よって、貪欲アルゴリズムにより最適解が求まる。

独立性システム$(E,\mathcal{I})$がマトロイドではないと仮定する。
このとき独立集合$I,\,J$で、$|I|<|J|$かつ全ての$x\in J\setminus I$について$I\cup\{x\}\notin\mathcal{I}$となるものがとれる。また、$\varepsilon$を$\varepsilon<\frac{|I|}{|J|}-1$なる正の数とする。このとき、以下のような重みを考える。
\begin{equation} c(x)=\left\{ \begin{array}{ll} 1+\varepsilon & x\in I\\ 1 & x \in J\setminus I\\ 0 & else \end{array} \right. \end{equation}
このとき、独立アルゴリズムによって選ばれる集合は$I$だが、$\sum_{x\in I}c(x)=|I|(1+\varepsilon)<|J|=\sum_{x\in J}c(x)$となり、貪欲アルゴリズムによって最適解が求められることに矛盾。
よって、$(E,\mathcal{I})$はマトロイドである。