关于图类K_n^m±G的生成树数目

On the Number of Spanning Trees of Graphs K_n^m±G

摘要: 记K_n^m(n≥2,m≥1)是n个顶点的完全多重图，即任意两个顶点间有且仅有m条边相连。K_n^m+G (或K_n^m-G)为在K_n^m基础上再添加(或从中删除)子图的对应边得到的图。Nikolopoulos和Papadopoulos利用Kirchhoff矩阵–树定理给出了K_n^m+G生成树数目τ(K_n^m±G)=m(mn)^n-p-2det[mnI_p±L(G)]。本文利用线性代数技巧(一个有关矩阵和的行列式计算公式)，对该定理给出了一种新的简洁证法。并给出当G为完全图、圈、路、二部图时K_n^m±G生成数目的计算公式。

Abstract: Let K_n^m(n≥2,m≥1) be the complete multigraph n vertices, where any two different vertices, are connected by exactly m edges. K_n^m+G (or K_n^m-G) is defined as the resulting graph obtained from K_n^m by adding (or removing) all edges of a subgraph G in K_n^m . Based on Kirchhoff’s cele-brated matrix-tree theorem, Nikolopoulos and Papadopoulos, obtained the number of spanning trees of K_n^m±G as follows: τ(K_n^m±G)=m(mn)^n-p-2det[mnI_p±L(G)] . In this paper, by using some linear algebra techniques (a special formula on a determinant of two matrices), a new simple proof for above-mentioned counting formula was given. Furthermore, some new results on τ(K_n^m±G) were also shown when G is the complete graph, the cycle, the path and the complete bi-partite graph respectively.

1. 引言

图的生成树数目是图的一个同构不变量，它不仅是图论和组合学的重要研究对象，而且在计算机科学、统计物理、理论化学领域有一定的应用背景。例如，生成树数目是一个重要的度量网络稳定性的指标，人们一般认为生成树较多的网络更具有稳定性 [1]；另外生成树计数还与许多组合最优化问题有关 [2]。关于图的生成树数目的刻画，一个组合计数公式是Feussner组合公式 [3]： $\tau \left(G\right)=\tau \left(G-e\right)+\tau \left(G/e\right)$，图G的生成树数目等于图G删除一条边e后得到的子图 $G-e$ 的生成树数目加上图G收缩该边e得到的子图G/e的生成树数目；一个经典的代数方法Kirchhoff矩阵–树定理 [4]。它是通过求n阶图的 $n-1$ 阶代数余子式达到求图的生成树的数目，其优点是把图的生成树的计数问题转化成纯代数问题；此外，图G的生成树数目也等于图G的Tutte多项式在点(1, 1)处的特别值 [5]。

