图论学习笔记——树

图论 树

《离散数学2》图论学习笔记——树部分。

写在前面

（我们所学的）图论应该是充满直观的一门学科，而数学的抽象只是辅助于计算和证明的工具。因此希望读者能够在阅读的时候先把握直观的图论观点，随后再运用数学方法去进行深入和严谨的探讨。

本文写作时也秉持了这一原则。

读者在阅读时，应该先把握引用块外的主线逻辑，除非常关键的情况外均可以接受未加证明的定理；在之后再去阅读和理解引用块内的具体证明。

基本定义和概念

以下假定读者已经对于图论的概念有基本的了解。

以下定义和概念都是对于无向图而言。

• （森）林：不含任何回路的图 $G(V,E)$。

• 树：联通，但不含任何回路的图 $G(V,E)$ 。

  注意：有向图的“连通”一般指“弱联通”，即刨除方向后的联通；有向图强联通的概念不在这里介绍。

  • 树枝：树的边。
  • 树叶：树中度数 1 的节点。
  • 分支节点（内节点）：树中度数大于 1 的节点。

树的其他等价定义

以下六个对树的定义等价。

1. （G 联通，且无回路）

   6->1: 若不联通，加入存在一条边后必然没有回路。

2. G 的任意两个顶点之间存在唯一路径

   1->2: 若有两条路径，异或则可得到一条回路。

3. G 中无回路，且 $m = n-1$

   2->3: 若存在回路，则必然能找到不唯一路径；归纳法，利用点边和连通性证明 $m = n-1$ 。

4. G 是联通的，且 $m = n-1$

   3->4: 若不连通，不可能有 $n-1$ 这么多条边。

5. G 是联通的，且 G 中任意边都是桥

   4->5: 证明若只有 $n-2$ 边，不可能联通。

6. G 中无回路，且加入任意一条边能在图中得到唯一一条含新边的回路

   5->6: 无回路显然，故利用 (1) 其是树；利用 (2) 中，树有唯一路径得到唯一回路（这个证明不好）

支撑树

• 支撑树：图 $G(V,E)$ 支撑子图 $T$ （即图 $T$ 边的端点集合之并为 $V$），且 $T$ 为树。

  • 树边：$G$ 的在 $T$ 中的边。

• 余树：$G-T$，即图刨除任意支撑树的边。

  • 余树边（树的弦）：$G$ 在余树中的边。

性质：支撑树与余树一一对应。（用在后面支撑树生成，只要枚举出余树也就枚举出了支撑树）。

基本关联矩阵与支撑树计数

以下关联矩阵、基本关联矩阵都是对有向图而言。对于无向图，一般可以给每条边指定一个方向，大部分方法可以套用。

【其实支撑树计数问题应该是基于无向图的，使用指定边的方向转化为有向图求解。这和课本的逻辑有微小的差距。】

关联矩阵

每一列代表一条边，如果边从 $v_i$ 指向 $v_j$ ，那么该列第 $i$ 行填 $1$ ，第 $j$ 行填 $-1$ ，其余均为 $0$ 。 $n \times m$ 矩阵。

用 $B$ 来代表关联矩阵。

关联矩阵是一种表示边点关系的方式。边和点可以构成“回路”，树恰好不要“回路”，那么运用一点微小的线性代数知识，我们可以获得如下的结论，从而帮助我们以数学视角探究一些图的性质，并计算支撑树数目。

性质1：关联矩阵与回路

关联矩阵的 $k$ 列线性相关 $\Leftrightarrow$ 对应的 $k$ 条边中存在回路。

证明：这几乎是显然的，将回路对应的边调整好方向（也就是把列乘上 $1$ 或者 $-1$），从而可以顺序连接；把这些列相加可以得到 $0$ 列。

性质2：关联矩阵的秩

关联矩阵的秩的图论意义是什么？根据上面的性质，上面最多能从图中挑出多少边，使它们的导出子图上没有回路。

