木 (数学)

テンプレート:Infobox graph 数学、特にグラフ理論の分野における木（き、英: tree）とは、連結で閉路を持たない(無向)グラフである。有向グラフについての木（有向木）についても論じられるが、当記事では専ら無向木を扱う。

閉路を持たない（連結であるとは限らない）無向グラフを森（もり、英: forest）という。木は明らかに森である。

なお、閉路を持たない有向グラフは有向非巡回グラフである。有向木は有向非巡回グラフでもあるが、有向非巡回グラフは必ずしも有向木とは限らない。

コンピュータ上での木の扱いについては、木構造 (データ構造) を参照。

特徴づけ

$n$ 個の点からなるグラフ $T$ について次は同値である^[1]。

木 $T$ には、以下のような性質がある。

$T$ の2点を結ぶ $T$ に含まれない辺 $e$ に対して、 $T + e$ には $e$ を通るただ一つの閉路があり、この閉路上の任意の辺 $f$ に対して $T$ + e - $f$ は木となる。
頂点が2つ以上ある木には少なくとも2個の端末点がある。また、端末点とは次数1の点である。

上の定理から、木には必ず端末点があり、その端末点を除去すると位数の一つ小さい木が得られる。逆に言えば、位数 $n$ の木は、位数 $n - 1$ の木に一つの新しい点と、これに接続する一本の新しい辺を加えて得られる。

あるノードを選んで、それを一番「上」にあると考えると、そのノードを基準として2つのノードに上下の関係を考えることが出来る（すべてのノードの組み合わせについて定義されるとは限らない）。このとき、その一番上のノードを根（ね、英: root）という。根を持つ木を単なる木と区別して根付き木という。

根つき木に関する用語は、それを家系図に見たてたものが多く使われる。

点 $v 1$ と $v 2$ が辺で結ばれており、しかも $v 1$ の方が $v 2$ よりも根に近いとき、 $v 1$ は $v 2$ の親であるといい、 $v 2$ は $v 1$ の子であるという。
点 $v 2$ と $v 3$ が共通の親を持つとき、 $v 2$ と $v 3$ は兄弟という。
根つき木上の2点 $v 1$ , $v 2$ に対し、 $v 2$ と根を結ぶ経路上に $v 1$ があるとき、 $v 1$ は $v 2$ の先祖であるといい、 $v 2$ は $v 1$ の子孫であるという。

また根つき木に関する用語として、他に以下のようなものがある。

$n$ を自然数とする。葉ではない各点に対しその点の子の数が常に $n$ であるような木を $n$ 分木( $n$ ぶんぎ; n-ary tree)という。特に二分木はいくつかのアルゴリズムと密接に関わるデータ構造である。