形式陈述

图 $T=(V,E)$$T=(V,E)$ 是树，当且仅当它连通且无环。对有限图，这还等价于任意两顶点之间有唯一简单路径，以及 $T$$T$ 连通且 $|E|=|V|-1$$|E|=|V|-1$。

直觉

树用恰好足够的边把所有顶点连起来：删掉任意边会断开，加入任意新边会产生环。

例子与边界

文件目录和无环的组织层级可建模为有根树。单个顶点也是树。现实中的“家族树”若允许表亲婚姻可能产生环，便不再是图论意义的树。

推论与应用

树支撑递归分解、搜索树、语法树、最小生成树以及网络广播结构。

参考资料

• Reinhard Diestel, Graph Theory, 5th ed., §1.5.
• Douglas B. West, Introduction to Graph Theory, 2nd ed., §2.1.