矩阵树定理及其证明

往上貌似证明的资料比较少而且不全,于是就来 水一篇博客

定义

  1. 对于无向图,定义 \(D(G)\) 为图 \(G\) 的度数矩阵,其中:

\[D(G)(i, j) = \begin{cases} \deg_i & (i = j) \\ 0 & (i \ne j) \end{cases} \]

  1. 对于有向图,定义 \(D ^ {in}(G)\) 为图 \(G\) 的入度矩阵,\(D ^ {out}(G)\) 为图 \(G\) 的出度矩阵,其中:

\[D(G) ^ {in}(i, j) = \begin{cases} \mathrm{in}_i & (i = j) \\ 0 & (i \ne j) \end{cases}, D(G) ^ {out}(i, j) = \begin{cases} \mathrm{out}_i & (i = j) \\ 0 & (i \ne j) \end{cases} \]

  1. 定义 \(A(G)\) 为图 \(G\) 的邻接矩阵,其中:

\[A(G)(i, j) = the ~ number ~ of ~ the ~ path ~ from ~ i ~ to ~ j \]

  1. 定义图 \(G\) 的 \(\rm kirchhoff\) 矩阵 \(K(G) = D(G) - A(G)\)。

  2. 定义无向图 \(G\) 的生成树数量为 \(t(G)\),有向图根向树生成树(根为 \(u\),下同)数量为 \(t ^ {root}(G, u)\),有向图叶向树数量为 \(t ^ {leaf}(G, u)\)。

  3. 定义图 \(G\) 的关联矩阵 \(M(G)\) 为一个大小为 \(n \times m\) 的矩阵,其中(一下的方向对于无向图随意):

\[M(G)(i, j) = \begin{cases} -1 & (i ~ is ~ the ~ end ~ of ~ the ~ edge_j) \\ 1 & (i ~ is ~ the ~ start ~ of ~ the ~ edge_j) \\ 0 & (Otherwise) \\ \end{cases} \]

  1. 定义图 \(G\) 的减关联矩阵 \(M_0(G)\) 为关联矩阵 \(M(G)\) 去掉最后一行后的大小为 \((n - 1) \times m\) 的矩阵。

  2. 定义图 \(G\) 的子减关联矩阵 \(M_0(G)[S]\) 为选出 \(M_0(G)\) 中的列构成子集 \(S\),满足 \(|S| = n - 1, S \subseteq {1, 2, \cdots m}\)。

定理

以下默认所有数均为正整数。

  1. 无向图矩阵树定理:

\[\forall i \in [1, n], t(G) = \det K(G) \begin{pmatrix}1, 2, \cdots i - 1, i + 1, \cdots n \\ 1, 2, \cdots i - 1, i + 1, \cdots n\end{pmatrix} \]

  1. 有向图矩阵树定理:

\[\forall i \in [1, n], t ^ {root}(G, i) = \det K ^ {out}(G) \begin{pmatrix}1, 2, \cdots i - 1, i + 1, \cdots n \\ 1, 2, \cdots i - 1, i + 1, \cdots n\end{pmatrix} \]

\[\forall i \in [1, n], t ^ {leaf}(G, i) = \det K ^ {in}(G) \begin{pmatrix}1, 2, \cdots i - 1, i + 1, \cdots n \\ 1, 2, \cdots i - 1, i + 1, \cdots n\end{pmatrix} \]

  1. \(\rm Best\) 定理:设有向欧拉图 \(G\) 的欧拉回路数量为 \(ec(G)\),则有:

\[\forall i \in [1, n], ec(G) = t ^ {root}(G, i) \prod\limits_{u \in V} (\deg_u - 1)! \]

其中对于欧拉图 \(\mathrm{in}, \mathrm{out}\) 均相同,因此 \(\deg\) 可任选其一。

若要求欧拉回路起点 \(k\),则以 \(k\) 为起点的欧拉回路数量 \(ec(G, k)\) 为:

\[ec(G, k) = t ^ {root}(G, k) \deg_k \prod\limits_{u \in V} (\deg_u - 1)! \]

此定理下面暂不证明,先咕着

证明

以下只证明无向图无根树生成树矩阵树定理。

  1. 引理 \(1\):

\[M \times M ^ {T} = K \]

\[\begin{aligned} M \times M ^ {T}(i, j) &= \sum\limits_{k = 1} ^ m M(i, k) \times M ^ {T}(k, j) \\ &= \sum\limits_{k = 1} ^ m M(i, k) \times M(j, k) \\ \end{aligned} \]

可以发现当且仅当 \(i, j\) 都为边 \(k\) 的一个端点时,贡献不为 \(0\)。

若 \(i = j\) 则 \(M(i, k) = M(j, k)\) 贡献相等,那么两者乘积贡献 \(1\)。因此总贡献为 \(\deg_i\)。

若 \(i \ne j\) 则 \(M(i, k) \ne M(j, k)\) 贡献相反,那么两者乘积贡献 \(-1\)。因此总贡献为 \(-A(i, j)\)。

于是有引理 \(1\) 成立。

  1. 引理 \(2\):

