Spanning Tree(全域木)とは何か - アメリカの大学で奮闘中

今回の記事ではグラフ理論のSpanning Tree(全域木)を扱います。

まずそもそもグラフとは？の人はこちらの記事から入られることをお勧めします。

また今回は分かりやすくするために無向グラフを使います。

全域木はかなり平たくいうと、全ての頂点が辺で結ばれている状態を満たすグラフのことを言います

全域木は元々のグラフの補グラフ(subgraph)になっています。

ちなみに、Theoremで全ての連結グラフは全域木を持つことが保証されています。

最小全域木は重り付グラフの時に、全域木のトータルの重りの和が最小になるグラフです。

最小全域木を求めるアルゴリズムは主に2つです。Kruskal's Algorithm(クラスカルのアルゴリズム)とPrime Algorithm(プライムのアルゴリズム)です。

これらのアルゴリズムを使う際は、一旦全ての辺を消します。

Kruskal's Algorithm(クラスカルのアルゴリズム)は全ての辺(edge)の中から小さいものを順に書き足していき、全ての頂点が結ばれるまで続けます。

Prime Algorithm(プライムのアルゴリズム)はある任意の一点からスタートして、今まで通った頂点から出ている辺(edge)の中でweight(重り)が一番小さいものを選んで線をひきます。

これを全ての頂点(node, vertex)が連結されるまで続けます。

最小全域木はできる限り合計の重りの和が小さくしたまま全ての頂点との経路が作れます。この特徴を使って実社会の問題解決に役立ててもらえればと思います。