「樹形図」はこの項目へ転送されています。小比類巻かほるのアルバムについては「樹形図 (アルバム)」をご覧ください。

木
6つの頂点と5つの辺からなる木の例
頂点n
辺n − 1
彩色数2
テンプレートを表示

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

閉路を持たない（連結であるとは限らない）グラフを森（もり、英: forest）という。木は明らかに森である。あるいは、森を一般的な場合とし、連結な森を木という、とすることもある。コンピュータ上での木の扱いについては「木構造 (データ構造)」を参照

特徴づけ

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

T は木である

T に閉路はなく、 n − 1 本の辺を持つ

T は連結で、 n − 1 本の辺を持つ

T は連結で、すべての辺は橋である

T の任意の2点を結ぶ道がちょうど1つある

T に閉路はないが、新しい辺をつけ加えると閉路が必ず1つできる

性質

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

T の2点を結ぶ T に含まれない辺 e に対して、T + e には e を通るただ一つの閉路があり、この閉路上の任意の辺 f に対して T + e - f は木となる。

頂点が2つ以上ある木には少なくとも2個の端末点がある。また、端末点とは次数1の点である。

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

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

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

点 v1 と v2 が辺で結ばれており、しかも v1 の方が v2 よりも根に近いとき、v1 は v2 の親であるといい、v2 は v1 の子であるという。

点 v2 と v3 が共通の親を持つとき、v2 と v3 は兄弟という。

根つき木上の2点 v1, v2 に対し、v2 と根を結ぶ経路上に v1 があるとき、v1 は v2 の先祖であるといい、v2 は v1 の子孫であるという。

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

子を持たない点を葉という。

各辺の長さを1とするとき、点と根との経路の長さをその点の高さという。また、根から最も経路の長さが長くなる点までの長さを、その木の高さという。

n分木

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

一般に、無向木は任意の点を根とみなすことができる。それに対し有向木は、根である点をただ1つだけ持つ。辺の向きとして、根から葉に向かっている場合と、葉から根に向かっている場合とがある。混在はできない（混在してしまうと閉路ができてしまう）[2]。

閉路を持たない任意の有向グラフは有向非巡回グラフ（Directed Acyclic Graph、DAG[3]）である。有向木は連結な有向非巡回グラフでもあるが、連結な有向非巡回グラフが必ずしも有向木とは限らない（DAGでは子孫あるいは親の共有がある場合がある。そうするとそれは木ではない）。
脚注^ ウィルソン 2007, p. 60.
^ データ構造などの実装としてはしばしば、Unixのファイルシステムにおける .. というディレクトリエントリなどのように、逆向きのリンクを持たせることがある。
^ 頻出するデータ構造であり、アクロニム風に「だぐ」と呼ばれることも多い。

参考文献

ウィルソン, R. J.『 ⇒グラフ理論』 原書第4版、西関隆夫・西関裕子、近代科学社、2007年。.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation.cs-ja1 q,.mw-parser-output .citation.cs-ja2 q{quotes:"「""」""『""』"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free a,.mw-parser-output .citation .cs1-lock-free a{background:url("//upload.wikimedia.org/wikipedia/commons/6/65/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited a,.mw-parser-output .id-lock-registration a,.mw-parser-output .citation .cs1-lock-limited a,.mw-parser-output .citation .cs1-lock-registration a{background:url("//upload.wikimedia.org/wikipedia/commons/d/d6/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription a,.mw-parser-output .citation .cs1-lock-subscription a{background:url("//upload.wikimedia.org/wikipedia/commons/a/aa/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("//upload.wikimedia.org/wikipedia/commons/4/4c/Wikisource-logo.svg")right 0.1em center/12px no-repeat}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:#d33}.mw-parser-output .cs1-visible-error{color:#d33}.mw-parser-output .cs1-maint{display:none;color:#3a3;margin-left:0.3em}.mw-parser-output .cs1-format{font-size:95%}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}ISBN 978-4-7649-0296-1。 

関連項目

カクタスグラフ

系統樹