图论2-树

摘要: 树的相关概念和定理，参考徐俊明《图论及其应用》

【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：潮汐朝夕
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

本文记录图论中的基本概念和定理，证明省略，本文是个备忘录，需要细节的时候再查相应的资料即可。

总览参考文章 图论导引，本文是树的内容。

树的概念中，涉及到一些对偶关系，可以对比着看：树与余树，边割集与圈集，割空间与圈空间(相关领域：拟阵)。

支撑树、图空间、关联矩阵中的一些概念可以对比着看，如下：

支撑树，圈集，割集的关系 <—> 图空间，圈向量，割向量的关系 <—> 关联矩阵所有行向量构成的向量空间，所有圈向量构成的向量空间，所有割向量构成的向量空间的关系

---

$1 树，森林

定义：不含圈的连通图称为树。不含圈的图称为森林。

定理：对于简单图 $G = (V, E)$，以下命题等价

• (1) G 是树
• (2) G 中任意两点之间恰好有一条路
• (3) G 中无圈，且 $|E| = |V| - 1$
• (4) G 连通，且 $|E| = |V| - 1$
• (5) G 连通，且对任意 $e \in E$，$G-e$ 不连通
• (6) G 中无圈，且对任意 $e \notin E$，$G+e$ 恰好有一个圈

推论：每棵非平凡树(顶点数大于1的树)至少含有两个度为1的顶点(叶子) 定理：记连通分量个数为 $\omega G$ 是林 $\Leftrightarrow |E| = |V| + \omega$ 推论：每无孤立点的森林至少含有 $2\omega$ 个度为1的顶点(叶子)

---

$2 生成树

定义：F 是 G 的一个生成子图，且 $\omega(F) = \omega(G)$，若 F 为一棵树，成 F 为 G 的一个生成树；若 F 是林，则 F 为 G 的生成林。

生成树和生成林的概念与边的方向无关。

定理：每个连通图都有生成树 定理(Cayley定理)：以 $V = [n]$ 为顶点集的标记树(顶点认为不同，同构的两棵树也视为2棵树)共有 $2^{n-2}$

---

$3 圈秩

• 定理：F是G的支撑林，若存在 $e \in E(G) \setminus E(F)$，则 $F+e$ 含有且仅含有一条圈
• 推论：图 G 中至少含有 $\epsilon - v + \omega$ 条不同的圈

定义：$\epsilon - v + \omega$ 为圈秩，也叫 Betti 数。

定义：H 是 G 的子图，$G - E(H)$ 称为 H 在 G 中的余图，记为 $\overline{H}(G)$ (注意与G 的补图的符号 $\overline{G}$ 区别)，F 是 G 的生成林或生成树，则 $\overline{F}(G)$ 称为余林或余树。

---

$4 边割集

定义：B 是 E 的非空子集。若存在 V 的非空子集 S，使得 $B = [S, \overline{S}]$，称 B 为 D 的边割集。若 B 的任何非空真子集都不是边割集，则 B 为 最小边割集，也成为键。边数为 1 的边割集称为割边，也成为桥(在 图论1-基本概念 中从连通分量个数的角度也定义过割边和桥，但是没有定义边割集)。

• 定理：F 是非空图 G 的生成林，$e \in E(F)$，则 (1) $\overline{F}(G)$ 不含键，(2) $\overline{F} + e$ 含有且只有一个键
• 推论：图 G 中至少含有 $v + \omega$ 个不同的键

---

$5 图空间, 加权图

D 为图，$V(D) = \{u_{1}, u_{2}, …, u_{n}\}$, $E(D) = \{e_{1}, e_{2}, …, e_{m}\}$

定义：D 的顶点空间 $\mathscr{V}(D)$：$V(D)$ 到 $\mathbb{R}$ 的所有函数的向量空间。 $dim \mathscr{V}(D) = |V|$

