木 (数学)
出典: フリー百科事典『ウィキペディア（Wikipedia）』
| 木 | |
|---|---|
6つの葉と5つの節点からなる木
|
|
| 頂点 | v |
| 辺 | v - 1 |
| 彩色数 | 2 |
木構造（きこうぞう、英語：tree structure）あるいは木（き、英語：tree）、樹形図（じゅけいず）は、グラフの種類の一つで、単連結で閉路を持たない無向グラフのことである。
- 系図を利用してやることも出来る。
- 閉路を持たない（連結であるとは限らない）無向グラフを森という。木は明らかに森である。
- 閉路を持たない有向グラフ（無閉路有向グラフ）はDAG（Directed acyclic graph）という。
コンピュータ上での木の実装については、木構造 (データ構造)のページに詳しいので、そちらを参照のこと。
[編集] 性質
木 T には、以下のような性質がある。
- （T の辺の個数）=（T の節点の個数）- 1
- 記号で表すと、||T|| = |T| - 1
- 任意の2点 x,y に対して、x,y を結ぶ道はただ一つである。
- T の2点を結ぶ T に含まれない辺 e に対して、T + e には e を通るただ一つの閉路があり、この閉路上の任意の辺 f に対して T + e - f は木となる。
- 少なくとも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 はv_2の先祖であるといい、v2 は v1 の子孫であるという。
また根つき木に関する用語として、他に以下のようなものがある。
- 子を持たない点を葉という。
- 各辺の長さを1とするとき、点と根との経路の長さをその点の高さという。また、根から最も経路の長さが長くなる点までの長さを、その木の高さという。
n を自然数とする。葉ではない各点に対しその点の子の数が常に n であるような木をn分木(nぶんぎ)という。特に二分木はいくつかのアルゴリズムと密接に関わるデータ構造である。
