スパニング木

スパニング木とは

グラフ理論において、スパニング木（-き、）あるいは極大木（きょくだいき）、全域木（ぜんいきぎ）、スパニングツリーとは以下のように定義される木のことである。

グラフ G(V,E) において T ⊆ E となる辺集合 T があるとき、グラフ S(V,T) が木（閉路を持たないグラフ）であるなら、 S(V,T) のことをグラフ G(V,E) のスパニング木であるとする。

つまり、あるグラフの全ての頂点とそのグラフを構成する辺の一部分のみで構成される木のことである。
各辺に重み（コスト）がある場合、最小のコストで構成されるスパニング木は単純な貪欲法で <math>O\left(\left|E\right|\log\left|E\right|\right)</math> となるアルゴリズムが知られている（Kruskalのアルゴリズム）。また辺の数が頂点に比べて十分大きいときは<math>O\left(\left|E\right|\right)</math>で求まるアルゴリズムもある（Primのアルゴリズム）。
また、ある頂点から別の頂点に移動するコストが最小になるスパニング木のことを最短経路木といいある頂点から他の全ての頂点への移動コストが最小になるような最短経路木を求める問題を最短経路問題という。この問題は単一の頂点から任意の頂点への最短経路木を求める方法としてはダイクストラ法が、また任意の頂点から任意の頂点への移動コストが最小になるような最短経路木を求める方法としてはワーシャル-フロイド法が知られている。
この木の概念は特にコンピュータネットワーク関連で重要な位置を占めている。何故なら各種端末やルータ、スイッチングハブなどを頂点と見なし、接続されているケーブル類を辺と見なせばネットワークはひとつの巨大なグラフであり、スパニング木の概念はそのグラフに対する経路の構築手順であると見なせるからである。実際にOSPFやSTPでは上記の最短経路木を構成することによって通信経路を決定している。

• 出典: フリー百科事典『ウィキペディア（Wikipedia）』
• [ スパニング木の改定履歴 ]