若 \(S\) 构成的边集在原图上构成生成树,那么 \(\det M_0[S] = 1 / -1\) 否则 \(\det M_0[S] = 0\)。

先证后者:

若原图没有构成树,那么至少存在一个简单环 \(C(e_{i_1}, e_{i_2}, \cdots e_{i_k})\),记 \(e_{{i_j}_u}, e_{{i_j}_v}\) 分别为边 \(e_{i_j}\) 的两个端点。

同时,对于 \(M_0[S]\) 有如下两点观察:

  • 对于同一行,恰好存在两列非 \(0\)。

  • 对于同一列,恰好存在两行一行为 \(1\) 一行为 \(-1\)。(若为最后一行也可视作出现)

下面证明 \(M_0[S]\) 对应原 \(M_0\) 的 \(i_1, i_2, \cdots i_k\) 列线性相关,考虑依次合并所有列:

我们首先拿第 \(i_1\) 列消 \(i_2\) 列,因为简单环上两边共点,因此至少存在一行使得两列上均非 \(0\),我们消掉这一行后根据观察 \(2\) 必恰好仅有 \(e_{{i_1}_u}, e_{{i_2}_v}\) 这两行一行为 \(1\) 一行为 \(-1\)。

假设合并到第 \(i_j\) 列,若 \(j \ne k\) 那么使用 \(i_{j - 1}\) 列合并的结果同第一列消第二列的方式消掉第 \(i_j\) 列,于是第 \(i_j\) 列消完后必恰好在 \(e_{{i_1}_u}, e_{{i_j}_v}\) 这两行一行为 \(1\) 一行为 \(-1\)。

最后合并到第 \(i_{k - 1}\) 列时,此时非 \(0\) 两行与原 \(i_k\) 列未消时一致,故此时可以将第 \(i_k\) 列消为全 \(0\)。

因此这 \(i_1, i_2, \cdots i_k\) 列线性相关,\(\det M_0[S] = 0\)。


再证前者:

考虑将原行列式消成好算的形式,类似于高斯消元的方式,我们钦定一行的主元拿此行去消所有行。

具体地,若 \(S\) 构成的边集为一棵树,那么必定能找到叶子节点 \(u\),此时选出 \(u\) 所在的行,必定恰好只存在一列非 \(0\),拿此列去消所有行(事实上只能消掉边的另一个节点所对应的行)。

可以发现这等价于每次在 \(M_0[S]\) 中删去树上叶子节点所对应的一条边,故此过程一定可以不断递归直至消去所有边。

最后我们发现,每一行都只剩下恰好一列为其做为叶子时所对应列为 \(1 / -1\),故此时行列式值仅在每行选这些列时非 \(0\),不论逆序对数量,所得行列式值均为 \(1 / -1\)。

  1. 引理 \(3\)(\(\rm Binet - Cauchy\) 定理):

定义大小分别为 \(n \times m, m \times n(n \le m)\) 的矩阵 \(A, B\) 则有:

\[\det(AB) = \sum\limits_{S \subseteq \{1, 2, \cdots m\}, |S| = n} \det(A[S]) \times \det(B[S]) \]

其中 \(A[S], B[S]\) 分别表示 \(A\) 取 \(S\) 集合内的列,\(B\) 取 \(S\) 集合内的行所构成的矩阵。

证明引理 \(3\) 之前再给出两条引理:

定义 \(\lambda(P)\) 为排列 \(P\) 的逆序对数量。

    1. 引理 \(1\):
  • 定义 \(P'\) 为 \(P\) 的逆排列,即满足 \(P'_{P_i} = i\),那么有:

