树的性质

树的简洁定义：一个无环连通图就是树，其是最简单的非平凡图类型

平凡图
平凡图指只有一个顶点且没有边的图，非平凡图至少有两个顶点和一条边。

树的性质一

记具有n个节点的图为T，则有以下论断等效：

• (i) T是树
• (ii) T无环，且具有$n-1$条边
• (iii) T连通，且具有$n-1$条边
• (iv) T连通，各边都为桥(bridge)
• (v) T中任意两节点都仅被一条路径(path)连接
• (vi) T无环，但如果添加任意条新边则会产生一个环

证明
(i)$\Rightarrow$ (ii)：由定义树无环；如果边数小于$n-1$则无法形成树，大于则成环
(ii)$\Rightarrow$ (iii)：无环，假设不连通则整个图由至少两个以上的树组成，则边数为$n-m$，矛盾；因此图连通，具有$n-1$条边
(iii)$\Rightarrow$ (iv)：T连通，任意删除其中一条边则形成两个孤立树，因此各边皆为桥
(iv)$\Rightarrow$ (v)：桥和唯一相连路径等效
(v)$\Rightarrow$ (vi)：如果T有环，则可能存在有两条路径相连的节点，矛盾
(vi)$\Rightarrow$ (i)：如果T不是树，添加任意一条新边则可能无法产生一个环，矛盾

由握手引理还可以得出具有n个节点的树度为：$2(n-1)$

树的性质二

如果T是连通图G的生成树(spanning tree)，则：

• (i) G的任意割集(cutset)都与T有共边
• (ii) G的任意环都与T的补图(complement of T)有共边

证明
G的任意割集都能将G分为两个独立部分，而T中任意删除一条边也能将T分为两个独立部分，因此T中任意一条边都存在于G的割集之中，证毕
假设G的任意环都与T的补图无共边，则其必与T共边，这表明T中存在环，矛盾因而证毕

基本环集(Fundamental Set of Cycles)与基本割集(Fundamental Set of Cutsets)：

• 基本环集(Fundamental Set of Cycles)：对于图G中任意一条不属于生成树T的边（称为弦），当把这条弦添加到T中时，会且仅会形成一个唯一的环。这个环是由该弦以及T中连接该弦两端点的唯一路径所构成。所有通过这种方式（即分别添加G中每一条弦）形成的环的集合，就称为与生成树T关联的基本环集；每条弦对应一个基本环，因此基本环集中环的数量等于G中弦的数量。
• 基本割集(Fundamental Set of Cutsets)：对于生成树T中的任意一条边（称为树枝），如果将它从T中移除，T的顶点集将被分割成两个不相交的集合$V₁$和$V₂$。此时，所有在原图G中连接$V₁$和$V₂$中顶点的原有边的集合，就构成一个割集。通过这种方式（即分别移除T中每一条树枝）得到的所有割集的集合，称为与生成树T关联的基本割集。每一条树枝对应一个基本割集，因此基本割集中割集的数量等于T中树枝的数量。

树的计数问题(Counting Trees)

数化学结构树

“树”这一结构在化学领域的早期经典应用就包括对烷烃（alkanes）的同分异构体进行计数，该问题可以通过忽略氢原子、只关注碳骨架实现简化，因为氢原子的作用就是补充连接到碳原子上，使每个碳原子的度数都达到4。

关键论证：一个$CₙH₂ₙ₊₂$分子所对应的图是一棵树。

证明：该图是连通的。其顶点数$v = n (碳) + (2n+2) (氢) = 3n+2$。其边数$e = (n×4 + (2n+2)×1) / 2 = 3n+1$。由于满足了$边数 = 顶点数 - 1 (e = v-1)$的条件，因此该图必然是一棵树。

数无向标号树

凯利定理(Caley’s Theorem)：对于具有$n$个节点的树，具有$n^{n-2}$个互不相同的标号树

证明
方法一：Prüfer 序列法
Prüfer 序列是一个长度为$n-2$的整数序列，输入是一个$n$个节点的带标号树，长度为$n-2$的Prüfer序列，重复 n-2 次以下步骤：

1. 找到当前树中度为 1 的最小标号节点（叶子）
2. 记录与其相连的节点编号
3. 删除该叶子节点

从序列恢复树的方法
给定长度为 n-2 的序列$P = (p₁, ..., pₙ₋₂)$：

1. 初始化每个节点的度数为 1，加上它在 P 中出现的次数
2. 对于序列中的每个$pᵢ$：
   • 找出当前度数为1的最小编号节点$v$
   • 添加边$(v, pᵢ)$
   • 更新度数
3. 最后剩下两个节点，连接它们

结论

• 每个长度为$n-2$的序列对应唯一一棵标号树
• 总数 =$n^{(n-2)}$

方法二：矩阵树定理法 拉普拉斯矩阵定义
对于无向图 G：

• $L = D - A$，其中
  • D为度数矩阵（对角线上为节点度数）
  • A为邻接矩阵

矩阵树定理

• 从拉普拉斯矩阵$L$中删除任意一行和对应列，得到$L*$
• 所有$生成树数 = det(L*)$

对完全图$Kₙ$的应用

• 每个点的度为$n-1$
• 邻接矩阵中除对角线外全为 1
• 拉普拉斯矩阵：$L = nI - J$（$J$为全1矩阵）
• $det(L*) = n^{(n-2)}$

因此完全图$Kₙ$中的$生成树数量 = n^{(n-2)}$，与Cayley定理一致

方法三：递归计数法 设$Tₙ$表示$n$个带标号节点能组成的树的数量，固定一个节点（如编号 1）作为根，剩余$n-1$个节点构成若干棵子树；假设划分为$k$个子集，大小为$n₁, n₂, ..., n_k$，满足$n₁ + ... + n_k = n - 1$
构造方法为：

• 每个子集可构成$Tₙᵢ$棵树
• 编号有组合方式：$C(n-1, n₁, ..., n_k)$
• 总数累加所有划分：$T_n = \sum C(n-1, n_1, ..., n_k) \times T_{n1} \times ... \times T_{nk}$

使用生成函数或归纳解得：$Tₙ = n^{(n-2)}$

推论：$K_{n}$的生成树数量为$n^{(n-2)}$

证明
对于任意具有n个节点的标签树都关联一个$K_{n}$的生成树，因此得证

矩阵树定理(matrix-tree theorem)：令G为一个具有节点集$\{ v_1,v_2,\cdots,v_n \}$的简单图，令$M=(m_{ij})$是满足$m_{ii}=deg(v_i)$的$n \times n$矩阵，如果节点$v_i$和$v_j$相邻则$m_{ij}=-1$，否则$m_{ij}=0$。则G的生成树数量等于M中任意元素的代数余子式(cofactor)。

补充：代数余子式的计算方法
$C_{ij}=(-1)^{i+j} \cdot det(M_{ij})$

树计数问题的应用

树计数问题的应用包括：最小连接容器问题，该问题引出了对贪心算法的研究；树搜索问题，引出了对广度优先搜索和深度优先搜索的研究；电网络的分析，引出了电流和电压定律；具体内容后续在遇到时会进行补充。