对于有向【联通！】图的关联矩阵 $B$ ：

1. $\text{rank}(B) < n$ 。这是说，任意 $n$ 条边的导出子图中均存在回路。

   证明：线性代数来说，可以把所有行（$n$ 行加到一起，每个位置都是 $0$（每列只有一个 $1$ 和一个 $-1$），因此线性相关）。

2. $\text{rank}(B) = n-1$ 。这是说，一个图一定存在 $n-1$ 条边，他们的导出子图没有回路。根据上面的等价定义，这也就是说，（联通图的）支撑树一定存在。

   证明：从线性代数视角，考虑若干行（注意，是行！）的线性组合。如果他们的和是 $0$，且存在一个系数非 $0$ ，那么根据连通性，所有行对应的系数都是一样的（因为每列只有一个 $1$ 和一个 $-1$，这两行的系数必然相同，又因为联通，可以走到所有的 $n$ 行）。所以所有行的系数都非 $0$ ，也就不存在 $n-1$ 行的线性组合是 $0$ 。

   重要的结论：关联矩阵的任意 $n-1$ 行，他们都不线性相关。这保证了下面基本关联矩阵相关性结论的正确性。

基本关联矩阵

在关联矩阵 $B$ 中划掉第 $i$ 行（$1 \leq i \leq n$ ，$i$ 是任选的），得到基本关联矩阵 $B_i$ 。

注意，基本关联矩阵和关联矩阵含有相同量的信息，根据基本关联矩阵我们可以推出关联矩阵。这一点可以和 $\text{rank}(B) = n-1$ 共同理解。

理解基本关联矩阵，核心的问题是：为什么要删掉 $1$ 行呢？ 这就需要进入数学的视角来考察“树”。

因为在数学上，图“有无回路”的特征（也就是树的特征）用的是关联矩阵的线性相关性来刻画，而这一线性相关性可以用行列式来在数值上刻画，而行列式只能运用于方阵。

因此我们想要判断 $n-1$ 条边是否构成树（也就是判断关联矩阵中对应 $n-1$ 列是否线性相关），为了使用行列式来刻画这 $n-1$ 列的线性相关性，我们只需要 $n-1$ 行，因此是需要删除一行的。如果行列式不是 $0$ ，那么这就是一棵树；若行列式为 $0$ ，则不是。

然而，我们可以敏感的发觉“删除一行”的操作可能会出现问题。删除掉一行之后，这 $n-1$ 列的线性相关性是否还能保持 ？答案是确定的，详细证明如下。

证明：

1. 有一个方向是显然的：从线性代数视角来看，如果原来的 $n-1$ 列线性相关，那么删掉一行（也就是减少一个维度）之后这 $n-1$ 列仍然线性相关；
2. 另一个方向略显困难：如果原来关联矩阵的 $n-1$ 列线性无关，那么删掉一行之后，在基本关联矩阵中这 $n-1$ 列仍然线性无关吗？如果删掉某行后不是线性无关，那么存在这些列的线性组合使得到的列中该行位置的元素不是 $0$，该行之外位置的元素全都是 $0$ 。那么关联矩阵的这 $n-1$ 列的线性组合后的元素和不为 $0$ ；这与关联矩阵中每一列所有元素和都是 $0$ 矛盾。

在用行列式刻画基本关联矩阵中取出来 $n-1$ 列的线性相关性的时候，我们注意到一个很好的性质：这样的行列式只会是 $\pm1$ 或 $0$ 。直观理解的话，因为矩阵很稀疏且只有 $\pm 1$ 的非 $0$ 元，所以代数余子式展开的时候不会很大。详细证明如下。

证明：使用数学归纳法，对阶数进行归纳。（略，待补）

这一结论（线性无关是 $\pm 1$ ，相关是 $0$ ）在下文计数时提供了很大的便利（平方后算术加和即可得到非零的“个数”）。

支撑树计数

