書記が数学やるだけ#609 木と林の性質，最小全域木のアルゴリズム

今回からは木について，性質とアルゴリズムについて扱っていく。

問題

説明

木構造はアルゴリズムでも基本的な概念である。

最小全域木を求めるアルゴリズムには，クラスカル法やプリム法などがある。

解答

木には多くの同値表現がある。

端点が少なくとも2つ以上存在することは，握手補題を用いて示すことができる。

クラスカル法は，閉路を作らないようにしつつ重みの小さい順に辺を加えていくアルゴリズムである。

プリム法は，繋がっている辺のうち閉路を作らないものを順次加えていくアルゴリズムである。

本記事のもくじはこちら：