本文讨论的图均为无向连通图，且允许重边，但忽略自环。给定图 $G=\left(V\left(G\right),V\left(E\right)\right)$， $V\left(G\right)$ (简记V)为G的顶点集， $E\left(G\right)$ (简记E)为G的边集。若G的子图T是一个包含V中所有顶点的连通无圈子图，则称T为图G的一棵生成树。图 $G=\left(V,E\right)$ 的两棵生成树 $T_1,T_2$ 是不同的，当且仅当 $T_1,T_2$ 不同构或 $T_{\text{1}}\cong T_{\text{2}}$ (同构)，但他们顶点标号不同。用 $\tau (G)$ 表示图G生成树数目； $G\cup H$ 表示图G和图H的并图； $G\vee H$ 表示图G和图H的联图，即在并图 $G\cup H$ 的基础上将G的每一个顶点与H的每一个顶点相连所得到的图。记 $K_n$ 、 $C_n$ 、 $P_n$ 分别表示n个顶点的完全图、圈、路； $s{K}_{\text{2}}$ 表示s条平行边(不交边)； $K_{p,q}$ 表示顶点集 $V\left(K_{p,q}\right)$ 划分为 $V_1\left(\left|V_1\right|=p\right)$ 和 $V_{\text{2}}\left(\left|V_{\text{2}}\right|=q\right)$ 的完全二部图； $K_n^m\left(n\ge 2,m\ge 1\right)$ 表示n个顶点的完全多重图，即任意两个顶点间有且仅有m条边相连。设 $G=\left(V,E\right)$ 是p个顶点的重图，且 $V\subseteq V\left(K_n^m\right)$， $E\subseteq E\left(K_n^m\right)$， $K_n^m+G$ (或 $K_n^m-G$ )定义为 $K_n^m$ 基础上再添加(或从中删除) $K_n^m$ 的子图G的对应边得到的图。特别地，当 $m=1$ 时， $K_n^m\pm G=K_n\pm G$，这里，G为 $K_n$ 的某个子图， $K_n+G$ 表示再 $K_n$ 的基础上添加子图G中所有的边所得到的重图。 $K_n-G$ 表示从 $K_n$ 中去除子图G中的所有边所形成的图，称其为G在 $K_n$ 下的补图。当 $\left|V\right|=n$ 时， $K_n-G\cong \bar{G}$ (G的补图)。当 $G=K_n$ 、 $C_n$ 、 $P_n$ 时， $K_n-G$ 的生成树数目 $\tau \left(K_n-G\right)$ 已被研究。设G是p个顶点的重图，且 $V\left(G\right)\subseteq V\left(K_n^m\right)$， $E\left(G\right)\subseteq E\left(K_n^m\right)$，文献 [6] 中利用到Kirchhoff矩阵–树定理，通过复杂的行列式行(列)运算性质分析，给出了 $K_n^m\pm G$ 生成树数的计算公式 $\tau \left(K_n^m\pm G\right)=m{\left(mn\right)}^{n-p-2}\det \left[mn{I}_P\pm L\left(G\right)\right]$。本文基于矩阵–树定理，将利用一种加项行列式技巧(也就是，如果n阶行列式 $D=\left|a_{ij}\right|$， $D\left(x\right)=\left|a_{ij}+x\right|$ 是D的每一个元素加上x后获得的n阶新行列式(加项行列式)，那么 $D\left(x\right)=D+x{\displaystyle \underset{i=1}{\overset{n}{\sum }}{\displaystyle \underset{j=1}{\overset{n}{\sum }}{A}_{ij}}}$，这里 $A_{ij}$ 是 $a_{ij}$ 在D中的代数余子式 [7])给出上式的一个新证明，我们的证明清晰简单，其方法或许可用于计算一些其他特别图类的生成树数目问题。同时，当G取特殊图时，给出 $K_n^m\pm G$ 生成树数目的一些新结果。

2. 相关定理与引理

记 $G=\left(V,E\right)$，且 $V=\{v_1,v_2,\cdots ,v_n\}$， $E=\{e_1,e_2,\cdots ,e_m\}$。对 $\forall v_i,v_j\in V$，若 $v_i,v_j$ 相邻，则记为 $v_i~v_j$。 $N_G\left(v_i\right)=\{v_j\in V|v_i~v_j\}$， $d_i=d_G\left(v_i\right)=\left|N_G\left(v_i\right)\right|$。图的拉普拉斯矩阵定义如下，

