《图论导论》树
树的性质
树的简洁定义：一个无环连通图就是树，其是最简单的非平凡图类型
平凡图
平凡图指只有一个顶点且没有边的图，非平凡图至少有两个顶点和一条边。
树的性质一
记具有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 的最小标号节点（叶子）
- 记录与其相连的节点编号
- 删除该叶子节点
从序列恢复树的方法
给定长度为 n-2 的序列$P = (p₁, …, pₙ₋₂)$：
- 初始化每个节点的度数为 1，加上它在 P 中出现的次数
- 对于序列中的每个$pᵢ$：
- 找出当前度数为1的最小编号节点$v$
- 添加边$(v, pᵢ)$
- 更新度数
- 最后剩下两个节点，连接它们
结论
- 每个长度为$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})\)
树计数问题的应用
树计数问题的应用包括：最小连接容器问题，该问题引出了对贪心算法的研究；树搜索问题，引出了对广度优先搜索和深度优先搜索的研究；电网络的分析，引出了电流和电压定律；具体内容后续在遇到时会进行补充。