根つき木

ウィキペディア小見出し辞書

根つき木

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/11/24 13:38 UTC 版)

「木 (数学)」の記事における「根つき木」の解説

あるノードを選んで、それを一番「上」にあると考えると、そのノードを基準として2つのノードに上下の関係を考えることが出来る（すべてのノードの組み合わせについて定義されるとは限らない）。このとき、その一番上のノードを根（ね、英: root）という。根を持つ木を単なる木と区別して根付き木という。 根つき木に関する用語は、それを家系図に見たてたものが多く使われる。 点 v1 と v2 が辺で結ばれており、しかも v1 の方が v2 よりも根に近いとき、v1 は v2 の親であるといい、v2 は v1 の子であるという。 点 v2 と v3 が共通の親を持つとき、v2 と v3 は兄弟という。 根つき木上の2点 v1, v2 に対し、v2 と根を結ぶ経路上に v1 があるとき、v1 は v2 の先祖であるといい、v2 は v1 の子孫であるという。 また根つき木に関する用語として、他に以下のようなものがある。 子を持たない点を葉という。 各辺の長さを1とするとき、点と根との経路の長さをその点の高さという。また、根から最も経路の長さが長くなる点までの長さを、その木の高さという。