木 (数学)
テンプレート:Redirect テンプレート:Infobox graph 木（き、テンプレート:Lang-en-short）とは、グラフの種類の一つで、連結で閉路を持たない無向グラフのことである。木構造（きこうぞう）あるいは樹形図（じゅけいず）ともいう。
閉路を持たない（連結であるとは限らない）無向グラフを森（もり、テンプレート:Lang-en-short）という。木は明らかに森である。閉路を持たない有向グラフ（無閉路有向グラフ）はDAG（Directed acyclic graph）という。
コンピュータ上での木の実装については、木構造 (データ構造)のページに詳しいので、そちらを参照のこと。
特徴づけ
テンプレート:Mvar 個の点からなるグラフ テンプレート:Mvar について次は同値であるテンプレート:Sfn。 テンプレート:Div col
- テンプレート:Mvar は木である
- テンプレート:Mvar に閉路はなく、 テンプレート:Math 本の辺を持つ
- テンプレート:Mvar は連結で、 テンプレート:Math 本の辺を持つ
- テンプレート:Mvar は連結で、すべての辺は橋である
- テンプレート:Mvar の任意の2点を結ぶ道がちょうど1つある
- テンプレート:Mvar に閉路はないが、新しい辺をつけ加えると閉路が必ず1つできる
性質
木 テンプレート:Mvar には、以下のような性質がある。
- テンプレート:Mvar の2点を結ぶ テンプレート:Mvar に含まれない辺 テンプレート:Mvar に対して、テンプレート:Math には テンプレート:Mvar を通るただ一つの閉路があり、この閉路上の任意の辺 テンプレート:Mvar に対して テンプレート:Mvar + e - テンプレート:Mvar は木となる。
- 少なくとも2個の端末点がある。また、端末点とは次数1の点である。
上の定理から、木には必ず端末点があり、その端末点を除去すると位数の一つ小さい木が得られる。逆に言えば、位数 テンプレート:Mvar の木は、位数 テンプレート:Math の木に一つの新しい点と、これに接続する一本の新しい辺を加えて得られる。
根つき木
あるノードを選んで、それを一番「上」にあると考えると、そのノードを基準として2つのノードに上下の関係を考えることが出来る（すべてのノードの組み合わせについて定義されるとは限らない）。このとき、その一番上のノードを根（ね、テンプレート:Lang-en-short）という。根を持つ木を単なる木と区別して根付き木という。
根つき木に関する用語は、それを家系図に見たてたものが多く使われる。
- 点 テンプレート:Math と テンプレート:Math が辺で結ばれており、しかも テンプレート:Math の方が テンプレート:Math よりも根に近いとき、テンプレート:Math は テンプレート:Math の親であるといい、テンプレート:Math は テンプレート:Math の子であるという。
- 点 テンプレート:Math と テンプレート:Math が共通の親を持つとき、テンプレート:Math と テンプレート:Math は兄弟という。
- 根つき木上の2点 テンプレート:Math, テンプレート:Math に対し、テンプレート:Math と根を結ぶ経路上に テンプレート:Math があるとき、テンプレート:Math は テンプレート:Math の先祖であるといい、テンプレート:Math は テンプレート:Math の子孫であるという。
また根つき木に関する用語として、他に以下のようなものがある。
- 子を持たない点を葉という。
- 各辺の長さを1とするとき、点と根との経路の長さをその点の高さという。また、根から最も経路の長さが長くなる点までの長さを、その木の高さという。
テンプレート:Mvar を自然数とする。葉ではない各点に対しその点の子の数が常に テンプレート:Mvar であるような木をテンプレート:Mvar分木(テンプレート:Mvarぶんぎ)という。特に二分木はいくつかのアルゴリズムと密接に関わるデータ構造である。
