全域木

出典: フリー百科事典『ウィキペディア(Wikipedia)』
スパニング木から転送)
移動: 案内検索
4×4のグリッドグラフにおける全域木の一例

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

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

つまり、あるグラフの全ての頂点とそのグラフを構成する辺の一部分のみで構成される木のことである。

最小全域木[編集]

各辺に重み(コスト)がある場合、最小の総和コストで構成される全域木を最小全域木という。

辺の重みが均一の場合は幅優先探索O(E) で求まる。

最短経路問題[編集]

ある頂点から他の頂点への移動コストが最小になるような経路を求める問題を最短経路問題という。ある頂点から他の全ての頂点に移動するコストが最小になる木のことを最短経路木といい、これは全域木である。最短経路問題は単一の頂点から任意の頂点への最短経路木を求める方法としてはダイクストラ法ベルマン-フォード法などが、また任意の頂点から任意の頂点への移動コストが最小になるような最短経路木を求める方法としてはワーシャル-フロイド法が知られている。

応用[編集]

全域木の概念は特にコンピュータネットワーク関連で重要な位置を占めている。何故なら各種端末やルータスイッチングハブなどを頂点と見なし、接続されているケーブル類を辺と見なせばネットワークはひとつの巨大なグラフであり、全域木の概念はそのグラフに対する経路の構築手順であると見なせるからである。実際にOSPFSTPでは上記の最短経路木を構成することによって通信経路を決定している。

関連項目[編集]