树（图论）
shù (tú lùn)
树是没有圈的连通图,其中任意两个顶点之间恰好由一条路径连接。
Formula
|E| = |V| - 1
Definition
树是没有环路或圈的连通图；就像真实的树或家谱一样，它从一个根出发向外分支，没有循环路径回到起点。$n$ 个顶点上的一棵树恰好有 $n-1$ 条边，是连通的，且没有圈，这三条性质中任意两条都能推出第三条；一个连通图的生成树是包含所有顶点且本身是树的子图。树 $T = (V,E)$ 的等价刻画有：连通且 $|E|=|V|-1$；无圈且 $|E|=|V|-1$；或者任意两个顶点之间由唯一一条路径连接；卡塔兰数计算的是有 $n+1$ 个叶子的满二叉树的数目。
Example
家谱是一个图，每个人是一个顶点，亲子关系是边，没有圈，因为你不可能是自己的祖先。克鲁斯卡尔算法和普里姆算法找出加权图的最小生成树（MST），即总边权重最小的生成树，被用于网络设计以最小化电缆长度。凯莱公式指出，$K_n$（$n$ 个顶点的完全图）的生成树数目为 $n^{n-2}$；普吕弗序列通过在带标号的树与长度为 $n-2$ 的序列之间建立双射，证明了这一公式。
Key Insight
树是最简单的连通图，无处不在：文件系统、组织架构图、编译器中的语法分析树，以及机器学习中的决策树。在数据结构中，平衡二叉搜索树（AVL 树、红黑树）维持对数级别的高度，保证 O(log n) 的搜索时间，这正是二分查找高效的原因。