几类图的推广的拉普拉斯矩阵的特征多项式

The Characteristic Polynomial of Generalized Laplace Matrix of Several Kinds of Graphs

摘要: 本文主要研究几类图的推广的拉普拉斯矩阵的特征多项式。用A(G)表示有n个顶点的简单图G的邻接矩阵，D(G)表示图G的顶点度对角矩阵。图G的拉普拉斯矩阵为，推广的拉普拉斯矩阵设为 。根据完全图和二部图的推广的拉普拉斯矩阵的特征多项式的结果，可以知道推广式中k分别取−1、0、1时，即是无符号拉普拉斯矩阵、邻接矩阵、拉普拉斯矩阵的相应的结果。

Abstract: In this paper, we mainly study the characteristic polynomial of the generalized Laplace matrix of several kinds of graphs. The adjacency matrix of a simple graph with n vertexes represented by A(G), D(G) represents the vertex degree diagonal matrix of graph G. The Laplace matrix of G is , the generalized Laplace matrix is set to . We can know the promotion of the k are taken −1, 0, 1. That is, the corresponding results of the unsigned Laplace matrix, adjacency matrix and the Laplace matrix.

1. 引言

本文讨论的图均为简单、有限的无向图。未定义的术语和符号参见 [1] 。设G是一个图。V(G)和E(G)分别表示图G的顶点集和边集，A(G)是图G的(0,1)邻接矩阵(这里，当顶点v_i和v_j相邻时， $a_{ij}=1$ ，当顶点v_i和v_j不相邻时， $a_{ij}=0$ 。) $L\left(G\right)=D\left(G\right)-A\left(G\right)$ 称为拉普拉斯矩阵(Laplace)， $Q\left(G\right)=D\left(G\right)+A\left(G\right)$ 称为无符号的拉普拉斯矩阵,其中D(G)为图G的顶点度对角矩阵，简记为D；A(G)为图的邻接矩阵，简记为A。多项式 $LG\left(\lambda \right)=\left|\lambda In-L\left(G\right)\right|$ 和分别为拉普拉斯矩阵的特征多项式和无符号拉普拉斯矩阵的特征多项式(其中I为单位方阵)。

谱的方法是研究图理论的重要方法 [1] 。图的相关矩阵(邻接矩阵、拉普拉斯矩阵、无符号拉普拉斯矩阵等)的研究是图论研究的一个活跃领域，人们通过研究图矩阵的特征值与特征向量 [2] [3] 解决图上的问题以及与图有关的实际问题。目前对邻接矩阵 [4] 、无符号拉普拉斯矩阵 [5] 和拉普拉斯矩阵 [6] [7] 及其谱 [8] [9] [10] 方面的研究结果已经有很多。

设 $L_k=kD-A$ ，易知 $L_k$ 是拉普拉斯矩阵的自然推广。本文给出了完全图和二部图的推广拉普拉斯矩阵的特征多项式和特征根。并且当 $L_k=kD-A$ 中的 $k$ 分别取−1、0、1时，很容易得出无符号拉普拉斯矩阵、邻接矩阵、拉普拉斯矩阵的相应的结果。

2. 推广的拉普拉斯矩阵的特征多项式

2.1. 完全图的推广的拉普拉斯矩阵的特征多项式

定理1：设G是具有n个顶点的完全图，则它的推广拉普拉斯矩阵L_k的特征多项式为 $L_k\left(\lambda \right)=\left[\lambda -\left(k-1\right)\left(n-1\right)\right]{\left[\lambda -k\left(n-1\right)-1\right]}^{n-1}$

证明：因为G是完全图，则图G的推广拉普拉斯矩阵的特征多项式为

$L_k\left(\lambda \right)=\left|\lambda I_n-L_k\right|=\left|\begin{array}{ccccc}\lambda -k\left(n-1\right)& 1& 1& \cdots & 1\\ 1& \lambda -k\left(n-1\right)& 0& \cdots & 0\\ 1& 0& \lambda -k\left(n-1\right)& \cdots & 0\\ ⋮& ⋮& ⋮& \ddots & ⋮\\ 1& 0& 0& \cdots & \lambda -k\left(n-1\right)\end{array}\right|$ (1)

