木 (数学)

出典: フリー百科事典『ウィキペディア(Wikipedia)』
2014年8月6日 (水) 18:14時点におけるARAKI Satoru (トーク)による版 (外部リンクにDiestelの本を追加)
(差分) ← 古い版 | 最新版 (差分) | 新しい版 → (差分)
移動先: 案内検索

テンプレート:Redirect テンプレート:Infobox graph (き、テンプレート:Lang-en-short)とは、グラフの種類の一つで、連結閉路を持たない無向グラフのことである。木構造(きこうぞう)あるいは樹形図(じゅけいず)ともいう。

閉路を持たない(連結であるとは限らない)無向グラフを(もり、テンプレート:Lang-en-short)という。木は明らかに森である。閉路を持たない有向グラフ(無閉路有向グラフ)はDAGDirected acyclic graph)という。

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

ファイル:Tree-sample1.png

特徴づけ

テンプレート:Mvar 個の点からなるグラフ テンプレート:Mvar について次は同値であるテンプレート:Sfnテンプレート:Div col

テンプレート:Div col end

性質

テンプレート:Mvar には、以下のような性質がある。

上の定理から、木には必ず端末点があり、その端末点を除去すると位数の一つ小さい木が得られる。逆に言えば、位数 テンプレート:Mvar の木は、位数 テンプレート:Math の木に一つの新しい点と、これに接続する一本の新しい辺を加えて得られる。

根つき木

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

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

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

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

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

脚注

テンプレート:Reflist

参考文献

関連項目

外部リンク