$L\left(G\right)=\{\begin{array}{l}{d}_i\begin{array}{cc}& \end{array}i=j,\\ -1\begin{array}{cc}& \end{array}i\ne j,且v_i~v_j,\\ 0\begin{array}{cc}& \end{array}其他.\end{array}$ (1)

Kirchhoff矩阵树–定理表明 $L\left(G\right)$ 中任意元素的代数余子式就是图G的生成树数目，即 $\tau \left(G\right)={\left(-1\right)}^{i+j}\det \left(L_{i,j}\left(G\right)\right)$ 其中 $L_{i,j}\left(G\right)$ 表示从 $L\left(G\right)$ 中删除第i行和第j列后得到的余子矩阵。由此，容易得到生成树数目的另一表达式 $\tau \left(G\right)=\left(u_1\left(G\right)\cdots u_n\left(G\right)\right)/n$，其中 $u_1\left(G\right)\ge u_{\text{2}}\left(G\right)\ge \cdots \ge u_{n-\text{1}}\left(G\right)\ge u_n\left(G\right)=0$ 为 $L\left(G\right)$ 的特征值，即G的拉普拉斯特征值。

注意到图的拉普拉斯矩阵的任意元素的代数余子式相等且等于图的生成树数目，简单运用引言提及的加项行列式技巧立即可得到 $\det \left[L\left(G\right)+a{J}_n\right]=a{n}^2\tau \left(G\right)$，一个更一般性的结果见如下引理。

引理2.1. ( [8]) 设 $G=\left(V,E\right)$， $u=\left(u_i\right)$， $v=\left(v_i\right)$ 是 $R^{\left|V\right|}$ 中的列向量，其中 $i\in V$，则有

$\det \left(L\left(G\right)+u{v}^{\text{T}}\right)=\left({\displaystyle \underset{i\in V}{\sum }{u}_i}\right)\left({\displaystyle \underset{i\in V}{\sum }{v}_i}\right)\tau \left(G\right)$ (2)

引理2.2. ( [9]) 设G是一个有n个顶点的图， $\bar{G}$ 是G的补图。如果G的拉普拉斯矩阵的特征值为 ${\mu }_1\left(G\right),{\mu }_2\left(G\right),\cdots ,{\mu }_{n-1}\left(G\right),0$，那么 $\bar{G}$ 对应的特征值为 $n-{\mu }_1\left(G\right),n-{\mu }_2\left(G\right),\cdots ,n-{\mu }_{n-1}\left(G\right),0$，即 $K_n-G$ 的特征值； $K_n+G$ 的特征值为 $n+{\mu }_1\left(G\right),n+{\mu }_2\left(G\right),\cdots ,n+{\mu }_{n-1}\left(G\right),0$。

引理2.3. ( [10])

1) $L\left(K_n\right)$ 的特征值为n和0，且重数分别为 $n-1$ 和1；

2) $L\left(C_n\right)$ 的特征值为 $2-2\cos \frac{2i\pi }{n},i=1,\cdots ,n$ ；

3) $L\left(P_n\right)$ 的特征值为 $2-2\cos \frac{i\pi }{n},i=1,\cdots ,n$ ；

4) 当 $K_{p,q}$ 的 $p=q$ 时，其为正则图，故 $L\left(K_{p,q}\right)=D-A=pI-A$，所以特征值为 $\text{0},2p,p$，并且p的重数为 $p+q-2$ ；

5) 如果 $G=K_n-s{K}_2\left(n\ge 2s>0\right)$，那么 $L\left(G\right)$ 的特征值为 $n-2,n,0$，并且重数分别为 $s,n-s-1$ 和1。

下面引理容易从基本的线性代数方法推导得到，证明从略。

引理2.4. 设G是一个有n个顶点的图，则有

$\det \left(L\left(G\right)+s{I}_n+t{J}_n\right)=\left(s+nt\right){\displaystyle \underset{i=1}{\overset{n-1}{\prod }}\left[{\mu }_i\left(G\right)+s\right]}$ (3)

其中 $I_n$ 表示 $n\times n$ 单位矩阵， $J_n$ 表示 $n\times n$ 全一矩阵。

3. 一个新证明

在文献 [6]，作者Nikolopoulos和Papadopoulos利用到Kirchhoff矩阵–树定理和复杂的行列式行(列)运算，证明了如下定理。

定理3.1 $K_n^m$ 为m完全重图，G为任意图，且 $V\left(G\right)\subseteq V\left(K_n^m\right),E\left(G\right)\subseteq E\left(K_n^m\right)$，则有

$\tau \left(K_n^m\pm G\right)=m{\left(mn\right)}^{n-p-1}{\displaystyle \underset{i=1}{\overset{p-1}{\prod }}\left[mn\pm {\mu }_i\left(G\right)\right]}$ (4)