计算 $L_k\left(\lambda \right)$ ，首先需把(1)式中第2至n行同时加到第1行，即可提出公因子 $\lambda -\left[\left(k-1\right)\left(n-1\right)\right]$ 得：

$L_k\left(\lambda \right)=\left[\lambda -\left(k-1\right)\left(n-1\right)\right]\left|\begin{array}{ccccc}1& 1& 1& \cdots & 1\\ 1& \lambda -k\left(n-1\right)& 0& \cdots & 0\\ 1& 0& \lambda -k\left(n-1\right)& \cdots & 0\\ ⋮& ⋮& ⋮& \ddots & ⋮\\ 1& 0& 0& \cdots & \lambda -k\left(n-1\right)\end{array}\right|$ (2)

将(2)式中的第一行乘以−1加到第2至n行，得：

$L_k\left(\lambda \right)=\left[\lambda -\left(k-1\right)\left(n-1\right)\right]\left|\begin{array}{ccccc}1& 1& 1& \cdots & 1\\ 0& \lambda -k\left(n-1\right)-1& 0& \cdots & 0\\ 0& 0& \lambda -k\left(n-1\right)-1& \cdots & 0\\ ⋮& ⋮& ⋮& \ddots & ⋮\\ 0& 0& 0& \cdots & \lambda -k\left(n-1\right)-1\end{array}\right|$ (3)

再将(3)式根据行列式的上三角计算公式可得：

$L_k\left(\lambda \right)=\left[\lambda -\left(k-1\right)\left(n-1\right)\right]{\left[\lambda -k\left(n-1\right)-1\right]}^{n-1}$

易得， $L_k\left(\lambda \right)$ 的特征根如下：

${\lambda }_1=\left(k-1\right)\left(n-1\right),{\lambda }_2={\lambda }_3=\cdots ={\lambda }_n=k\left(n-1\right)+1$

在完全图中 $L_k=kD-A$ ， $k$ 取值不同，会有以下性质：

(1) 当 $k=0$ 时， $L_0=-A$ ，其特征根与邻接矩阵的特征根互为相反数。

(2) 当 $k=1$ 时， $L_1=D-A$ ,此矩阵就是拉普拉斯(Laplace)矩阵。

(3) 当 $k=-1$ 时， $L_{-1}=-\left(D+A\right)$ ，其特征根与无符号的拉普拉斯矩阵互为相反数。

(4) 当 $k=2$ 时， $L_2=2D-A$ ，得到的是推广的拉普拉斯矩阵，其特征多项式与特征根分别如下：

$L_k\left(\lambda \right)=\left[\lambda -\left(n-1\right)\right]{\left[\lambda -\left(2n-1\right)\right]}^{n-1}$ ， ${\lambda }_1=n-1,{\lambda }_2={\lambda }_3=\cdots ={\lambda }_n=2n-1$

2.2. 二部图的推广的拉普拉斯矩阵的特征多项式

定理2：设 $G=\left(U\cup V,E\right)$ 是具有n个顶点的二部图，其中(U,V)是G的一个二分类， $\left|U\right|=n_1$ ， $\left|V\right|=n_2$ ，则其推广的拉普拉斯矩阵L_k的特征多项式为：

$L_k\left(\lambda \right)={\left(\lambda -k{n}_1\right)}^{n_2-1}{\left(\lambda -k{n}_2\right)}^{n_1-1}\left[{\lambda }^2-\left(k{n}_1+k{n}_2\right)\lambda +\left(k^2-1\right)n_1{n}_2\right]$

证明：因为G是二部图，则图G的推广拉普拉斯矩阵的特征多项式为：

