# 木(グラフ理論) ## 定義 閉路を持たない(非巡回な)単純グラフを**森(forest)**、連結な森を**木(tree)**と呼ぶ。森における次数1の頂点を**葉(leaf)**と呼ぶ。木の頂点を階層的に描くとき、最上位の頂点を根(root)、各辺が結ぶ上下の頂点を親(parent)・子(child)と呼ぶ。木は次の性質をすべて満たし、これらは互いに木の特徴づけ(同値な定義)になりうる: (1) 任意の連結な部分グラフは木である、(2) 任意の2頂点間の道は一意である、(3) 隣接していない2頂点間に辺を1本足すと必ず閉路ができる、(4) 任意の辺を除去すると非連結になる(=すべての辺がカット辺である)、(5) 頂点数が2以上なら葉が2枚以上ある、(6) 頂点数は辺数よりちょうど1大きい。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 11 Simple Graphs]] §11.10.1〜§11.10.2) グラフ `G` の全頂点を含む部分グラフを**全域部分グラフ(spanning subgraph)**、`G` の全頂点を含む木である部分グラフを**全域木(spanning tree)**と呼ぶ。任意の連結グラフは全域木を持つ(整列原理(WOP)を用いて、辺数最小の連結な全域部分グラフを取り、それが非巡回であることをカット辺の議論で示す)。辺に重みを持つグラフにおいて辺重みの総和が最小となる全域木を**最小全域木(minimum weight spanning tree, MST)**と呼ぶ。MST を求める標準的な戦略は、あるMSTの部分グラフになりうる全域部分グラフ(**pre-MST**、必然的に森)を、頂点数-1回の辺追加(**拡張、extend**)を経てMSTまで育てるというものである。pre-MSTの各連結成分を黒または白に塗る**solid coloring**において、異なる色の端点を持つ辺を**gray edge**と呼び、最小重みのgray edgeで拡張することは常にpre-MSTを保つ(補題11.10.11)。この単一の補題が、Prim法(木を1点ずつ成長させる)・Kruskal法(森全体で最小重み辺を選ぶ)・両者を一般化した「成分ごとに並列に拡張できるアルゴリズム」を統一的に正当化する。全辺の重みが相異なるとき、MSTは一意である。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 11 Simple Graphs]] §11.10.3〜§11.10.4) ## 横断的知見 - **「任意の2頂点間の道は一意」という木の性質が通信ネットワーク設計の出発点になる**: 本ページの定義(性質2、[[@2015__MIT__Mathematics for Computer Science - Chapter 11 Simple Graphs]])が示す「木の任意の2頂点間の経路は一意」という事実を、[[@2015__MIT__Mathematics for Computer Science - Chapter 10 Communication Networks]]は完全二分木(complete binary tree)による相互結合網の最初の例として利用する。パケットを入力端子から出力端子へ届けるルーティングは、木ならではの一意な経路をそのまま辿ればよく、ルーティング問題(経路の選び方)が自明になる。ただしこの単純さの代償として、完全二分木は根スイッチへの輻輳(congestion)が最悪`N`に達する単一障害点を持つことが第10章で示され、木構造の経路一意性という利点が同時に輻輳集中という欠点の原因にもなる。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 11 Simple Graphs]] §11.10.1, [[@2015__MIT__Mathematics for Computer Science - Chapter 10 Communication Networks]] §10.1, §10.6) ## 未解決の問い - Prim法・Kruskal法は本章では貪欲アルゴリズム(greedy algorithm)としてのみ紹介され、計算量(データ構造による実装効率の違い)は扱われていない。アルゴリズム論の別ソースでの計算量の突き合わせが必要。 - 「成分ごとに独立・並列に拡張できるアルゴリズム3」は分散計算に適すると本章は述べるが、具体的な分散MSTアルゴリズム(GHSアルゴリズムなど)や通信ネットワーク(第10章)との関係は本章単独では確認できない。 - 木の特徴づけ(性質1〜6)のうち、どの部分集合が必要十分条件として最小になるか(本章は補題11.10.4で「森かつ頂点数=辺数+1」の1組を示すのみ)は、他の組み合わせについて演習に留まり、本文で網羅されていない。 ## 関連 - 概念: [[単純グラフ]] / [[相互結合網]] - source: [[@2015__MIT__Mathematics for Computer Science - Chapter 11 Simple Graphs]] / [[@2015__MIT__Mathematics for Computer Science - Chapter 10 Communication Networks]] ## 出典 - Eric Lehman, F. Thomson Leighton, Albert R. Meyer, *Mathematics for Computer Science*, revised 2015-05-18, Chapter 11.