定理3.1的新证明：只证明 $K_n^m+G$ 的情况即可( $K_n^m-G$ 的情况证明类似)，由引理2.1可知，取 $u,v$ 为 $n\times 1$ 列向量时，有如下等式成立：

$\det \left[L\left(K_n^m+G\right)+u{v}^{\text{T}}\right]=\left({\displaystyle \underset{i\in V}{\sum }{u}_i}\right)\left({\displaystyle \underset{i\in V}{\sum }{v}_i}\right)\tau \left(K_n^m+G\right)$ (5)

进一步，令 $u$ 中元素全为m， $v$ 中元素全为1时，则上式简化为

$\det \left[L\left(K_n^m+G\right)+m{J}_n\right]=m{n}^2\tau \left(K_n^m+G\right)$ (6)

若对 $L\left(K_n^m+G\right)+m{J}_n$ 适当分块，则

$L\left(K_n^m+G\right)+m{J}_n=\left[\begin{array}{cc}& \\ L\left(K_p^m+G\right)+m\left(n-p\right)I_p+m{J}_p& O_{p\times \left(n-p\right)}\\ & \\ & \\ O_{\left(n-p\right)\times p}& L\left(K_{n-p}^m\right)+mp{I}_{n-p}+m{J}_{n-p}\\ & \end{array}\right]$

其中， $O_{p\times \left(n-p\right)}$ 表示 $p\times \left(n-p\right)$ 的零矩阵，从而，

$\det \left[L\left(K_n^m+G\right)+m{J}_n\right]=\det \left[L\left(K_p^m+G\right)+m\left(n-p\right)I_p+m{J}_p\right]\cdot \det \left[L\left(K_{n-p}^m\right)+mp{I}_{n-p}+m{J}_{n-p}\right]$ (7)

注意到 ${\mu }_i\left(K_p^m+G\right)=mp+{\mu }_i\left(G\right)$， ${\mu }_i\left(K_{n-p}^m+G\right)+mp=mn$ 由引理2.2及引理2.4可知， $\begin{array}{l}\det \left[L\left(K_p^m+G\right)+m\left(n-p\right)I_p+m{J}_p\right]\cdot \det \left[L\left(K_{n-p}^m\right)+mp{I}_{n-p}+m{J}_{n-p}\right]\\ =\left[m\left(n-p\right)+mp\right]{\displaystyle \underset{i=1}{\overset{p-1}{\prod }}\left[{\mu }_i\left(K_p^m+G\right)+m\left(n-p\right)\right]}\cdot \left[mp+m\left(n-p\right)\right]{\displaystyle \underset{i=1}{\overset{n-p-1}{\prod }}\left[{\mu }_i\left(K_{n-p}^m\right)+mp\right]}\\ =mn{\displaystyle \underset{i=1}{\overset{p-1}{\prod }}\left[{\mu }_i\left(K_p^m+G\right)+mn-mp\right]}\cdot mn{\displaystyle \underset{i=1}{\overset{n-p-1}{\prod }}\left[{\mu }_i\left(K_{n-p}^m\right)+mp\right]}\\ ={\left(mn\right)}^2{\displaystyle \underset{i=1}{\overset{p-1}{\prod }}\left[{\mu }_i\left(K_p^m+G\right)+mn-mp\right]}\cdot {\displaystyle \underset{i=1}{\overset{n-p-1}{\prod }}\left[{\mu }_i\left(K_{n-p}^m\right)+mp\right]}\\ ={\left(mn\right)}^{n-p+1}{\displaystyle \underset{i=1}{\overset{p-1}{\prod }}\left[mn+{\mu }_i\left(G\right)\right]}\end{array}$