有一个近乎显然的做法：我们枚举基本关联矩阵抽出任意 $n-1$ 列构成的子阵（它是方的），如果它的行列式不是 $0$（那么就是 $1$ 或者 $-1$ ，它的平方一定是 $1$ ），那么代表这 $n-1$ 列对应的 $n-1$ 条边可以构成一棵支撑树。

证明：行列式不是 $0$ $\Rightarrow$ $n-1$ 列线性无关 $\Rightarrow$ 边导出的图没有回路 $\Rightarrow$ 是一棵树

那么我们把所有的对应的行列式的平方求和即可得到某图中支撑树的数目。

接下来所有的事情都是为了加速（至少在形式上“加速”）这一过程。

比内-柯西（Binet-Cauchy）定理

首先做一些纯粹数学上的准备。

对于 $A = (a_{ij})_{m \times n}, B = (b_{ij})_{n \times m} (m \leq n)$ ，

我们有 $\det(AB) = \sum\limits_{S}\det(A_{S}B_S)$ ，其中 $S \subseteq \{1,2,\cdots, n\}, |S| = m$ ；

关于记号的说明：$A_S$ 表示从 $A$ 中挑选 $S$ 集合下标的 $m$ 【列】构成的 $m \times m$ 方阵；$B_S$ 同理表示从 $B$ 中挑选同样 $S$ 集合下标的 $m$ 【行】构成的 $m \times m$ 的方阵。

证明：（略，不打算补）

利用基本关联矩阵：无限制支撑树计数

利用上面的定理，我们可以巧妙的加速以上运算（或者至少让看起来的形式简洁一点）。

我们令 $B_i$ 为点 $v_i$ 对应（把 $v_i$ 对应的行删掉）的基本关联矩阵。则：

$$\det(B_i{B_i}^T) = \sum\limits_S \det({B_i}_S {{B_i}_S}^T) = \sum_\limits{S} \det({B_i}_S)^2$$
注意到，这个式子可以和上文的“显然的做法”对应： $\sum\limits_{S}$ 对应中的“枚举 $n-1$ 列”，${B_i}_S$ 对应挑出来的 $n-1$ 列构成的方阵。

于是：$\det(B_i {B_i}^T)$ 即为图的支撑树个数。

带限制条件的支撑树计数

有的时候，我们会对支撑树做出一些限制，而为了计算符合条件的支撑树个数，我们需要对上面的方法进行一些微小的特异化。

包含或不含特定边的支撑树计数

不含 $e$ 的支撑树：删去边 $e$ 之后，按照新图构造关联矩阵与基本关联矩阵（其实就是从原来的矩阵里面删掉一列）进行计算。

包含 $e$ 的支撑树：

1. 把 e 两边的点缩成一个点，再进行计算
2. 所有支撑树 - 不含 $e$ 的支撑树 = 含 $e$ 的支撑树

以特定节点为根的支撑树计数

再次申明，这一概念只适用于有向图。

严格来说，“对于一棵树，其以 $v_i$ 为根” 当且仅当 “这棵树中， $v_i$ 的负度为 $0$，剩余所有节点的负度均为 $1$ ”。

以直观的视角来看，“对于一棵树，其以 $v_i$ 为根” 当且仅当 “对于一棵树，将 $v_i$ 放在最上面，按照“重力”下垂，所有的边都由上指向下”。【“重力下垂”是个很强的条件，仅仅拥有“从上向下”的边并不能保证得到的是树，只能保证得到的是有向无环图】

我们需要想办法排除掉所有不符合根条件的支撑树。也就是对关联矩阵进行修改（具体来说，就是把所有 $1$ 置为 $0$ ），使得所有不满足根条件的支撑树所对应的 $n-1$ 阶子式的行列式变为 $0$ ；满足条件的仍是它本身。

