木 (数学)
出典: Wikipedio
|
|
木構造（きこうぞう、英語：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）という。根を持つ木を単なる木と区別して根付き木という。
根つき木に関する用語は、それを家系図に見たてたものが多く使われる。
- 点v_1とv_2が辺で結ばれており、しかもv_1の方がv_2よりも根に近いとき、v_1はv_2の親であるといい、v_2はv_1の子であるという。
- 点v_2とv_3が共通の親を持つとき、v_2とv_3は兄弟という。
- 根つき木上の2点v_1,v_2に対し、v_2と根を結ぶ経路上にv_1があるとき、v_1はv_2の先祖であるといい、v_2はv_1の子孫であるという。
また根つき木に関する用語として、他に以下のようなものがある。
- 子を持たない点を葉という。
- 各辺の長さを1とするとき、点と根との経路の長さをその点の高さという。また、根から最も経路の長さが長くなる点までの長さを、その木の高さという。
nを自然数とする。葉ではない各点に対しその点の子の数が常にnであるような木をn分木(nぶんぎ)という。特に二分木はいくつかのアルゴリズムと密接に関わるデータ構造である。cs:Strom (graf) de:Baum (Graphentheorie) en:Tree (graph theory) fa:درخت (نظریه گراف) fi:Puu (graafiteoria) fr:Arbre (mathématiques) he:עץ (תורת הגרפים) hu:Fa (gráfelmélet) it:Albero (grafo) lt:Medis (grafų teorija) lv:Aciklisks grafs nl:Boomstructuur pl:Drzewo (matematyka) pt:Árvore (grafo) ro:Arbore (teoria grafurilor) ru:Дерево (теория графов) sk:Strom (graf) sr:Стабло (теорија графова) sv:Träd (graf) th:ต้นไม้ (ทฤษฎีกราฟ) uk:Дерево (теорія графів) vi:Cây (lý thuyết đồ thị) zh:树 (图论)
