マトロイドによるクラスカル法の正当性の証明

はじめに
この記事でやること
注意点
（前半）マトロイドと貪欲法
（後半）マトロイドのクラスカル法への適用
- ベクトルマトロイド
  - 【命題 2.1.1】
- グラフのマトロイド
おわりに
参考文献

はじめに

クラスカル法を知っていますか？私は知ってます。

最小全域木問題の解法として知られるアルゴリズムで、重みの昇順に閉路ができないよう辺を追加していくだけで最小全域木になりますよ～という、貪欲法で最適解が得られる稀有（？）な例です。基本的に、貪欲法は「局所最適解に嵌ってしまう」という弱点があるのですが、クラスカル法は帰納法（wikiのやつ）によって正当性が証明できます。

しかし、貪欲法が使えるかどうかを問題ごとに一々考えるのは大変です。そこで考えられた貪欲法が使える指標の一つが「マトロイド」と呼ばれる構造です。

もし「全域木がマトロイドだからクラスカル法は正しい」と雑に説明できてしまうと、とても楽ですよね。というわけで、これをやります。*1

この記事でやること

離散最適化問題において貪欲法が使える「マトロイド」という構造について、クラスカル法の正当性の証明を目標に解説します。
記事の前半ではマトロイドの定義と貪欲法との関係とその証明、後半ではクラスカル法にマトロイドを適用する方法の説明となります。これら説明を最短で行うため、具体例をほぼほぼ出さずに定義→命題→証明の流れで突き進みます。
あくまでもクラスカル法に関する話を目標に定めているため、マトロイドについてのほんの一部分にしか触れておりません（もちろん証明は厳密に書いているつもりです）。ですので、本記事を読んでマトロイドに興味を持たれた方は是非ご自身で色々調べてみることをお勧めします。

注意点

ちょっぴり線形代数の知識がいります。（線形独立とか次元とかが何かわかっていれば十分のはず…。）
グラフに単純性を仮定しません。（すなわち、多重辺・自己ループの存在を認めます。）

（前半）マトロイドと貪欲法

マトロイドの定義

【定義 1.1.1】*2

【定義 1.1.1】（独立性システム、マトロイド）
$E: 非空な有限集合, \mathcal{F}: E の部分集合族$ とする。
$\mathcal{F}$ が次の2条件を満たすとき、 $\mathcal{F}$ は $E$ の独立性システムと言う:

$\emptyset \in \mathcal{F}$
$X \in \mathcal{F}, Y \subseteq X \Rightarrow Y \in \mathcal{F}$

さらに、次の条件も満たすとき、 $\mathcal{F}$ は $E$ のマトロイドと言う:

$X, Y \in \mathcal{F}, |X| \gt |Y| \Rightarrow \exists e \in X \setminus Y : Y \cup e \in \mathcal{F}$

※以下、マトロイドに対しては $\mathcal{F}$ のかわりに主に $\mathcal{I}$ を使うこととします。

マトロイドに関する用語

【定義 1.2.1】

【定義 1.2.1】（独立集合、従属集合）
$E: 非空な有限集合, \mathcal{I}: E のマトロイド$ とする。
$X \subseteq E$ について

$X: （\mathcal{I}の）独立集合 : \underset{\text{def}}{\Leftrightarrow} X \in \mathcal{I}$
$X: （\mathcal{I}の）従属集合 : \underset{\text{def}}{\Leftrightarrow} X \notin \mathcal{I}$

【定義 1.2.2】

【定義 1.2.2】（基、サーキット）
$E: 非空な有限集合, \mathcal{I}: E のマトロイド$ とする。
$B \in \mathcal{I}, C \in 2^{E} \setminus \mathcal{I}$ について

$B: （\mathcal{I}の）基: \underset{\text{def}}{\Leftrightarrow} B: \mathcal{I}において極大$
$C: （\mathcal{I}の）サーキット: \underset{\text{def}}{\Leftrightarrow} 2^{E}\backslash \mathcal{I}において極小$

【定義 1.2.3】

【定義 1.2.3】（集合の基）
$E: 非空な有限集合, \mathcal{I}: E のマトロイド, X \subseteq E$ とする。
このとき、 $\exists B_X \subseteq X: B_X \in \mathcal{I} かつ \forall e \in X \setminus B_X, B_X \cup \{e\} \notin \mathcal{I}$
この $B_X$ を $X$ の基と呼ぶ。

