木 (数学)

数学、特にグラフ理論の分野における木（き、）とは、連結で閉路を持たない(無向)グラフである。有向グラフについての木（有向木）についても論じられるが、当記事では専ら無向木を扱う（有向木については節にまとめた）。
閉路を持たない（連結であるとは限らない）グラフを森（もり、）という。木は明らかに森である。あるいは、森を一般的な場合とし、連結な森を木という、とすることもある。
特徴づけ.
 個の点からなるグラフ について次は同値である。
性質.
木 には、以下のような性質がある。
上の定理から、木には必ず端末点があり、その端末点を除去すると位数の一つ小さい木が得られる。逆に言えば、位数 の木は、位数 の木に一つの新しい点と、これに接続する一本の新しい辺を加えて得られる。
根つき木.
あるノードを選んで、それを一番「上」にあると考えると、そのノードを基準として2つのノードに上下の関係を考えることが出来る（すべてのノードの組み合わせについて定義されるとは限らない）。このとき、その一番上のノードを根（ね、）という。根を持つ木を単なる木と区別して根付き木という。
根つき木に関する用語は、それを家系図に見たてたものが多く使われる。
また、根つき木に関する用語として、他に以下のようなものがある。
n分木.
 を自然数とする。葉ではない各点に対しその点の子の数が常に であるような木を分木(ぶんぎ; n-ary tree)という。特に二分木はいくつかのアルゴリズムと密接に関わるデータ構造である（ただし大抵は次で述べる有向木による二分木）。
有向木.
一般に、無向木は任意の点を根とみなすことができる。それに対し有向木は、根である点をただ1つだけ持つ。辺の向きとして、根から葉に向かっている場合と、葉から根に向かっている場合とがある。混在はできない（混在してしまうと閉路ができてしまう）。
閉路を持たない任意の有向グラフは有向非巡回グラフ（Directed Acyclic Graph、DAG）である。有向木は連結な有向非巡回グラフでもあるが、連結な有向非巡回グラフが必ずしも有向木とは限らない（DAGでは子孫あるいは親の共有がある場合がある。そうするとそれは木ではない）。