$L_k\left(\lambda \right)=\left|\lambda I_n-L_k\right|=\left|\begin{array}{cccccc}\lambda -k{n}_2& \cdots & 0& 1& \cdots & 1\\ ⋮& \ddots & ⋮& ⋮& \ddots & ⋮\\ 0& \mathrm{...}& \lambda -k{n}_2& 1& \cdots & 1\\ 1& \cdots & 1& \lambda -k{n}_1& \cdots & 0\\ ⋮& \ddots & ⋮& ⋮& \ddots & ⋮\\ 1& \cdots & 1& 0& \cdots & \lambda -k{n}_1\end{array}\right|$ (4)

计算 $L_k\left(\lambda \right)$ ，首先需将(4)式根据行列式的特征将其分成四块，可得：

$L_k\left(\lambda \right)=\left|\begin{array}{cc}A& B\\ C& D\end{array}\right|$

那么子行列式A，B，C，D分别如下：

$A=\left|\begin{array}{ccc}\lambda -k{n}_2& \cdots & 0\\ ⋮& \ddots & ⋮\\ 0& \cdots & \lambda -k{n}_2\end{array}\right|$ ， $B=\left|\begin{array}{ccc}1& \cdots & 1\\ ⋮& \ddots & ⋮\\ 1& \cdots & 1\end{array}\right|$ ， $C=\left|\begin{array}{ccc}1& \cdots & 1\\ ⋮& \ddots & ⋮\\ 1& \cdots & 1\end{array}\right|$ ， $D=\left|\begin{array}{ccc}\lambda -k{n}_1& \cdots & 0\\ ⋮& \ddots & ⋮\\ 0& \cdots & \lambda -k{n}_1\end{array}\right|$

根据分块矩阵的行列式计算式 $L_k\left(\lambda \right)=\left|A\right|\cdot \left|D-C{A}^{-1}B\right|$ ，并且此时的行列式 $\left|A\right|$ 必须可逆，所以得：

$L_k\left(\lambda \right)={\left(\lambda -k{n}_2\right)}^{n_1}\left|\left[\begin{array}{ccc}\lambda -k{n}_1& \cdots & 0\\ ⋮& \ddots & ⋮\\ 0& \cdots & \lambda -k{n}_1\end{array}\right]-\left[\begin{array}{ccc}1& \cdots & 1\\ ⋮& \ddots & ⋮\\ 1& \cdots & 1\end{array}\right]\left[\begin{array}{ccc}\frac{1}{\lambda -k{n}_2}& \cdots & 0\\ ⋮& \ddots & ⋮\\ 0& \cdots & \frac{1}{\lambda -k{n}_2}\end{array}\right]\left[\begin{array}{ccc}1& \mathrm{...}& 1\\ \mathrm{...}& \mathrm{...}& \mathrm{...}\\ 1& \mathrm{...}& 1\end{array}\right]\right|$ (5)

(5) 式根据矩阵的运算(即相乘和相减)可得：

$L_k\left(\lambda \right)={\left(\lambda -k{n}_2\right)}^{n_1}\left|\begin{array}{cccc}\lambda -k{n}_1-\frac{n_1}{\lambda -k{n}_2}& \frac{-n_1}{\lambda -k{n}_2}& \cdots & \frac{-n_1}{\lambda -k{n}_2}\\ \frac{-n_1}{\lambda -k{n}_2}& \lambda -k{n}_1-\frac{n_1}{\lambda -k{n}_2}& \cdots & \frac{-n_1}{\lambda -k{n}_2}\\ ⋮& ⋮& \ddots & ⋮\\ \frac{-n_1}{\lambda -k{n}_2}& \frac{-n_1}{\lambda -k{n}_2}& \cdots & \lambda -k{n}_1-\frac{n_1}{\lambda -k{n}_2}\end{array}\right|$ (6)

根据(6)式可得它与一种特殊的行列式相同(对角线上的元素为a，其余的都为b)，根据其计算公式 $\left[a+\left(n-1\right)b\right]\left(a-b\right)n-1$ 可得最终的特征多项式为：