后者我们通过可以给有根树的点和边重新编号，使 $v_1$ 为根，使所有的边 $e_j = (v_i,v_j)(j = 2,3,\cdots,n)$ 都有 $i < j$ 。注意到如此编号的话，在图关于 $v_1$ 的基本关联矩阵（也就是删去了第一行）中，这棵以 $v_1$ 为根的有根树对应的 $n-1$ 阶矩阵是上三角矩阵（因为 $i < j$），且对角线均为 $-1$ ，$1$ 只能在严格上三角的位置，因此删除所有的 $1$ 不会改变行列式的值。

边和点的重新编号，体现在矩阵/行列式的数学视角里面是什么呢？对边的重新编号是列交换，对点的重新编号是行交换。

以上三个操作都不改变行列式的值，

前者不太好说【书上直接“显然”了】：首先如果一棵支撑树，不是以 $v_r$ 为根的有根树，那么必然存在节点 $v_j,v_j \neq v_r$ 的负度为 $0$ （利用 $\sum_\limits{i}{{d^-}(v_i)} = m = n-1$），即 $v_j$ 对应的行全为 $0$ （因为正度的 $1$ 全被删掉了），有全 $0$ 行的矩阵的行列式必然为 $0$。【其实这也有点图论视角。】

从图论的视角来看这个问题更加明显一点。去除所有 $1$ 后，（基本）关联矩阵本质上只表示负度，也就是某行的 $-1$ 的个数表示该行对应的点的负度度数，每列有且仅有一个 $-1$ 。而根据有根树的定义，对于一棵树，其以 $v_i$ 为根 当且仅当 $v_i$ 的负度为 $0$ 且剩余所有节点的负度均为 $1$ 。那么转化成数学表示的话，后一个条件就是 $n-1$ 阶方阵每一行、每一列有且仅有一个 $-1$ 。我们知道，这是一个置换矩阵，行列式是 $\pm 1$ 。这样想可以使两方面的推导都更加自然。

所以结论： 且令 $\vec{B_i}$ 表示将 $v_i$ 对应的基本关联矩阵中所有的 $1$ 置成 $0$ 之后的矩阵，那么以 $v_i$ 为根的数的个数就等于 $\det(\vec{B_i}{B_i}^T)$ 。

至于为什么不采用 $\det(\vec{B_i}\vec{B_i}^T)$ 作为表达式？

因为上文关于 $\vec{B_i}$ 中 $n-1$ 阶子阵行列式变化视角和图论视角下的讨论，都是基于挑出来的列对应的边能构成一棵树的前提下进行的。而如果缺乏这个前提，上文的讨论是不能成立的。本质上来说，就是 “$v_i$ 的负度为 $0$ 且除了 $v_i$ 的点负度均为 $1$ ”的条件（删去 $v_i$ 行，再挑出来满足这样条件的边对应的的 $n-1$ 阶子阵的行列式不是 $0$ 哦！）并不能确保这些边的导出子图为一棵树。容易想到的反例就是一棵有根树 + 一堆环。

---

以上两种形式的约束可以组合。值得提到的是，包含某条边的特定节点的支撑树计数，有一种较为简单的办法：把该边指向的节点的其余所有入度都删掉。

矩阵树（Matrix Tree）定理

一种较为简便求解支撑树计数问题的方法。

对于无向图 $G(V,E)$ ，定义拉普拉斯矩阵 $L_{n \times n}$：

