5. 木と有向木

木 (tree) は特に興味深いグラフである。木を特徴付ける性質の一例を示す:

• 与えられた頂点集合を持つ最小の連結グラフ

• 与えられた頂点集合を持つ最大の非閉路 (閉路を持たない) グラフ

有向木 (arborescence) は有向グラフにおいて木に最も近い概念である。

本章では木の理論を説明し、木の応用にも少し触れる。木のさらなる応用は理論的情報科学の講義で解説されることが多い。ただし、そういった場面では木の概念が本書のものと多少異なる。