$L{}_k\left(\lambda \right)={\left(\lambda -k{n}_1\right)}^{n_2-1}{\left(\lambda -k{n}_2\right)}^{n_1-1}\left[{\lambda }^2-\left(k{n}_1+k{n}_2\right)\lambda +\left(k^2-1\right)n_1{n}_2\right]$

并且易得出其特征根如下：

${\lambda }_1=\frac{k\left(n_1+n_2\right)-\sqrt{k^2{\left(n_1-n_2\right)}^2+4n_1{n}_2}}{2}$ , ${\lambda }_2={\lambda }_3=\cdots ={\lambda }_{n_2}=k{n}_1$

${\lambda }_{n_2+1}=\cdots ={\lambda }_{n_1+n_2-1}=k{n}_2$ , ${\lambda }_n=\frac{k\left(n_1+n_2\right)+\sqrt{k^2{\left(n_1-n_2\right)}^2+4n_1{n}_2}}{2}$

在二部图中 $L_k=kD-A$ ， $k$ 取值不同，会有以下性质：

(1) 当 $k=0$ 时， $L_0=-A$ ，其特征根与邻接矩阵的特征根互为相反数。

(2) 当 $k=1$ 时， $L_1=D-A$ ,此矩阵就是拉普拉斯(Laplace)矩阵。

(3) 当 $k=-1$ 时，，其特征根与无符号的拉普拉斯矩阵互为相反数。

(4) 当 $k=2$ 时， $L_2=2D-A$ ，得到的是推广的拉普拉斯矩阵。

根据定理2及其二部图的特性可以得出以下两个推论

推论1：在二部图 $G=\left(U\cup V,E\right)$ 中， $\left|U\right|=n_1=1$ ， $\left|V\right|=n_2=n-1$ 时，此时的图为星图，其推广的拉普拉斯矩阵的特征多项式为： $L_k\left(\lambda \right)={\left(\lambda -k\right)}^{n-2}\left({\lambda }^2-kn\lambda +k^{2}n-k^2-n+1\right)$ 。

易得其特征根如下：

${\lambda }_1=\frac{kn}{2}-\sqrt{\frac{k^2{n}^2}{4}-k^{2}n+k^2+n-1}$ ， ${\lambda }_2={\lambda }_3=\cdots ={\lambda }_{n-1}=k$ ， ${\lambda }_n=\frac{kn}{2}+\sqrt{\frac{k^2{n}^2}{4}-k^{2}n+k^2+n-1}$

推论2：在二部图 $G=\left(U\cup V,E\right)$ 中， $\left|U\right|=n_1=n/2$ ， $\left|V\right|=n_2=n/2$ 时，此时是均匀分布的二部图，其推广的拉普拉斯矩阵矩阵的特征多项式为： $L_k\left(\lambda \right)=\frac{1}{4}\left[{\left(\lambda -\frac{kn}{2}\right)}^{n-2}\right]\left[4{\left(\lambda -\frac{kn}{2}\right)}^2-n^2\right]$ 。

易得其特征根如下：

${\lambda }_1=\frac{n}{2}-\frac{kn}{2}$ ， ${\lambda }_2={\lambda }_3=\cdots ={\lambda }_{n-1}=\frac{kn}{2}$ ， ${\lambda }_n=\frac{n}{2}+\frac{kn}{2}$

3. 总结

本文是在拉普拉斯矩阵 $L=D-A$ 的基础上将其自然推广成 $L_k=kD-A$ ，给出了完全图和二部图的推广的拉普拉斯矩阵的特征多项式及其特征根，并且由推广的拉普拉斯矩阵直接得出与邻接矩阵A、拉普拉斯矩阵L、无符号的拉普拉斯矩阵Q的特征多项式以及它们的特征根之间的关系。

本文定义的推广的拉普拉斯矩阵及其特征多项式的研究结果，可以作为今后研究网络的结构、网络的划分以及网络的连通度等方面的有力工具。

基金项目

国家自然科学基金项目(11661069)；国家自然科学基金项目(61663041)。