$$L_{ij} = \left\{\begin{aligned}-m_{ij}&,i \neq j\\\text{deg}(v_i)&,i = j\end{aligned}\right.$$
其中 $m_{ij}$ 表示 $v_i$ 与 $v_j$ 之间的边数。

则该无向图 $G$ 的支撑树个数则为 $t(G) = \det(L_i)$ ，$L_i$ 为去掉第 $i$ 行和第 $i$ 列后得到的矩阵，$i = 1, 2, \cdots, n$。

或者，用特征值表示：找出 $L$ 的 $n-1$ 个非 $0$ 特征值 $\lambda_1 , \cdots,\lambda_{n-1}$， 那么 $t(G) = \frac{1}{n} \prod\limits_{1 \leq i \leq n-1} \lambda_i$

这一定理的本质是找到了一个对于关联矩阵与其转置乘积结果的简洁表达，因此在 $m$ 较大时能节省出很多的时间。具体证明如下：

引理1: $BB^T = L$

证明：$(BB^T)_{ij} = \sum\limits_{e_k \in E} B_{ik} {B^T}_{kj} = \sum\limits_{e_k \in E} B_{ik}B_{jk}$

1. 当 $i=j$ 时，显然只有 $e_k$ 邻接与 $i$ 的时候， $B_{ik} = \pm1$ ，其余时候均为 0 ；故求和即为与 $i$ 邻接的边的个数，即 $deg(v_i)$ 。
2. 当 $i \neq j$ 时，$B_{ik} \neq 0$ 且 $B_{jk} \neq 0$ 当且仅当 $e_k$ 连接 $v_i$ 与 $v_j$ ；而 $B_{ik}$ 与 $B_{jk}$ 显然一者为 $1$ ，一者为 $-1$，故乘积为 $-1$ ，求和后即为 $-m_{ij}$ 。

引理2：$B_i{B_i}^T = L_i$

证明：这几乎是显然的。

关于有根树的矩阵树定理，在这里不加证明的展示以下结论：

对于有向图 $G(V,E)$ ，定义出度拉普拉斯矩阵 $L^\text{out}$ ：（$n \times n$）

$$> {L^\text{out}}_{ij} = > \left\{\begin{aligned}-m_{ij}&,i \neq j\\\text{deg}^{\text{out}}(v_i)&,i = j\end{aligned}\right. >$$
其中 $m_{ij}$ 为从 $v_i$ 指向 $v_j$ 的有向边条数。

同理可以定义入度拉普拉斯矩阵 $L^{\text{in}}$ 。

定义 ${L^{\text{out}}}_i$ 为 $L^\text{out}$ 去掉 第 $i$ 行和第 $i$ 列得到的矩阵；那么以 $v_r$ 为根节点的有根树个数即为 $t^{root}(G,r) = \det({L^{out}}_r)$ 。

同理可以定义 ${L^{\text{in}}}_i$ ，则以 $v_r$ 为叶节点的有根树数目即为 $t^\text{leaf}(G,r) = \det({L^{\text{in}}}_r)$。

回路矩阵、割集矩阵与支撑树生成

我们已经会算出一个图中的支撑树个数，我们自然也想知道这些支撑树的具体形式。

很明显，如同上文的计数是有很简单的方法的。我们枚举所有可能的 $n-1$ 条边，检测这 $n-1$ 条边是否是一条支撑树。然而，如果两棵（可能是）“树”的图有很多条共同的边，那么他们的结构是十分类似的，很有可能都是树或都不是树。然而如上的检测方法并没有利用到这一点。

---

对于一个图，图中的回路和割集，分别对应了支撑树的两条性质：“无回路”，“联通”的两个性质。这启发我们，回路/割集与支撑树之间是否有某种形式上的对应关系？是有的。

如果我们已经有图 $G$ 的一棵支撑树 $T$ 和余树 $G-T$ ，那么：

1. 对于某一条余树边，存在唯一的树边集合的子集，使它们的并构成一条回路；

2. 对于某一条树边，存在唯一的余树边集合的子集，使它们的并构成一个（边）割集。

正确性证明如下：

证明：

因此换个思路，对于一个图，如果我们找到若干[1]的回路 / 割集，同时把所有的边分成两部分（也就是可能的“树边”，必然是 $n-1$ 条边 和 “余树边”，必然是 $m-n+1$ 条边）之后，回路 / 割集 的边的分布正好与上面的契合[^2]，那么我们就可以确定这样的边集合划分是能构成一个支撑树的。

总而言之，这部分的目的是：建立从支撑树到若干回路/割集之间的一一对应关系，从而能够服务于我们计算出支撑树的具体模样。

---

为了使我们的研究更加清晰严谨，我们沿袭上面的方法，继续用矩阵的线性代数工具。

基本概念

将回路/割集与其的边关联，再竖着垒到一起，就构成了回路和割集矩阵，表示若干回路 / 割集。两者概念颇多相似，下面用一个表格来概括相关概念，方便读者辨析其概念异同。

补充一个概念：回路/割集的“独立”。若干回路独立，即不存在其中的若干回路，其边集异或为空集（或某一些回路的异或是另一个）。

以下讨论中，图为 $G(V,E)$ ，$|V|= n,|E| = m$ 。

内容	回路	割集
集合	忽略方向可以首尾相连的，初级的[1]，边集。	忽略方向，删去后联通块个数增加[^6]的，极小的，边集。
方向	在两个方向中[^4]，可以给回路指定一个方向。 回路的方向与回路中边的方向， 要么相同，要么相反。	在两个方向中，可以给割集指定一个方向。[^7] 割集的方向与割集中边的方向， 要么相同，要么相反。
矩阵	用 $k \times m$ 的矩阵来表示图中的某 $k$ 条回路。 每行代表一条回路，每列代表一条边； $a_{ij}$ 代表 $c_i$ 与 $e_j$ 的相关关系； 不相关为 $0$，相关同向为 $1$，不同向为 $-1$。	用 $l \times m$ 的矩阵来表示图中的某 $l$ 个割集。 每行代表一个割集，每列代表一条边； $b_{ij}$ 代表 $s_i$ 与 $e_j$ 的相关关系； 不相关为 $0$，相关同向为 $1$，不同向为 $-1$。
完全 矩阵	图中所有的回路，按以上方法构成矩阵 $C_e$ 。	图中所有的割集，按以上方法构成矩阵 $S_e$ 。
基本 矩阵	给定一棵支撑树 $T$，包含仅一条余树边的回路， 令回路方向与该余树边相同， 共 $m-n+1$ 条（如何证明？）。 令其为 $C_{f}$ 。	给定一棵支撑树 $T$，包含仅一条树边的割集， 令割集方向与该树边方向相同[^8] 共 $n-1$ 个（如何证明？） 令其为 $S_{f}$ 。
(独立)[^5] 矩阵	$m-n+1$ 条独立的回路。	$n-1$ 个独立的割集。

回路/割集矩阵性质

性质 1 ：回路/割集矩阵 与 关联矩阵 的关系

当关联/回路/割集矩阵对于边的编号相同时，有 $B{C_e}^T = 0$ ，$S_e{C_e}^T = 0$ 。或者可以理解为， $\mathbf {b_j} (\mathbf{c_i})^T = 0$, $\mathbf{s_j}(\mathbf{c_i})^T = 0$ 。（$\mathbf {b_j}$ 是关联矩阵对应任意节点的行向量， $\mathbf{c_i}$ 是回路矩阵中对应任意回路的行向量，$\mathbf{s_j}$ 是割集矩阵中对应任意割集的行向量）

证明：以图论视角来证明。两者的相乘是把同一条边对应的两个方面的数相乘。对于某个节点，一个回路带来的入度与出度之和一定是 0；对于一个割集割出来的点集合 A 与 B，一个回路中从 A 到 B 与从 B 到 A 的边数一定是相等的。

根据基本回路/割集矩阵的性质，我们可以给回路/割集以及边重新指定编号（体现在矩阵上就是交换行列），从而将基本回路/割集矩阵化为标准型：

$$\begin{aligned} C_f = \begin{bmatrix}I_{m-n+1} & {C_f}'\end{bmatrix};\;\; & {C_f}' \in \mathbb M_{(m-n+1)\times(n-1)} \\ S_f = \begin{bmatrix}I_{n-1} & {S_f}'\end{bmatrix};\;\; &{S_f}' \in \mathbb M_{(n-1)\times(m-n+1)} \end{aligned}$$

性质 2 ：回路/割集矩阵 的 秩、线性相关性

$\text{rank}(C_e) = \text{rank}(C_f) = m - n + 1$， $\text{rank}(S_e) = \text{rank}(S_f) = n-1$ 。

证明方法 1：（线性代数视角）。

一方面，基本回路/割集矩阵的秩，根据上文的“标准型变换”容易知道。而基本回路/割集矩阵的所有行都被包含在完全回路/割集矩阵中，因此 $\text{rank}(C_e) \geq m-n+1, \text{rank}(S_e) \geq n-1$ 。

另一方面，Sylvester 定理指出，若 $A_{n \times s},B_{s \times m}$， $AB = 0$，则 $\text{rank}(A) + \text{rank}(B) \leq s$ 。我们又有 $B{C_e}^T= 0$ ， 因此 $\text{rank}(B) + \text{rank}({C_e}^T) \leq m$ ，而我们上面已经知道 $\text{rank}(B) = n-1$ ，因此可以知道 $\text{rank}(C_e) = \text{rank}({C_e}^T) \leq m - n + 1$ 。因此 $\text{rank}(C_e) = m - n + 1$ 。再类似地，我们也可以推出 $\text{rank}(S_e) \leq n-1$ ，$\text{rank}(S_e) = n-1$ 。

证明方法2：也可以从图论视角来证明吗？

注：这也说明了最小的独立的回路/割集的个数，因为矩阵的行秩等于列秩，而回路/割集独立与线性相关性的关系式比较显然的。

性质 3 ：回路/割集矩阵与余树/树的对应关系

联通图 $G$ 的（独立）回路矩阵 $C$ 的任意一个 $m-n+1$ 阶子阵行列式非 $0$ $\iff$ 这些列对应的边组成 $G$ 的某一棵余树。

联通图 $G$ 的（独立）割集矩阵 $S$ 的任意一个 $n-1$ 阶子阵行列式非 $0$ $\iff$ 这些列对应的边组成 $G$ 的某一棵支撑树。

证明：

性质 4 ：基本回路/割集矩阵与（独立）回路/割集矩阵的联系

$C_f = P C$ ，其中 $P$ 可逆。$S_f = PS$ ，其中 $P$ 可逆。

证明：

支撑树生成

如最开头提到，支撑树和支撑树是类似的，这提醒我们用已知支撑树，对边集进行变换后来生成未知的支撑树。这就是 Mayeda 算法。（我们这里介绍的是非常朴素的 Mayeda 算法）

树与树的距离

支撑树 $T_1$ 与 $T_2$ 的距离，是 $|T_1 - T_2| = |T_2 - T_1|$ 。也就是在某一棵树而不在另一棵树的边的条数。

基本树变换

对于某棵支撑树 $T_1$ ，对于某条树边 $e_i$ 和 $e_i$ 对应的基本割集（ $S_{e_i}$ ？）中的某条边 $e'$ (当然，应该有 $e_i \neq e'$) ，称 $T_1 \rightarrow T_2 = T_1 -e_i + e'$ 为基本树变换。这记作 $T_2 = T_1 \oplus (e_i,e')$