※【定義 1.2.2】の「基」とは異なる概念であることに注意してください。

存在性は簡単に示せます。

$\mathcal{F} := \{Y \subseteq X \mathrel{|} Y \in \mathcal{I} \}$ としたときに $\emptyset \in \mathcal{F}$ より $\mathcal{F} \neq \emptyset$ であることに注意して、 $B_X$ として $\mathcal{F}$ の中で最大のものを取ればよいです。

特に、 $X \in \mathcal{I}$ のとき $B_X = X$ となります。

【定義 1.2.4】

【定義 1.2.4】（階数関数）
$E: 非空な有限集合, \mathcal{I}: E のマトロイド$ とする。
関数 $r: 2^E \to \mathbb{N}_{\ge 0}; X \mapsto r(X)$ を
\begin{align} r(X) := \text{max} \{ |Y| \mathrel{|} Y \subseteq X, Y \in \mathcal{I} \} \end{align}と定め、これを（ $\mathcal{I}$ の）階数関数と呼ぶ。

つまり、 $r(X)$ は $X$ の基のサイズのことです。集合の基のサイズは一意であるため、well-definedです。

【命題 1.2.5】*3

【命題 1.2.5】
$E: 非空な有限集合, \mathcal{I}: E のマトロイド, r: 階数関数$ について、以下が成立：

$X \subseteq E \Rightarrow r(X) \le |X|$
$X \in \mathcal{I} \Leftrightarrow r(X) = |X|$
$X \subseteq Y \subseteq E \Rightarrow r(X) \le r(Y)$

直感的に明らかだと思うので、証明略*4

マトロイドと貪欲法

はじめにざっくりと「貪欲法が使える」と述べましたが、これを正しく定式化しておきます。

【定義 1.3.1】

【定義 1.3.1】（最大独立集合問題）
$E: 非空な有限集合, \mathcal{F}: E の独立性システム$ とする。
与えられた重み関数 $w: E \to \mathbb{R}_{\ge 0}$ に対し、
$\sum_{e \in X} w(e)$ が最大となる $X \in \mathcal{F}$ を見つける最適化問題を最大独立集合問題と呼ぶ。

※例えば「01ナップサック問題」や「最大マッチング問題」などは、最大独立集合問題として表現できます。（ $\mathcal{F}$ をうまく定義してあげればよいです。）

【定義 1.3.2】

【定義 1.3.2】（最小基問題）
$E: 非空な有限集合, \mathcal{F}: E の独立性システム$ とする。
与えられた重み関数 $w: E \to \mathbb{R}_{\ge 0}$ に対し、
$\sum_{e \in X} w(e)$ が最小となる極大な $X \in \mathcal{F}$ を見つける最適化問題を最小基問題と呼ぶ。

※「最小全域木問題」は最小基問題として表現できます。

これら問題に対し、貪欲法を疑似コードで表現します。

【定義 1.3.3】

【定義 1.3.3】（最大独立集合問題に対する貪欲法）
$E := \{ e_{1}, \dots, e_{n} \}, \mathcal{F}: E の独立性システム, w: E \to \mathbb{R}_{\ge 0}: 重み関数$
による最大独立集合問題について、（必要があれば適切に並び替えて） $w(e_{1}) \ge \dots \ge w(e_{n})$ としたとき、貪欲法を以下のアルゴリズムで定義する：

$X \gets \emptyset$
1. $\text{if } X \cup e_{i} \in \mathcal{F}: X \gets X \cup e_{i}$
$\text{return } X$

【定義 1.3.4】

【定義 1.3.4】（最小基問題に対する貪欲法）
$E := \{ e_{1}, \dots, e_{n} \}, \mathcal{F}: E の独立性システム, w: E \to \mathbb{R}_{\ge 0}: 重み関数$
による最小基問題について、（必要があれば適切に並び替えて） $w(e_{1}) \le \dots \le w(e_{n})$ としたとき、貪欲法を以下のアルゴリズムで定義する：

$X \gets \emptyset$
1. $\text{if } X \cup e_{i} \in \mathcal{F}: X \gets X \cup e_{i}$
$\text{return } X$

