「最短経路の本 レナのふしぎな数学の旅」の中で言及されていたので、Geminiを使って少し細かく調べた。
クルスカル法について
クルスカル法は無向木(undirected tree)における最小全域木を見つけるために使用できるアルゴリズムである。
なお、これは、有向木(directed tree)における最小有向全域木を見つけるためには使用できない。
証明
あるグラフにおける最小全域木を作ることを考える。 このグラフのエッジを要素と見なすと、以下の構造が定義できる。
独立集合：「閉路を作らない要素の選び方」(=森の作り方)の集合。
基：独立集合の中で、要素数が最大となるパターン。これは全域木であることと同値である。
基グラフ：それぞれの基をノードとみなす。ノードAとBが、要素を1本入れ替えるだけで変換できる関係なら、その間に無向エッジを張る。
今、「閉路を作らないようにエッジ(要素)を1本ずつ増やすプロセス」は以下の3条件を満たすため、マトロイドであると言える。
- 空集合の存在：エッジを1本も含まない森は、閉路がないため独立集合に含まれる
- 部分集合閉性：あるエッジの集まりが独立集合に含まれる(=森である)ならば、そこからエッジ(要素)を減らしても独立集合に含まれるのまま(=森である)である
- 交換性質（増大性質）：ある独立集合の要素(森) $A$ とより大きな独立集合の要素(森) $B$ があるとき、$B$ だけが持っているエッジ(要素)の中に、「$A$ に追加しても閉路を作らないエッジ」が少なくとも1つ存在する
したがって、貪欲法の正当性により、「エッジ(要素)にコストがある場合、その時点で閉路を作らない最も安いエッジ(要素)を貪欲に選び続けるだけで、最終的に必ず最小全域木(コスト最小の基)に到達できる」ことがいえる。