全域木

この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。 出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方） 出典検索?: "全域木" – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL (2012年7月)

この記事は英語版の対応するページを翻訳することにより充実させることができます。（2024年5月） 翻訳前に重要な指示を読むには右にある[表示]をクリックしてください。 英語版記事を日本語へ機械翻訳したバージョン（Google翻訳）。 万が一翻訳の手がかりとして機械翻訳を用いた場合、翻訳者は必ず翻訳元原文を参照して機械翻訳の誤りを訂正し、正確な翻訳にしなければなりません。これが成されていない場合、記事は削除の方針G-3に基づき、削除される可能性があります。 信頼性が低いまたは低品質な文章を翻訳しないでください。もし可能ならば、文章を他言語版記事に示された文献で正しいかどうかを確認してください。 履歴継承を行うため、要約欄に翻訳元となった記事のページ名・版について記述する必要があります。記述方法については、Wikipedia:翻訳のガイドライン#要約欄への記入を参照ください。 翻訳後、{{翻訳告知|en|Spanning tree|…}}をノートに追加することもできます。 Wikipedia:翻訳のガイドラインに、より詳細な翻訳の手順・指針についての説明があります。

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

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

• クラスカル法 - 単純な貪欲法で計算量は ${\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]。

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

表 話 編 歴 グラフ理論
要素・定義・表現	頂点 辺（英語版） グラフ 無向 有向 ラベル付き（英語版） 重み付き（英語版） ハイパーグラフ 接続行列 隣接行列 隣接リスト
指標	位数（英語版） サイズ（英語版） 次数 次数行列 距離（英語版） 半径 直径 内周 (頂点)彩色数 辺彩色数（英語版） 点連結度 辺連結度 交叉数（英語版）
部分構造	ループ（英語版） 多重辺（英語版） 部分グラフ（英語版） 誘導部分グラフ 道 閉道 連結成分（英語版） 強連結成分（英語版） 橋（英語版） カット クリーク 独立集合 支配集合（英語版） マッチング オイラー路 シュタイナー木 全域木 ハミルトン路
全体構造	連結グラフ 正則グラフ 立方体グラフ ケージ 強正則グラフ 木 平面グラフ 2部グラフ 有向非巡回グラフ 弦グラフ ムーアグラフ パーフェクトグラフ 対称グラフ 半対称グラフ 頂点推移グラフ 辺推移グラフ 距離推移グラフ 補グラフ 双対グラフ グラフ同型
固有名を持つグラフ	パスグラフ（英語版）Pn 閉路グラフCn 完全グラフKn 完全2部グラフKm,n スターSn = K1,n 車輪グラフWn 空グラフ ピーターセングラフ ヒーウッドグラフ マギーグラフ ホフマンシングルトングラフ フォークマングラフ
トピック・定理	一筆書き オイラーの多面体定理 クラトフスキの定理 四色定理 五色定理 ケイリーの公式 プリューファー列 最短経路問題 巡回セールスマン問題 中国人郵便配達問題 ダイクストラ法 ベルマン-フォード法 ワーシャル-フロイド法 ハミルトン閉路問題 最大クリーク問題 頂点被覆問題 最小頂点被覆問題 最大独立集合問題 最大流最小カット定理 支配集合問題 次数直径問題 安定結婚問題
カテゴリ / コモンズ