下证：$T_2$ 是一棵支撑树。只需要证明其连通性，而这由割集的极小性容易知道。

对于某条树边 $e_i$，定义 $T^{e_i}$ 为树 $T$ 在树边 $e_i$ 下所有可能的基本树变换可以得到的新树。

定义 $T^k = \bigcup T^{e_{i_1}\cdots e_{i_k}}$ ，即进行 $k$ 次基本树变换后能够能到的所有的树的集合。

两者的一致性

对 $T_1$ 进行一次基本树变换能够得到且仅得到所有与 $T_1$ 距离为 $1$ 的另一棵树 $T_2$。

证明：一个方向：得到的是树，距离为 $1$ ，前者已经证过，后者由定义容易得到。另一个方向，使用反证法证明 $e' \in T_2 - T_1$ 的边必在 $T_1$ 关于 $e \in T_1 - T_2$ 的基本割集中即可。

任何距离在 $k$ 之内的两棵支撑树，都可以通过 $k$ 次以内的基本树变换相互转化。这也就是说，$T^k$ 包含了所有距 $T$ 距离为 $k$ 的支撑树。

证明：根据 支撑树距离 的三角形不等式（这几乎是显然的，本质上是集合的对称差），只需要 $k=1$ 时成立即可，这在上面已经证明过了。

