木 (数学)

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索
Tree graph.svg
6つの頂点と5つの辺からなる木
頂点 v
v - 1
彩色数 2
テンプレートを表示

(き、英語: tree)とは、グラフの種類の一つで、単連結閉路を持たない無向グラフのことである。木構造(きこうぞう)あるいは樹形図(じゅけいず)ともいう。

閉路を持たない(連結であるとは限らない)無向グラフを(もり、英語: forest)という。木は明らかに森である。閉路を持たない有向グラフ(無閉路有向グラフ)はDAGDirected acyclic graph)という。

コンピュータ上での木の実装については、木構造 (データ構造)のページに詳しいので、そちらを参照のこと。

Tree-sample1.png

性質[編集]

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)という。根を持つ木を単なる木と区別して根付き木という。

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

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

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

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

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

関連項目[編集]