※ここで出力される $X$ が極大であることは【定義 1.1.1-(Ⅱ)】から示せます。

勿論、これら貪欲法は一般にはうまくいきません。
しかし、ここで以下の定理が成り立ちます。

【定理 1.3.5】

【定理 1.3.5】（マトロイドの最大独立集合問題に対する貪欲法）
$E := \{ e_{1}, \dots, e_{n} \}, \mathcal{F}: E の独立性システム$ とする。

$\mathcal{F}: マトロイド$
$\Leftrightarrow$ 任意の重み関数 $w: E \to \mathbb{R}_{\ge 0}$ に対し、【定義 1.3.3】の貪欲法が最大独立集合問題の最適解を出力する。

【定理 1.3.6】

【定理 1.3.6】（マトロイドの最小基問題に対する貪欲法）
$E := \{ e_{1}, \dots, e_{n} \}, \mathcal{F}: E の独立性システム$ とする。

$\mathcal{F}: マトロイド$
$\Rightarrow$ 任意の重み関数 $w: E \to \mathbb{R}_{\ge 0}$ に対し、【定義 1.3.4】の貪欲法が最小基問題の最適解を出力する。

※【定理 1.3.6】については、一般に逆が成り立つのか私自身わかっておりません。勉強不足で申し訳ありません…

早速証明していきましょう！

【定理 1.3.5】の証明

$\Rightarrow$ の証明：（ $\mathcal{F}: Eのマトロイド$ を仮定）

【補題 1.4.1】

貪欲法の出力を $B$ 、最適解の1つを $B^{*}$ とする。

また、 $i = 1, \dots , n$ に対し

$B_i := B \cap \{e_1, \dots , e_i \}, B^{*}_i := B^{*} \cap \{e_1, \dots , e_i \}$ とする。このとき、 $r: 階数関数$ として

$|B_i| = r(\{e_1, \dots , e_i \})$
$|B^{*}_i| \le r(\{e_1, \dots , e_i \})$
$|B_i| \ge |B^{*}_i|$

証明：

$B, B^{*}: \mathcal{F}の基$ であることに注意する。

を示せば、【命題1.2.5-(ii)】より示される。
- $B_i \in \mathcal{F}$ である。
- $B_i$ はアルゴリズム2行目のforループ終了時における $X$ に等しいため、
- $\forall e_j \in \{e_1, \dots , e_i \} \setminus B_i, B_i \cup \{e_j\} \notin \mathcal{F}$
- $\therefore B_i: \{e_1, \dots , e_i \}の基$ （ $\because$ 【定義 1.2.3】)　 $\square$

ii:

$B^*_i \subseteq B^*$ より $B^*_i \in \mathcal{F}$ （ $\because$ 【定義 1.1.1-(Ⅱ)】）であるため

\begin{align} |B^*_i| &= r(B^*_i) &\because \text{【命題 1.2.5-(ii)】} \\ &\le r(\{e_1, \dots , e_i \}) &\because \text{【命題 1.2.5-(i)】} \square \end{align}

iii:

i, ii と【命題 1.2.5-(iii)】より　 $\square$

$B_0 = B^*_0 := \emptyset, w(e_{n+1}) := 0$ とすると

\begin{align} \sum_{e \in B} w(e) &= \sum_{i=1}^{n} (|B_i|-|B_{i-1}|)w(e_i) \\ &= \sum_{i=1}^{n} |B_i|w(e_i) - \sum_{i=1}^{n} |B_{i-1}|w(e_i) \\ &= \sum_{i=1}^{n} |B_i|w(e_i) - \sum_{i=0}^{n-1} |B_i|w(e_{i+1}) \\ &= \sum_{i=1}^{n} |B_i|w(e_i) - \sum_{i=1}^{n} |B_i|w(e_{i+1}) \\ &= \sum_{i=1}^{n} |B_i|(w(e_i)-w(e_{i+1})) \\ &\ge \sum_{i=1}^{n} |B^*_i|(w(e_i)-w(e_{i+1})) \tag{※} \\ &= \sum_{i=1}^{n} |B^*_i|w(e_i) - \sum_{i=1}^{n} |B^*_i|w(e_{i+1}) \\ &= \sum_{i=1}^{n} |B^*_i|w(e_i) - \sum_{i=0}^{n-1} |B^*_i|w(e_{i+1}) \\ &= \sum_{i=1}^{n} |B^*_i|w(e_i) - \sum_{i=1}^{n} |B^*_{i-1}|w(e_i) \\ &= \sum_{i=1}^{n} (|B^*_i|-|B^*_{i-1}|)w(e_i) \\ &= \sum_{e \in B^*} w(e) \end{align}

