木

【き (tree)】

閉路を含まない連結なグラフを木という. 連結なグラフ $G=(V,A)\,$ に対して, $G\,$ の部分グラフであって点集合 $V\,$ をもつ木を, グラフ $G\,$ を張る木(spanning tree)といったり, グラフ $G\,$ の全域木, 極大木, 全張木あるいは, 単にグラフ $G\,$ の木などという. 根と呼ばれる1点が指定された木を根付き木(rooted tree)という. さらに, 根付き木は, (有向グラフとして)枝の向きに沿って根からすべての点に行くことができるとき, 有向木(directed tree)と呼ばれる.