定义：D 的边空间 $\mathscr{E}(D)$：$E(D)$ 到 $\mathbb{R}$ 的所有函数的向量空间。$dim \mathscr{E}(D) = |E|$

对于顶点空间，考虑顶点空间中的一个函数 $\boldsymbol{f} \in \mathscr{V}(D)$，$\boldsymbol{f}(v_{i}) = x_{i}$ 为顶点的权。$\boldsymbol{f}$ 可以写成以下形式

$$\boldsymbol{f} = \sum\limits_{i=1}\limits^{|V|}x_{i}\boldsymbol{u_{i}} \\ 其中 \quad \boldsymbol{u_{i}} \in \mathscr{V}(D) \quad 且 \quad \boldsymbol{u_{i}}(v_{i}) = \left\{ \begin{array}{**lr**} 1, \quad j = i \\ 0, \quad j \neq i \\ \end{array} \right.$$

则 $\boldsymbol{u_{1}}, \boldsymbol{u_{2}}, …,\boldsymbol{u_{v}}$ 为 $\boldsymbol{V}$ 的一组基，$(x_{1}, x_{2}, …, x_{v})$ 为 $\boldsymbol{f}$ 在这组基下的坐标，记 $\boldsymbol{f} = (x_{1}, x_{2}, …, x_{v})$。

对于边空间，考虑边空间中的一个函数 $\boldsymbol{g} \in \mathscr{E}(D)$，$\boldsymbol{g}(e_{i}) = y_{i}$ 为边的权。$\boldsymbol{g}$ 可以写成以下形式

$$\boldsymbol{g} = \sum\limits_{i=1}\limits^{|E|}y_{i}\boldsymbol{a_{i}} \\ 其中 \quad \boldsymbol{a_{i}} \in \mathscr{E}(D) \quad 且 \quad \boldsymbol{a_{i}}(e_{i}) = \left\{ \begin{array}{**lr**} 1, \quad j = i \\ 0, \quad j \neq i \\ \end{array} \right.$$

则 $\boldsymbol{a_{1}}, \boldsymbol{a_{2}}, …,\boldsymbol{a_{v}}$ 为 $\boldsymbol{V}$ 的一组基，$(y_{1}, y_{2}, …, y_{v})$ 为 $\boldsymbol{g}$ 在这组基下的坐标，记 $\boldsymbol{g} = (y_{1}, y_{2}, …, y_{v})$。

在这两个空间中赋予内积，则空间中任何基中的两组向量是正交的。以下内容仅考虑无环图 D 的边空间 $\mathscr{E}(D)$

定义：设 $\boldsymbol{w} \in \mathscr{E}(D)$ 称 $(D, \boldsymbol{w})$ 为加权图。$\boldsymbol{w}$ 为权函数，$\boldsymbol{w}(e)$ 为边 e 的权。

权可以以邻接矩阵的形式给出，称为加权矩阵($\boldsymbol{w}(e_{i}) = 1$ 时加权矩阵就是邻接矩阵)。加权矩阵可以有距离矩阵，费用矩阵等意义。

符号：

• B 是 E 的子集，记 $\boldsymbol{w}(B) = \sum\limits_{e \in B}\boldsymbol{w}(e)$
• S 是 V 的子集，记 $\boldsymbol{w}^{+}(S) = \boldsymbol{w}(E_{D}^{+}(S))$, $\boldsymbol{w}^{-}(S) = \boldsymbol{w}(E_{D}^{-}(S))$

定义：$\boldsymbol{f} \in \mathscr{E}(D)$，若 $\forall v \in V, \boldsymbol{f}^{+}(v) = \boldsymbol{f}^{-}(v)$，称 $\boldsymbol{f}$ 为 D 的圈向量

定义：C 是 D 中的圈(不一定有向)，$C^{+}$ 表示 C 中与 C 的正向方向一致的边集；$C^{-}$ 表示 C 中与 C 的正向相反的边集。

定义：$\boldsymbol{f}_{C} \in \mathscr{E}(D)$ 如下：

$$\boldsymbol{f}_C(e) = \left\{ \begin{array}{**lr**} 1, \quad e \in C^{+} \\ -1, \quad e \in C^{-} \\ 0, \quad e \notin C^{+} \cup C^{-} \\ \end{array} \right.$$

$\boldsymbol{f}_{C}$ 是满足 D 的圈向量定义的，称为圈 C 的圈向量。D 的所有圈向量构成 $\mathscr{E}(D)$ 的子空间，称为 D 的圈空间，记为 $\mathscr{C}(D)$

定义：设 $\boldsymbol{p} \in \mathscr{V}(D)$ , $e=uv$，定义 $\boldsymbol{\delta}_{p} \in \mathscr{E}(D)$

$$\boldsymbol{\delta}_{p}(e) = \boldsymbol{p}(u) - \boldsymbol{p}(v), \forall e \in E$$

称 $\boldsymbol{\delta}_{p}$ 为 D 的割向量。

定义：设 $B = E_{D}[S, \overline{S}]$ 是 D 中的键，定义 $\boldsymbol{g}_{B} \in \mathscr{E}(D)$ 如下：

$$\boldsymbol{g}_{B}(e) = \left\{ \begin{array}{**lr**} 1, \quad a \in (S, \overline{S}) \\ -1, \quad a \in (\overline{S}, S) \\ 0, \quad a \notin B \\ \end{array} \right.$$

若

$$\boldsymbol{p}(u) = \left\{ \begin{array}{**lr**} 1, \quad u \in S \\ 0, \quad u \notin S \\ \end{array} \right.$$

则 $\boldsymbol{\delta}_{p} = \boldsymbol{g}_{B}$，于是 $\boldsymbol{g}_{B}$ 为键 B 的割向量。D 的所有割向量构成 $\mathscr{E}(D)$ 的子空间，称为割空间，记为 $\mathscr{B}(D)$

• 定理：M 是 D 的关联矩阵，则 $\mathscr{B}(D)$ 是 M 的行向量空间$\mathscr{M}$，$\mathscr{C}(D)$ 是 $\mathscr{M}$ 的正交补
• 推论：对任何图都有 $\mathscr{E}(D) = \mathscr{B}(D) \oplus \mathscr{C}(D)$

定义： $\boldsymbol{f} \in \mathscr{E}(D)$, $D_{\boldsymbol{f}}$ 表示 D 中使得 $\boldsymbol{f}$ 的值不为 0 的边集导出的子图。$D_{\boldsymbol{f}}$ 称为 $\boldsymbol{f}$ 的支撑图(支撑图是对应权函数的)。

引理：

• (1) 若 $\boldsymbol{f} \in \mathscr{E}(D)$ 且非零，则 $D_{\boldsymbol{f}}$ 含圈
• (2) 若 $\boldsymbol{g} \in \mathscr{B}(D)$ 且非零，则 $D_{\boldsymbol{g}}$ 含键

定义： $\boldsymbol{B}$ 是行由 $\mathscr{E}(D)$ 中的向量组成的矩阵

• $R \subseteq E(D)$，则 $\boldsymbol{B}|R$ 表示 $\boldsymbol{B}$ 中列限制在 R 上得到的子矩阵。
• R 是 D 的子图，记为 $\boldsymbol{B}|E(R)$，也可以记为 $\boldsymbol{B}|R$

定理：$\boldsymbol{B}, \boldsymbol{C}$ 分别是 $\mathscr{B}(D)$ 和 $\mathscr{C}(D)$ 的基矩阵，则对任意 $R \subseteq E(D)$ 有

• (1) $\boldsymbol{B}|R$ 列线性无关 $\Leftrightarrow D[R]$ 不含圈
• (1) $\boldsymbol{C}|R$ 列线性无关 $\Leftrightarrow D[R]$ 不含键

推论：$dim \mathscr{B} = |V| - \omega$, $dim \mathscr{C} = |E| - |V| + \omega$

定义：F 是 D 的支撑森林，对 D 的边标号：$e_{1}, e_{2}, …, e_{|E|}$，使得 $E(\overline{F}) = \{e_{1}, e_{2}, …, e_{|E| - |V| + \omega}\}$, $E(F) = \{e_{|E| - |V| + \omega + 1}, …, e_{|E|}\}$。

• 生成森林的基本圈，圈空间对应生成森林的基矩阵

对每个 $e_{i} \in E(\overline{F})$，$F+e_{i}$ 含唯一圈(第3节圈秩那块的定理)，记为 $C_{i}$，称为 D 中对应于 F 的基本圈。记 $\boldsymbol{f}_{i}$ 为对应于圈 $C_{i}$ 且使得 $\boldsymbol{f}_{C_{i}}(e_{i}) = 1$ 的圈向量，于是以

\begin{equation}
\boldsymbol{f}_{1}, \boldsymbol{f}_{2}, …, \boldsymbol{f}_{|E|-|V|+\omega} \tag{01}
\end{equation}

为行构成的 $(|E| - |V| + \omega) \times |E|$ 阶矩阵 $\boldsymbol{C}_{F}$ 有以下分块形式。

$$\boldsymbol{C}_{F} = (\boldsymbol{I}_{|E|-|V|+\omega}\boldsymbol{C}_{2})$$

其中 $\boldsymbol{I}_{|E|-|V|+\omega} = \boldsymbol{C}_{F}|\overline{F}$ 为 $|E|-|V|+\omega$ 阶单位阵；$\boldsymbol{C}_{2} = \boldsymbol{C}_{F}|F$ 为 $(|E|-|V|+\omega) \times (|V| - \omega)$ 阶矩阵，因为 $rank \boldsymbol{C}_{F} = |E|-|V|+\omega$，所以向量组 (01) 是圈空间 $\mathscr{E}(D)$ 的一组基，$\boldsymbol{C}_{F}$ 称为 $\mathscr{E}(D)$ 中对应于 F 的基矩阵。

• 生成森林的基本键，割空间对应生成森林的基矩阵

对 $e_{j} \in E(F)$，$\overline{F}+e_{j}$ 含唯一的键(第四小节边割集那块的定理)。记为 $B_{j}$，称为 D 中对应于 F 的基本键。$\boldsymbol{g}_{j}$ 表示对应于 $B_{j}$ 且使 $\boldsymbol{g}_{B_{i}}(a_{j}) = 1$ 的割向量，$j = |E| - |V| + \omega + 1, …, |E|$。于是以

$$\boldsymbol{g}_{|E| - |V| + \omega + 1}, \boldsymbol{g}_{|E| - |V| + \omega + 2}, ..., \boldsymbol{g}_{|E|} \tag{02}$$

为行构成的 $(|V| - \omega) \times |E|$ 阶矩阵 $\boldsymbol{B}_{F}$ 有以下分块形式

$$\boldsymbol{B}_{F} = (\boldsymbol{B}_{1}\boldsymbol{I}_{|v|-\omega})$$

其中 $\boldsymbol{B}_{1} = \boldsymbol{B}_{F}|\overline{F}$ 是 $(|v| - \omega) \times (|E|-|V|+\omega)$ 阶矩阵，$\boldsymbol{I}_{|v|-\omega} = \boldsymbol{B}_{F}|F$ 是 $|v| - \omega$ 阶矩阵。由于 $rank \boldsymbol{B}_{F} = |V| - \omega$，所以向量组 (02) 是割空间 $\mathscr{B}(D)$ 中的一组基，$\boldsymbol{B}_{F}$ 称为 $\mathscr{B}(D)$ 中对应于F的基矩阵。

---

$6 生成树的数目

无环连通图 D 中，生成树(支撑树)的数目记为 $\tau(D)$

无环连通图 D 中，$\boldsymbol{B}$ 是割空间 $\mathscr{B}(D)$ 的基矩阵，由第五小节圈空间和割空间的基矩阵那块的定理，若 $R \subseteq E(D)$ 且 $|R| = |V| - 1$，则子方阵 $\boldsymbol{B}|R$ 是可逆的 \Leftrightarrow D[R] 是 D 的生成树。于是 $\tau(D)$ 就等于 $\boldsymbol{B}$ 中阶为 $|v| - 1$ 的可逆方阵数目。

定义：矩阵 $M$ 为 $n \times m$ 阶矩阵，吐过 M 中所有的满阶($\min(n, m)$阶)子方阵的行列式值都去0, -1, 1，则称 $M$ 为幺模矩阵。如果所有子方阵都是幺模的，那么矩阵为全幺模矩阵。

定理：D 是无环连通有向图，$\boldsymbol{B}$ 和 $\boldsymbol{C}$ 分别是 $\mathscr{B}(D)$ 和 $\mathscr{C}(D)$ 中的幺模基矩阵。则

• $\tau(G) = det(\boldsymbol{B}\boldsymbol{B}^{T}) = det(\boldsymbol{C}\boldsymbol{C}^{T})$
• 推论 ：$\tau(G) = \pm det \begin{pmatrix} \boldsymbol{B} \\ \boldsymbol{C}\end{pmatrix}$

推论：D 是无环连通有向图，T 是 D 中的生成树，$\boldsymbol{B}_{T}$ 和 $\boldsymbol{C}_{T}$ 分别是 $\mathscr{B}(D)$ 和 $\mathscr{C}(D)$ 中对应于 T 的基矩阵，$\boldsymbol{K}$ 是从 D 的关联矩阵 M 中删去任意一行后所得矩阵，则

• $\tau(G) = det(\boldsymbol{B}_{T}\boldsymbol{B}_{T}^{T}) = det(\boldsymbol{C}_{T}\boldsymbol{C}_{T}^{T}) = det(\boldsymbol{K}\boldsymbol{K}^{T})$
• 推论：$T_{n}$ 是 n $(\ge 2)$ 阶竞赛图，$\tau(T_{n}) = n^{n-2}$
• 推论(矩阵-树定理)：G 是顶点集 $\{v_{1}, v_{2}, ..., v_{n}\}$ 的无环连通无向图，则 $\tau(G) = det(\boldsymbol{K}\boldsymbol{K}^{T})$，其中 $\boldsymbol{K}$ 是从 G 中任意一个定向图 D 的关联矩阵 $\boldsymbol{M}(D)$ 中删去任意一行后得到的矩阵
• 推论(Cayley公式)：$\tau(K_{n}) = 2^{n-2}, n \ge 2$

---

$7 最小生成树

定义：最小生成树是在加权简单图 $(G, \boldsymbol(w))$ 中找出权和最小的生成树，也叫最小连接问题

• Prim 算法
• Kruskal 算法

定义：Steiner树问题(组合优化问题)：求加权连通图中有一些必选点和一些可选点，求使得所有必选点连通的最小支撑树。

---

$8 最短路径

定义：加权简单无向图 $(G, \boldsymbol{w})$，其中 $\boldsymbol{w} \in \mathscr{E}(G)$, 边 $e=uv$ 上的值 $\boldsymbol{w}(e)$ 表示 (u, v) 的距离。找出 $(G, \boldsymbol{w})$ 中根在 $v_{0}$，且各个点到 $v_{0}$ 的距离和最小的生成树。

• Dijkstra (适用无负权有向/无向图)

例题：A, B, C 三只桶，容积分别 12 升, 9 升, 5 升。A 中有 12 升。能否将 A 中的水分成两半，如果可以，最少多少步。

---

$9 电网络方程

Kirchhoff 电流定律(KCL), Kirchhoff 电压定律(KVL)

---