(※)では【補題 1.4.1】と $w(e_i)-w(e_{i+1}) \ge 0$ を用いた。

以上より、貪欲法による解 $B$ は最適解の1つである。　 $\square$

の証明：（対偶を示す。を仮定）
- $\mathcal{F}$ は独立性システムであるため、仮定より【定義 1.1.1-(Ⅲ)】を満たさない、すなわち $\exists X, Y \in \mathcal{F}, |X| \gt |Y| : \forall e \in X \setminus Y, Y \cup \{e\} \notin \mathcal{F}$
- ここで、 $k := |Y|$ とおき、次のように重み関数 $w: E \to \mathbb{R}_{\ge 0}$ を定義：

\begin{align} w(e) := \begin{cases} k+2 & (e \in Y) \\ k+1 & (e \in X \setminus Y) \\ 0 & (\text{otherwise}) \end{cases} \end{align}

- を貪欲法による解とすると、
  - $\because$ 貪欲法のアルゴリズムの動作中、まず $B$ に $e \in Y$ を満たす $e$ が全て追加される。
  - このとき、 $X, Y$ に関する条件より $e \in X \setminus Y$ を満たす $e$ は追加されない。
  - その後、いくつかの $w(e) = 0$ である $e$ が追加される。
  - よって、 $\sum_{e \in B} w(e) = |Y|(k+2) = k(k+2)$ 　 $\square$
- 一方、 $X \in \mathcal{F}$ であって

\begin{align} \sum_{e \in X} w(e) &= |X|(k+2) \\ &\ge (|Y|+1)(k+1) \\ &= (k+1)(k+1) \\ &\gt k(k+2) \end{align}

- よって、この重み関数 $w$ に対して貪欲法は最適解を出力しない　 $\square$

【定理 1.3.6】の証明

$\mathcal{F}: Eのマトロイド$ を仮定。
$W := \sum_{e \in E}w(e)$ とおき、関数 $\tilde{w}: E \to \mathbb{R}_{\ge 0}; e \mapsto \tilde{w}(e)$ を $\tilde{w}(e) := W-w(e)$ で定める。

【補題 1.4.2】

$w$ による最小基問題の最適値を $x$ 、 $\tilde{w}$ による最大独立集合問題の最適値を $y$ とし、 $\mathcal{F}$ の階数関数を $r$ とする。このとき、

$x = Wr(E)-y$

証明：

\begin{align} x &= \underset{B: E\text{の基}}{\text{min}} \{ \sum_{e \in B}w(e) \} \\ &= \underset{B: E\text{の基}}{\text{min}} \{ \sum_{e \in B}(W-\tilde{w}(e)) \} \\ &= \underset{B: E\text{の基}}{\text{min}} \{ W|B| - \sum_{e \in B}(\tilde{w}(e)) \} \\ &= Wr(E) - \underset{B: E\text{の基}}{\text{max}} \{ \sum_{e \in B}(\tilde{w}(e)) \} \\ &= Wr(E) - \underset{X \in \mathcal{F}}{\text{max}} \{ \sum_{e \in B}(\tilde{w}(e)) \} \\ &= Wr(E)-y \quad \square \end{align}

$\tilde{w}(e_1) \ge \dots \ge \tilde{w}(e_n)$ に注意すると、 $w$ による最小基問題に対しての貪欲法による解 $B$ は、 $\tilde{w}$ による最大独立集合問題の最適解の1つとなっている。
すなわち、【補題 1.4.2】において $y = \sum_{e \in B}\tilde{w}(e)$ と表せる。
ここで

\begin{align} \sum_{e \in B}\tilde{w}(e) &= \sum_{e \in B}(W-w(e)) \\ &= Wr(E) - \sum_{e \in B}w(e) \end{align}

なので、【補題 1.4.2】の $y$ にこれを代入すれば

\begin{align} x &= Wr(E)-(Wr(E) - \sum_{e \in B}w(e)) \\ &= \sum_{e \in B}w(e) \end{align}

