全域木

グラフ理論において、グラフの全域木（ぜんいきぎ、英: Spanning tree）、極大木（きょくだいき）、スパニング木、スパニングツリーとは、全域部分グラフ（そのグラフの全頂点を含む部分グラフ）のうち、木（連結で閉路を持たないグラフ）であるものをいう。全域木は連結グラフに必ず存在し、連結でないグラフには存在しない。

4×4のグリッドグラフにおける全域木の一例

8x8 グリッド グラフ上の 3 つの例

最小全域木

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

• クラスカル法 - 単純な貪欲法で計算量は ${\displaystyle O(E\log {E})}$。
• プリム法 - 貪欲法だが計算量は ${\displaystyle O(E+V\log {V})}$。辺の数が頂点に比べて十分大きいときは ${\displaystyle O(E)}$ と見なせる。

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

最短経路問題

→詳細は「最短経路問題」を参照

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

応用

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

結び目の射影図

全域木を用いることにより、結び目理論における結び目の射影図を簡単に構成する方法が報告されている^[1]。この方法によれば、結び目の交点数には制限がなく、任意の交点数で射影図を構成できる。具体的には、一般的な結び目の射影図に対して、2重性並行表示と呼ばれる特殊な射影図を定義する。この2重性並行表示は、3-正則平面グラフと対応がとれる。これにより、どの様な結び目も、3-正則平面グラフで表現できることになる。結び目を構成する方法は、3-正則平面グラフの全域木と双対グラフの全域木を用いる。その概略は、3-正則平面グラフの任意の全域木の各辺に「偶数個の交点」を配置し、全域木の辺ではない 3-正則平面グラフの各辺には「奇数個の交点」を配置する．この操作で得られた射影図は結び目である、という結論が記述されている^[2]。

参考文献

1. 長島 隆廣『3-正則平面グラフを用いた結び目の構成に関する定理』日本数学協会論文集・別冊数学文化・第2号，2006年12月発行，日本数学協会，pp.52-79.
2. 長島 隆廣『3-正則平面グラフを用いた結び目の構成に関する定理』論文PDF：https://researchmap.jp/T_Nagashima/ または， https://researchmap.jp/multidatabases/multidatabase_contents/detail/263160/b962b603f071c834290b5e34bfdd70cd?frame_id=539358

関連項目

• スパニングツリープロトコル
• シュタイナー木
• グラフ理論
• 交点数 (結び目理論)
• 結び目理論
• タングル