全域木のソースを表示

{{出典の明記|date=2012年7月}}
{{Expand English|Spanning tree|date=2024年5月}}
[[画像:4x4 grid spanning tree.svg|thumb|4×4のグリッドグラフにおける全域木の一例]]
[[画像:Натурализация гамильтоновых циклов.jpg|thumb|8x8 グリッド グラフ上の 3 つの例]]
[[グラフ理論]]において、[[グラフ (離散数学)|グラフ]]の'''全域木'''（ぜんいきぎ、{{lang-en-short|Spanning tree}}）、'''極大木'''（きょくだいき）、'''スパニング木'''、'''スパニングツリー'''とは、全域部分グラフ（そのグラフの全頂点を含む部分グラフ）のうち、木（[[連結グラフ|連結]]で[[閉路]]を持たないグラフ）であるものをいう。全域木は[[連結グラフ]]に必ず存在し、連結でないグラフには存在しない。

== 最小全域木 ==
各辺に重み（コスト）がある場合、最小の総和コストで構成される全域木を'''最小全域木'''という。
* [[クラスカル法]] - 単純な[[貪欲法]]で計算量は <math>O(E \log{E})</math>。
* [[プリム法]] - 貪欲法だが計算量は <math>O(E + V \log{V})</math>。辺の数が頂点に比べて十分大きいときは <math>O(E)</math> と見なせる。
* [[ブルーフカ法]] - 貪欲法で、計算量は <math>O(E \log{V})</math>。
辺の重みが均一の場合は[[幅優先探索]]で <math>O(E)</math> で求まる。

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

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

== 結び目の射影図 ==
全域木を用いることにより、結び目理論における結び目の射影図を簡単に構成する方法が報告されている<ref name="knot-2006-njze">長島 隆廣『3-正則平面グラフを用いた結び目の構成に関する定理』日本数学協会論文集・別冊数学文化・第2号，2006年12月発行，日本数学協会，pp.52-79.</ref>。この方法によれば、結び目の交点数には制限がなく、任意の交点数で射影図を構成できる。具体的には、一般的な結び目の射影図に対して、2重性並行表示と呼ばれる特殊な射影図を定義する。この2重性並行表示は、3-正則平面グラフと対応がとれる。これにより、どの様な結び目も、3-正則平面グラフで表現できることになる。結び目を構成する方法は、3-正則平面グラフの全域木と双対グラフの全域木を用いる。その概略は、3-正則平面グラフの任意の全域木の各辺に「偶数個の交点」を配置し、全域木の辺ではない 3-正則平面グラフの各辺には「奇数個の交点」を配置する．この操作で得られた射影図は結び目である、という結論が記述されている<ref name="knot-resmap-2006">長島 隆廣『3-正則平面グラフを用いた結び目の構成に関する定理』論文PDF：https://researchmap.jp/T_Nagashima/ または， https://researchmap.jp/multidatabases/multidatabase_contents/detail/263160/b962b603f071c834290b5e34bfdd70cd?frame_id=539358</ref>。

== 脚注 ==
{{脚注ヘルプ}}
{{Reflist}}

== 関連項目 ==
* [[スパニングツリープロトコル]]
* [[シュタイナー木]]
* [[グラフ理論]]
* [[交点数 (結び目理論)]]
* [[結び目理論]]
* [[タングル]]

{{Graph Theory-footer}}
{{アルゴリズム}}
{{最適化アルゴリズム}}

{{Normdaten}}
{{DEFAULTSORT:せんいきき}}
[[Category:全域木|*]]
[[Category:グラフ理論における計算問題]]
[[Category:選択公理]]
[[Category:数学に関する記事]]