したがって、貪欲法による解 $B$ は $w$ による最小基問題の最適解でもある。　 $\square$

長い証明を経て、ついに前半戦は終了です！

【定義 1.1.1】のたったの3条件から、貪欲法が使えるという凄まじい結論が得られるの、鮮やか過ぎると思いません？私は思いました。

さて、ここからはグラフとマトロイドの関係に迫る後半戦です。

（後半）マトロイドのクラスカル法への適用

ベクトルマトロイド

非常に重要なマトロイドです。グラフとマトロイドを繋ぐ要となります。

そのまま競プロでも使います。

【命題 2.1.1】

【命題 2.1.1】（ベクトルマトロイド）
$\boldsymbol{a}_{1}, \dots , \boldsymbol{a}_{n}: （適当な体上で定義された）m次元ベクトル,$
$E := \{ \boldsymbol{a}_{1}, \dots , \boldsymbol{a}_{m} \}$ とする。
$E$ の部分集合族 $\mathcal{I}$ を次で定義する：
$\mathcal{I} := \{ X \subset E \mathrel{|} X: 線形独立 \}$
このとき $\mathcal{I}$ はマトロイドであり、ベクトルマトロイドと呼ぶ。

証明：

以下の補題を用いる: （線形代数の知識なので証明は略*5）

【補題】

$A, B: m次元ベクトルの集合$ について

$A: 線形独立 \Leftrightarrow \text{dim} \langle A \rangle = |A|$
$A \subseteq B \Rightarrow \text{dim} \langle A \rangle \le \text{dim} \langle B \rangle$
$A \subseteq B$ のとき、 $\langle A \rangle = \langle B \rangle \Leftrightarrow \text{dim} \langle A \rangle = \text{dim} \langle B \rangle$

マトロイドの3条件を確認する。
1. ok
2. とし、を示す。
  - $X = \{\boldsymbol{a}_1, \dots, \boldsymbol{a}_k\}, Y = \{\boldsymbol{b}_{i_1}, \dots, \boldsymbol{b}_{i_l}\} \quad (\{i_1, \dots i_l\} \subset \{1, \dots, k\})$ とし、 $\Delta := \{1, \dots, k\} \setminus \{i_1, \dots, i_l\}$ とおく。

\begin{align} \sum_{j=1}^{l} \lambda_{i_j} \boldsymbol{a}_{i_j} = \boldsymbol{0} &\Rightarrow \sum_{j=1}^{l} \lambda_{i_j} \boldsymbol{a}_{i_j} + \sum_{i \in \Delta } 0 \cdot \boldsymbol{a}_i = \boldsymbol{0} \\ &\Rightarrow \sum_{i=1}^{k} \lambda_i \boldsymbol{a}_i = \boldsymbol{0} \quad (\lambda_i := 0 \text{ for } i \in \Delta ) \\ &\Rightarrow \lambda_i = 0 \quad \text{for } i \in \{1, \dots, k\} (\because X: \text{線形独立}) \\ &\Rightarrow \lambda_{i_j} = 0 \quad \text{for } j \in \{1, \dots, l\} \end{align}

1. - ok
2. とし、を示す。
  - $X, Y: 線形独立$ より、 $\text{dim} \langle X \rangle = |X|, \text{dim} \langle Y \rangle = |Y|$ （ $\because$ 【補題-(i)】）
  - 以下、背理法で示す。 $\forall x \in X \setminus Y, Y \cup \{x\}: 線形従属$ と仮定。
  - このとき、 …（※）
    - $\because)$
    - の場合：
      - $Y \cup \{x\} = Y$ より　 $\square$
    - $x \notin X \cap Y$ の場合：

\begin{align} |Y| &= \text{dim} \langle Y \rangle \\ &\le \text{dim} \langle Y \cup \{ x \} \rangle &\because 【補題\text{-(ii)}】 \\ &\lt | Y \cup \{ x \} | &\because 【補題\text{-(i)}】\\ &= |Y|+1 \end{align}

- - - - $\therefore \text{dim} \langle Y \rangle = \text{dim} \langle Y \cup \{x\} \rangle$
      - $\therefore \langle Y \rangle = \langle Y \cup \{x\} \rangle \quad \because$ 【補題-(iii)】 $\square$
  - （※）を繰り返し適用すれば $\langle Y \cup X \rangle = \langle Y \rangle$
  - 【補題-(iii)】より

