木 (数学)

グラフ理論における木構造について

数学、特にグラフ理論の分野において「木（tree）」とは、連結であり、かつ閉路を持たないグラフのことを指します。ここで言うグラフは、無向グラフを前提としています。有向グラフにおける木構造（有向木）も存在しますが、本稿では主に無向木について解説します。

森（Forest）について

木と密接な関係にある概念として「森（forest）」があります。森とは、閉路を持たないグラフのことで、必ずしも連結である必要はありません。したがって、木は明らかに森の一種です。逆に、森をより一般的な概念として捉え、連結な森を木と定義する場合もあります。

木の特徴づけ

n個の頂点を持つグラフTについて、以下の条件は全て同値です。

1. Tは木である。
2. Tは閉路を持たず、辺の数がn-1である。
3. Tは連結であり、辺の数がn-1である。
4. Tは任意の2つの頂点の間に、ただ1つの経路が存在する。
5. Tは閉路を持たず、任意の2頂点間に辺を追加すると、ただ一つの閉路が形成される。

木の性質

木Tには、以下のような重要な性質があります。

辺の追加と閉路の形成：木Tに含まれない辺eをTに追加すると、T+eには必ずeを含むただ一つの閉路ができます。この閉路上の任意の辺fを取り除くと、T+e-fは再び木となります。
端末点の存在：頂点が2つ以上ある木には、必ず2つ以上の端末点（次数1の頂点）が存在します。
再帰的な構造：木には必ず端末点があり、その端末点を取り除くと、元の木よりも頂点数が1つ少ない木が得られます。逆に、頂点数nの木は、頂点数n-1の木に新たな頂点と辺を1つずつ加えることで構成できます。

根付き木（Rooted Tree）

木の中から特定の頂点を「根」として指定することで、木構造に階層的な概念を導入できます。根を持つ木を「根付き木」と呼びます。根付き木は、家系図のような親子関係を表現するのに適しています。

根付き木の用語

親と子：頂点v1とv2が辺で結ばれており、v1がv2よりも根に近い場合、v1をv2の親、v2をv1の子と呼びます。
兄弟：同じ親を持つ頂点同士を兄弟と呼びます。
先祖と子孫：頂点v2と根を結ぶ経路上に頂点v1が存在する場合、v1をv2の先祖、v2をv1の子孫と呼びます。
葉：子を持たない頂点を葉と呼びます。
高さ：ある頂点と根との経路の長さをその頂点の高さと呼びます。また、木の中で最も長い経路の長さを木の高さと呼びます。

n分木（n-ary Tree）

nを自然数としたとき、葉ではない各頂点の子の数が常にnである木をn分木といいます。特に、子頂点の数が常に2である二分木（binary tree）は、多くのアルゴリズムで重要なデータ構造として利用されています。

有向木（Directed Tree）

無向木では任意の頂点を根として扱うことができますが、有向木では根となる頂点はただ一つに定まります。有向木における辺には向きがあり、根から葉に向かう場合と、葉から根に向かう場合が存在します。ただし、辺の向きが混在すると閉路ができてしまうため、有向木では辺の向きは一方向に統一されます。

有向非巡回グラフとの関係

閉路を持たない有向グラフは有向非巡回グラフ（DAG）と呼ばれます。有向木は連結な有向非巡回グラフの一種ですが、連結な有向非巡回グラフが必ずしも有向木であるとは限りません。DAGでは、子孫や親を共有するケースが存在し、そのような場合は木構造とはみなされません。

木構造は、データ構造やアルゴリズムにおいて非常に重要な役割を果たしています。その基本的な性質を理解することで、より高度な応用も可能になります。

参考文献

ウィルソン, R. J.『グラフ理論』 原書第4版、西関隆夫・西関裕子、近代科学社、2007年。ISBN 978-4-7649-0296-1.

関連項目

カクタスグラフ
系統樹

外部リンク

Graph Theory (Reinhard Diestel)

もう一度検索