木 (数学)
| 木 | |
|---|---|
 6つの頂点と5つの辺からなる木の例 | |
| 頂点 | n |
| 辺 | n − 1 |
| 彩色数 | 2 |
数学、特にグラフ理論の分野における木（き、英: tree）とは、連結で閉路を持たない(無向)グラフである。有向グラフについての木（有向木）についても論じられるが、当記事では専ら無向木を扱う（有向木については節にまとめた）。
閉路を持たない（連結であるとは限らない）グラフを森（もり、英: forest）という。木は明らかに森である。あるいは、森を一般的な場合とし、連結な森を木という、とすることもある。
コンピュータ上での木の扱いについては「木構造 (データ構造)」を参照
特徴づけ[編集]
n 個の点からなるグラフ T について次は同値である[1]。
性質[編集]
木 Tには、以下のような性質がある。
●T の2点を結ぶ Tに含まれない辺 eに対して、T + eには eを通るただ一つの閉路があり、この閉路上の任意の辺 fに対して T+ e- fは木となる。
●頂点が2つ以上ある木には少なくとも2個の端末点がある。また、端末点とは次数1の点である。
上の定理から、木には必ず端末点があり、その端末点を除去すると位数の一つ小さい木が得られる。逆に言えば、位数 nの木は、位数 n− 1 の木に一つの新しい点と、これに接続する一本の新しい辺を加えて得られる。
根つき木[編集]
あるノードを選んで、それを一番﹁上﹂にあると考えると、そのノードを基準として2つのノードに上下の関係を考えることが出来る︵すべてのノードの組み合わせについて定義されるとは限らない︶。このとき、その一番上のノードを根︵ね、英: root︶という。根を持つ木を単なる木と区別して根付き木という。 根つき木に関する用語は、それを家系図に見たてたものが多く使われる。 ●点 v1と v2が辺で結ばれており、しかも v1の方が v2よりも根に近いとき、v1 は v2の親であるといい、v2 は v1の子であるという。 ●点 v2と v3が共通の親を持つとき、v2 と v3は兄弟という。 ●根つき木上の2点 v1, v2に対し、v2 と根を結ぶ経路上に v1があるとき、v1 は v2の先祖であるといい、v2 は v1の子孫であるという。 また、根つき木に関する用語として、他に以下のようなものがある。 ●子を持たない点を葉という。 ●各辺の長さを1とするとき、点と根との経路の長さをその点の高さという。また、根から最も経路の長さが長くなる点までの長さを、その木の高さという。n分木[編集]
n を自然数とする。葉ではない各点に対しその点の子の数が常に nであるような木をn分木(nぶんぎ; n-ary tree)という。特に二分木はいくつかのアルゴリズムと密接に関わるデータ構造である︵ただし大抵は次で述べる有向木による二分木︶。有向木[編集]
一般に、無向木は任意の点を根とみなすことができる。それに対し有向木は、根である点をただ1つだけ持つ。辺の向きとして、根から葉に向かっている場合と、葉から根に向かっている場合とがある。混在はできない︵混在してしまうと閉路ができてしまう︶[2]。 閉路を持たない任意の有向グラフは有向非巡回グラフ︵Directed Acyclic Graph、DAG[3]︶である。有向木は連結な有向非巡回グラフでもあるが、連結な有向非巡回グラフが必ずしも有向木とは限らない︵DAGでは子孫あるいは親の共有がある場合がある。そうするとそれは木ではない︶。脚注[編集]
- ^ ウィルソン 2007, p. 60.
- ^ データ構造などの実装としてはしばしば、Unixのファイルシステムにおける
..というディレクトリエントリなどのように、逆向きのリンクを持たせることがある。 - ^ 頻出するデータ構造であり、アクロニム風に「だぐ」と呼ばれることも多い。
参考文献[編集]
●ウィルソン, R. J.﹃グラフ理論﹄ 原書第4版、西関隆夫・西関裕子、近代科学社、2007年。ISBN 978-4-7649-0296-1。関連項目[編集]
●カクタスグラフ ●系統樹外部リンク[編集]
●Graph Theory (Reinhard Diestel)
| 典拠管理データベース: 国立図書館 |
|
|---|