\begin{align} \text{dim} \langle Y \cup X \rangle &= \text{dim} \langle Y \rangle \\ &= |Y|\end{align}

- - 一方、 $\text{dim} \langle X \rangle \le \text{dim} \langle Y \cup X \rangle \quad \because$ 【補題-(ii)】
  - $\therefore |X| \le |Y|$ となり $|X| \gt |Y|$ に矛盾　 $\square$
  - ok

グラフのマトロイド

【定義 2.2.1】

【定義 2.2.1】（接続行列）
$G: 無向グラフ$ とする。
各 $e \in E(G)$ に対し、 $n$ 次元列ベクトル $B(G)_e$ の第 $v \in V(G)$ 成分 $B(G)_{ve}$ を次で定める：
\begin{align} B(G)_{ve} := \begin{cases} 0 &\text{if } v \notin e \\ 1 &\text{else if } v \in e \text{かつ} e \neq \{v, v\} \\ 2 &\text{otherwise} \end{cases} \end{align}
この列ベクトルを横に並べた $V(G) \times E(G)$ 行列 $B(G)$ を、 $G$ の接続行列という。

特に、 $B(G)$ の $v$ 行目の総和は $v$ の次数を表します。（重要）

【定義 2.2.2】

【定義 2.2.2】（閉路マトロイド）
$G: 無向グラフ, B(G)_e: Gの接続行列の第e列ベクトル$ とする。
$\mathcal{I} \subseteq 2^{E(G)}$ を次で定める：
\begin{align} \mathrel{I} := \{X \subseteq E(G) \mathrel{|} \{ &B(G)_e \mathrel{|} e \in X\} が \\ &\mathbb{Z}_2 上の |V(G)| 次元ベクトル空間において線形独立 \} \end{align}このとき、 $\mathcal{I}$ は $E(G)$ のマトロイドであり、Gの閉路マトロイドと呼ぶ。

これがマトロイドであることは、【命題 2.1.1】より明らかです。ありがとうベクトルマトロイド…！！

【命題 2.2.3】

【命題 2.2.3】（閉路マトロイドと森）
$G: 無向グラフ, \mathcal{I}: Gの閉路マトロイド$ とする。このとき
$X \in \mathcal{I} \Leftrightarrow G[X]は森$

※ $G[X]$ は $X$ による $G$ の誘導部分グラフを表します。*6

証明：

の証明：（対偶を示す。について、と仮定）
- 閉路に含まれる辺集合を $C$ とおくと $\sum_{e \in C} B(G)_e = \boldsymbol{0}$ *7
- よって、以下のように $\sum_{e \in X} \lambda_e B(G)_e = \boldsymbol{0}$ の非自明解 $\lambda_e$ が得られる：
- $\therefore X \notin \mathcal{I} ~~ \square$
$\Leftarrow$ の証明：（対偶を示す。 $X \notin \mathcal{I}$ と仮定。）
- $X: 自己ループを持つ$ なら、明らかに $G[X]$ は森でない。以下、 $X: 自己ループを持たない$ とする。
- $\lambda_e$ を $\sum_{e \in X} \lambda_e B(G) = \boldsymbol{0}$ の非自明解とし、 $Y := \{e \in X \mathrel{|} \lambda_e = 1\}$ とする。（ $Y \neq \emptyset$ ）
- このとき、 $Y$ は閉路を持つ。

- - $\because )$
  - $\boldsymbol{0} = \sum_{e \in X} \lambda_e B(G)_e = \sum_{e \in Y} \lambda_e B(G)_e$ より、各 $v \in V(G[Y])$ について $v$ の $G[Y]$ における次数は偶数であり、 $Y$ に誘導されていることに注意すると次数は2以上であるとわかる。
  - ここで、 $G[Y]$ で最大のパス $P$ とその端点の1つ $w$ をとれば、 $w$ の次数が2以上であることから $\exists u \in V(P) : \{w, u\} \in E(G[Y]) \setminus E(P)$ であり、この $P+\{w, u\}$ が $Y$ の持つ閉路である。 $\square$
- したがって、 $X$ は閉路を持つため、 $G[X]$ は森でない。 $\square$