支撑树的生成

对于某一支撑树，所有支撑树都在 $n-1$ 的距离之内。因此，对任意（参考）树做 $n-1$ 次基本树变换，所有的支撑树就一定都能出现在 $T^{n-1}$ 中。

这个算法的问题在于，计算 $T^{n-1}$ 时有某些支撑树重复出现，然而这只是效率问题，书上就没有讨论了。

最短支撑树

当我们给图的每一条边都赋予边权，那么每一棵支撑树都有其边权和，那么也就有“权值之和最小的”支撑树。如何计算出这样的最短支撑树？我们有如下的两个贪心算法—— Prim 算法与 Kruskal 算法。

Prim 算法

用伪代码描述算法如下：

Prim 算法：
    令点集 S 为 『任意一点』；令边集 T 为 『空』。
    若〖|S| 小于 |V|〗：
        找到最短的边，使得——
            一个端点在 S 中，另一个端点在 V-S 中。
        将该边加入 T ；将该边在 V-S 中的端点加入 S 。
    回。
    T 为所求最小支撑树。
结束。

Kruskal 算法

用伪代码描述算法如下：

Kruskal 算法：
    令边集 T 为 『空』。
    按 边权从小到大 枚举每条边：
        若该边两端点不能于边集 T 内联通：
            将该边加入 T。
    T 为所求最小支撑树。
