木 (グラフ理論)

数学のグラフ理論において、木（英: tree）とは、連結であり、かつ閉路（サイクル）を持たない無向グラフのことを指します。グラフ理論における最も基本的かつ重要な構造の一つであり、計算機科学におけるデータ構造としても広く応用されています。

閉路を持たないグラフは、連結であるかどうかにかかわらず森（英: forest）と呼ばれます。したがって、木は連結な森であると定義することも可能です。

数学的特徴

頂点数が n であるグラフ T が木であるための条件は、以下のいずれか一つが満たされることと同値です。

• 連結であり、かつ閉路を持たない。
• 閉路を持たず、辺の数が n - 1 本である。
• 連結であり、辺の数が n - 1 本である。
• 任意の2頂点を結ぶ道がただ一つ存在する。
• 閉路を持たないが、任意の2頂点間に新たな辺を追加すると、必ず一つの閉路が形成される。

また、頂点数が2以上の木には、必ず次数が1である端末点（葉）が少なくとも2つ存在します。この端末点を除去する操作を繰り返すことで、木を構成する頂点をすべて取り除くことが可能です。

根付き木

木の一つの頂点を「根（ルート）」として特別に指定したものを根付き木と呼びます。根付き木では、親、子、先祖、子孫といった階層的な関係が定義されます。

• 親と子：辺で結ばれた2頂点のうち、根に近い方を親、遠い方を子と呼びます。
• 葉：子を持たない頂点を葉と呼びます。
• 高さ：根からある頂点までの経路の長さをその頂点の高さと呼び、木の中で最も深い頂点の高さをその木の高さと定義します。

関連する概念

n分木

各頂点から出る子の数が最大で n 個であるような木を n 分木と呼びます。特に n=2 の二分木は、探索アルゴリズムやデータ構造において極めて重要な役割を果たします。

有向木とDAG

有向グラフにおいて、根から葉へ（あるいはその逆へ）辺の向きが統一されているものを有向木と呼びます。閉路を持たない有向グラフは有向非巡回グラフ（Directed Acyclic Graph、略称：DAG）と呼ばれます。有向木は連結なDAGの一種ですが、DAGは必ずしも木であるとは限りません（親の共有などが許容されるため）。