閉路を持たない連結な無向グラフ。連結かつ 辺数 = 頂点数 - 1 であることと同値。

有向木 (arborescence) とは、有向グラフであり、ある頂点rが存在して、rの入次数は0, r以外の頂点の入次数は1 という条件を見たするもの。rを根(root)と呼ぶ。DAGである。

木や有向木上では様々な問題が効率的に解ける。MSOと呼ばれる表現で書ける広いクラスの問題は木上では全て線形時間で解ける、という理論的な結果もある。