结束。

正确性证明

本节不必了解。

两者正确性的关键在于共同出现的 用最短边改善连通性 这个贪心操作，我们需要证明这样的操作不会毁掉我们的最小树性质。

如果我们能保证加入每条边之后，都是已经连接的点集的最小支撑（或者森林）；那么我们最后得到的就是一棵最小支撑树。

---

有一条非常重要的性质，对于证明的理解有很大的帮助：

定理：对于图 $G$ 中的一棵最小支撑树 $T$ ，任何树边 $e$ 都是其对应的割集（上文基本割集矩阵中确定的“割集”）中边权最小者；任何余树边都是其对应的回路（上文基本回路矩阵确定的“回路”）中边权最大值。

证明：使用反证法，如果不满足这样的条件，必然能找出一个更小的支撑树；具体读者自证不难。

---

具体来说，使用反证 + 归纳法。

Prim 算法能够保证当前选中的边集 $T$ 是点集 $S$ 的最小支撑树。

考虑某一次加点之前的点集是 $S_0$ ，边集是 $T_0$ ，$T_0$ 构成 $S_0$ 的最小支撑树；新加入的节点是 $v$ ，新加入的边是 $e$ 。假设 $T_0 + e$ 不构成 $S_0 + v$ 的最小支撑树，最小支撑树 $T \neq T_0 + e$ 中。则 $T_0$ 必然不包括 $e$ 。

节点 $v$ 与点集 $S_0$ 的联通方式。 如果 $v$ 与 $S_0$ 的连边数是 $1$ ，则包含该边的基本割集矩阵必然包含 $e$ 边，矛盾；如果 $v$ 与 $S_0$ 的连边数量大于 1。

---

Kruskal 算法能够保证当前选中的边集，对于每个联通块都是最小支撑树。

证明和 Prim 算法是类似的。

参考

• 戴一奇等：《图论与代数结构》，清华大学出版社。

• https://oi-wiki.org/graph/matrix-tree/

• https://zhuanlan.zhihu.com/p/108209378

• https://zhuanlan.zhihu.com/p/340464163