从而， $m{n}^2\tau \left(K_n^m+G\right)={\left(mn\right)}^{n-p+1}{\displaystyle \underset{i=1}{\overset{p-1}{\prod }}\left[mn+{\mu }_i\left(G\right)\right]}$，即 $\tau \left(K_n^m+G\right)=m{\left(mn\right)}^{n-p-1}{\displaystyle \underset{i=1}{\overset{p-1}{\prod }}\left[mn+{\mu }_i\left(G\right)\right]}$。同理可得 $\tau \left(K_n^m-G\right)=m{\left(mn\right)}^{n-p-1}{\displaystyle \underset{i=1}{\overset{p-1}{\prod }}\left[mn-{\mu }_i\left(G\right)\right]}$。

因此

$\tau \left(K_n^m\pm G\right)=m{\left(mn\right)}^{n-p-1}{\displaystyle \underset{i=1}{\overset{p-1}{\prod }}\left[mn\pm {\mu }_i\left(G\right)\right]}$ (8)

特别地，当 $m=1$ 时，有

$\tau \left(K_n\pm G\right)=n^{n-p-1}{\displaystyle \underset{i=1}{\overset{p-1}{\prod }}\left[n\pm {\mu }_i\left(G\right)\right]}$ (9)

推论1. 当 $G=K_p\left(p\le n\right)$ 时， $\tau \left(K_n^m\pm K_p\right)=m{\left(mn\right)}^{n-p-1}{\left(mn\pm p\right)}^{p-1}$。

推论2. 当 $G=C_p\left(p\le n\right)$ 时， $\tau \left(K_n^m\pm C_p\right)=m{\left(mn\right)}^{n-p-1}{\displaystyle \underset{i=1}{\overset{p-1}{\prod }}\left[mn\pm \left(2-2\cos \frac{2i\pi }{p}\right)\right]}$。

推论3. 当 $G=P_p\left(p\le n\right)$ 时， $\tau \left(K_n^m\pm P_p\right)=m{\left(mn\right)}^{n-p-1}{\displaystyle \underset{i=1}{\overset{p-1}{\prod }}\left[mn\pm \left(2-2\cos \frac{i\pi }{p}\right)\right]}$。

推论4. 当 $G=K_{\frac{p}{2},\frac{p}{2}}\left(p\le n\right)$ 时， $\tau \left(K_n^m\pm K_{\frac{p}{2},\frac{p}{2}}\right)=m{\left(mn\right)}^{n-p-1}{\left(mn\pm \frac{p}{2}\right)}^{p-2}\left(mn\pm p\right)$。

推论5. 当 $G=K_p-q{K}_2\left(p\ge 2q\right)$ 时， $\tau \left(K_n^m\pm G\right)=m{\left(mn\right)}^{n-p-1}{\left[mn\pm \left(p-2\right)\right]}^q{\left(mn\pm p\right)}^{p-q-1}$。

4. 总结

本文主要研究了组合图 $K_n^m\pm G$ 的生成树计数问题。我们的计算方法离不开一个基本原理：矩阵–树定理，这个定理一般将生成树的计算问题转换为一个行列式计算问题，而高阶行列式计算常常是困难问题。对这类图 $K_n^m\pm G$ 的生成树计数，本文运用了线性代数理论中的一种加项行列式计算技巧 $D\left(x\right)=D+x{\displaystyle \underset{i=1}{\overset{n}{\sum }}{\displaystyle \underset{j=1}{\overset{n}{\sum }}{A}_{ij}}}$，(这里 $D\left(x\right)=\left|a_{ij}+x\right|$，是n阶行列式 $D=\left|a_{ij}\right|$ 的每一个元素加上x后获得的行列式(加项行列式)， $A_{ij}$ 是 $a_{ij}$ 在D中的代数余子式)，给出了文献 [6] 主要定理的一个新证明，本文的证明方法或许具备可推广性。此外，给出了当G为完全图、圈、路、二部图时， $K_n^m\pm G$ 生成树数目的一些具体结果。

致谢

感谢指导老师对课题的指导，本论文发表受省一流线下课程《高等代数》建设、省自然科学基金(Y21A010028)资助。