\[\lambda(P) = \lambda(P') \]

\(\quad\) 不妨转化 \(P'\) 的逆序对求法,不难发现等价于给定序列 \(A\),每个元素存在两个关键字 \(x, y\),其中 \(A_{i_x} = p_i, A_{i_y} = i\)。

\(\quad\) 那么 \(\lambda(P')\) 等价于将将序列 \(A\) 按照第一关键字排序后以第二关键字为权值的逆序对数量。

\(\quad\) 在这里等价于按照权值排序后求下标的逆序对,这与直接求原排列的逆序对是等价的。

    1. 引理 \(2\):
  • 定义 \(P_{Q}\) 为排列 \(Q\) 与排列 \(P\) 的复合,则 \(\lambda(P_{Q})\) 与 \(\lambda(P) + \lambda(Q)\) 的奇偶性相同。

\(\quad\) 仿照引理 \(1\) 的证明方法,那么左式等价去求给定序列 \(A\),每个元素存在两个关键字 \(x, y\) 其中 \(A_{i_x} = P_i, A_{i_y} = Q'_i\),

\(\quad\) 那么 \(\lambda(P_Q)\) 等价于按照第一关键字排序后以第二关键字为权值的逆序对数量。

\(\quad\) 考虑调整证明,可知一开始的逆序对数量为 \(\lambda(Q') = \lambda(Q)\),排序利用冒泡排序的过程,可知有效的交换仅有 \(P\) 的逆序对个。

\(\quad\) 而我们知道每交换排列里两个元素排列逆序对数奇偶性改变,故总共改变 \(\lambda(P)\) 次,所以 \(\lambda(P_Q)\) 与 \(\lambda(P) + \lambda(Q)\) 奇偶性相同。


首先我们展开等式右侧:

\[\begin{aligned} & \sum\limits_{S \subseteq \{1, 2, \cdots m\}, |S| = n} \det(A[S]) \times \det(B[S]) \\ &= \sum\limits_{S \subseteq \{1, 2, \cdots m\}, |S| = n} \left(\sum\limits_{P} (-1) ^ {\lambda(P)} \prod\limits_{i = 1} ^ n A_{i, S_{P_i}}\right) \times \left(\sum\limits_{Q} (-1) ^ {\lambda(Q)} \prod\limits_{i = 1} ^ n B_{S_i, Q_i}\right) \\ &= \sum\limits_{S} \sum\limits_{P} \sum\limits_{Q} (-1) ^ {\lambda(P) + \lambda(Q)} \prod\limits_{i = 1} ^ n A_{i, S_{P_i}} \times B_{S_i, Q_i} \\ \end{aligned} \]

再展开等式左侧:

\[\begin{aligned} & \det(AB) \\ &= \sum\limits_{P} (-1) ^ {\lambda(P)} \prod\limits_{i = 1} ^ n \left(\sum\limits_{j = 1} ^ m A_{i, j} \times B_{j, P_i}\right) \\ &= \sum\limits_{P} (-1) ^ {\lambda(P)} \sum\limits_{R} \left(\prod\limits_{i = 1} ^ n A_{i, R_i} \times B_{R_i, P_i}\right) (|R| = n, \forall i, R_i \in \{1, 2, \cdots m\}) \\ &= \sum\limits_{R} \sum\limits_{P} (-1) ^ {\lambda(P)} \left(\prod\limits_{i = 1} ^ n A_{i, R_i}\right) \times \left(\prod\limits_{i = 1} ^ n B_{R_i, P_i}\right) \end{aligned} \]

仔细观察可知,对于可重排列 \(R\),若 \(\exist i < j, R_i = R_j\) 那么交换 \(P_i, P_j\) 后后面的积式不变,但逆序对奇偶性改变,因此两者贡献互为相反数可抵消。

因此我们只需钦定每个 \(\exist i < j, R_i = R_j\) 的可重排列 \(R\),让其和交换满足条件的最小 \(P_i, P_j\) 交换后的排列 \(P\) 的贡献相抵即可。

因为交换最小的 \(i, j\) 后依然满足 \(i, j\) 为最小的满足条件的点对,因此可以两两唯一配对。

故我们只需枚举不重的序列即可,为此我们首先枚举 \(\{1, 2, \cdots m\}\) 的子集,然后枚举一个长度为 \(n\) 的排列 \(Q\):

\[\begin{aligned} & \det(AB) \\ &= \sum\limits_{S} \sum\limits_{Q} \sum\limits_{P} (-1) ^ {\lambda(P)} \prod\limits_{i = 1} ^ n A_{i, S_{Q_i}} \times B_{S_{Q_i}, P_i} \\ &= \sum\limits_{S} \sum\limits_{Q} \sum\limits_{P_{Q'}} (-1) ^ {\lambda(P_{Q'})} \left(\prod\limits_{i = 1} ^ n A_{i, S_{Q_i}}\right) \times \left(\prod\limits_{i = 1} ^ n B_{S_i, P_{Q'_i}}\right) \\ &= \sum\limits_{S} \sum\limits_{Q} \sum\limits_{P_{Q'}} (-1) ^ {\lambda(P) + \lambda(Q)} \left(\prod\limits_{i = 1} ^ n A_{i, S_{Q_i}}\right) \times \left(\prod\limits_{i = 1} ^ n B_{S_i, P_{Q'_i}}\right) \end{aligned} \]

整理即可得到从右侧推导得到的式子。

下面我们只证明矩阵树定理删去最后一行最后一列是正确的(对于删去其余的情况,只需将 \(M_0\) 的定义修改成删去改行即可)。

类似于引理 \(1\),我们知道 \(K_0 = M_0 \times M_0 ^ T\) 其中 \(K_0\) 为 \(K\) 去掉最后一行和最后一列得到的方阵。

再根据引理 \(3\),可知:

\[\begin{aligned} \det K_0 &= \sum\limits_S \det(M_0[S]) \det(M_0 ^ T[S]) \\ &= \sum\limits_S \det{^ 2}(M_0[S]) \end{aligned} \]

由定理 \(2\),若边集 \(S\) 不构成生成树,则 \(\det(M_0[S]) = 0\),在该式中贡献为 \(0\)。

若边集 \(S\) 构成生成树,则 \(\det(M_0[S]) = 1 / -1\),在该式中贡献为 \(1\)。

故可得到 \(\det K_0\) 即为原图的生成树数量。

上一篇:yolov5 测试


下一篇:矩阵树定理(Matrix-tree Theorem)