アルゴリズムの授業で最小全域木（MST）問題を習うと，Kruskal 法という驚くほどシンプルなアルゴリズムが最適解を与えることに感動します．「辺を重みの小さい順に見て，閉路ができなければ採用する」― ただこれだけです．

しかし，ちょっと考えると不安になりませんか？ 貪欲法（greedy）は一般には最適解を保証しないのに，なぜ MST では上手くいくのでしょうか？ この記事では，その理由をマトロイドの観点から直感的に説明します．

1 最小全域木問題

この例では，辺$\{A,B\}$（重み1），$\{B,C\}$（重み2），$\{C,D\}$（重み3）を選ぶと重み和6の MST が得られます．Kruskal 法はまさにこの選択を行います．

2 Kruskal 法 ― 愚直な貪欲

Kruskal 法のアルゴリズムは驚くほど単純です：

1. すべての辺を重みの昇順にソートする

2. 辺を順番に見ていき，その辺を追加しても閉路ができなければ採用する

3. $n-1$ 本の辺を採用したら終了

しかし問題は，なぜこの素朴な戦略で最適解が得られるのかということです．

3 貪欲法が失敗する例 ― ナップサック問題

まず，貪欲法がうまくいかない例を見ましょう．

貪欲法が失敗する根本的な理由は，局所的に最善の選択が全体的にも最善とは限らないからです．では，MST 問題ではなぜこの問題が起きないのでしょうか？

4 カット性質 ― 貪欲が正しい直感的理由

MST で貪欲法が正しく動く最も直感的な理由は，カット性質（Cut Property）です．

Kruskal 法は，辺$\{u,v\}$を追加する時点で$u$と$v$が異なる連結成分にいる場合，その2つの連結成分がカットを定義します．その辺がカットをまたぐ最軽量辺であるかどうかは Kruskal 法の時点ではわかりませんが，辺を重みの昇順に処理しているので，「このカットをまたぐ辺の中で最初に見つかった辺」= 「このカットの最軽量辺」が保証されるのです．

5 マトロイド ― 貪欲法が最適になる構造の正体

実は，MST 問題で貪欲法が成功する理由には，より深い数学的構造があります．

6 Kruskal 法の正しさ ― まとめ

Kruskal 法が最適解を出す理由を2つのレベルで理解できました：

1. カット性質レベル：辺の重みの昇順に処理するので，各カットに対して最軽量辺が選ばれる

2. マトロイドレベル：森（閉路を含まない辺集合）はマトロイドをなし，マトロイド上の貪欲法は常に最適

次の記事では，オイラーとハミルトンの問題に見られる，グラフ理論の最も劇的な複雑さのギャップについて考えます．