木

閉路を持たない連結なグラフ。

性質#

$n$ 頂点の木は

• 辺がちょうど $n-1$ 本
• どの 2 頂点にも道がちょうど 1 本
• 辺を 1 本足すと閉路ができ、1 本除くと非連結になる

「連結を保つ最小限の辺」がちょうど木。

根付き木#

1 つの頂点を根として向きを付けたもの。 親子関係が定まり、階層構造を表せる。

このノート自体も木構造で、 notes/ のディレクトリ階層がそのまま根付き木になっている。

計算機科学での用途#

用途	例
探索	二分探索木、B 木
構文	抽象構文木
探索空間	分枝限定法の探索木
決定	決定木、ランダムフォレスト
ファイル	ディレクトリ階層

分枝限定法が実用的になるのは、 限定操作で木の大部分を刈れるから。 木の全ノードを訪れれば全探索と変わらない。

参考文献#

• Thomas H. Cormen et al. Introduction to Algorithms, 4th ed. MIT Press, 2022. https://mitpress.mit.edu/9780262046305/introduction-to-algorithms/
• Kenneth H. Rosen. Discrete Mathematics and Its Applications, 8th ed. McGraw-Hill, 2019. https://www.mheducation.com/highered/product/discrete-mathematics-applications-rosen/M9781259676512.html