Advances in Applied Mathematics
Vol.06 No.06(2017), Article ID:22151,5 pages
10.12677/AAM.2017.66092

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

Jing Liang1, Haixing Zhao1, Ke Zhang1, Yuanchao Liu2

1College of Computer, Qinghai Normal University, Xining Qinghai

2College of Mathematics and Statistics, Qinghai Normal University, Xining Qinghai

Received: Sep. 3rd, 2017; accepted: Sep. 19th, 2017; published: Sep. 26th, 2017

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 L ( G ) = D ( G ) A ( G ) , the generalized Laplace matrix is set to L k ( G ) = k D ( G ) A ( G ) . 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.

Keywords:Laplace Matrix, Generalized Laplace Matrix, Characteristic Polynomial, Eigenvalue

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

梁静1,赵海兴1,张科1,刘远超2

1青海师范大学计算机学院,青海 西宁

2青海师范大学数学与统计学院,青海 西宁

收稿日期:2017年9月3日;录用日期:2017年9月19日;发布日期:2017年9月26日

摘 要

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

关键词 :拉普拉斯矩阵,推广的拉普拉斯矩阵,特征多项式,特征根

Copyright © 2017 by authors and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY).

http://creativecommons.org/licenses/by/4.0/

1. 引言

本文讨论的图均为简单、有限的无向图。未定义的术语和符号参见 [1] 。设G是一个图。V(G)和E(G)分别表示图G的顶点集和边集,A(G)是图G的(0,1)邻接矩阵(这里,当顶点vi和vj相邻时, a i j = 1 ,当顶点vi和vj不相邻时, a i j = 0 。) L ( G ) = D ( G ) A ( G ) 称为拉普拉斯矩阵(Laplace), Q ( G ) = D ( G ) + A ( G ) 称为无符号的拉普拉斯矩阵,其中D(G)为图G的顶点度对角矩阵,简记为D;A(G)为图的邻接矩阵,简记为A。多项式 L G ( λ ) = | λ I n L ( G ) | 分别为拉普拉斯矩阵的特征多项式和无符号拉普拉斯矩阵的特征多项式(其中I为单位方阵)。

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

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

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

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

定理1:设G是具有n个顶点的完全图,则它的推广拉普拉斯矩阵Lk的特征多项式为 L k ( λ ) = [ λ ( k 1 ) ( n 1 ) ] [ λ k ( n 1 ) 1 ] n 1

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

L k ( λ ) = | λ I n L k | = | λ k ( n 1 ) 1 1 1 1 λ k ( n 1 ) 0 0 1 0 λ k ( n 1 ) 0 1 0 0 λ k ( n 1 ) | (1)

计算 L k ( λ ) ,首先需把(1)式中第2至n行同时加到第1行,即可提出公因子 λ [ ( k 1 ) ( n 1 ) ] 得:

L k ( λ ) = [ λ ( k 1 ) ( n 1 ) ] | 1 1 1 1 1 λ k ( n 1 ) 0 0 1 0 λ k ( n 1 ) 0 1 0 0 λ k ( n 1 ) | (2)

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

L k ( λ ) = [ λ ( k 1 ) ( n 1 ) ] | 1 1 1 1 0 λ k ( n 1 ) 1 0 0 0 0 λ k ( n 1 ) 1 0 0 0 0 λ k ( n 1 ) 1 | (3)

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

L k ( λ ) = [ λ ( k 1 ) ( n 1 ) ] [ λ k ( n 1 ) 1 ] n 1

易得, L k ( λ ) 的特征根如下:

λ 1 = ( k 1 ) ( n 1 ) , λ 2 = λ 3 = = λ n = k ( n 1 ) + 1

在完全图中 L k = k D A k 取值不同,会有以下性质:

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

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

(3) 当 k = 1 时, L 1 = ( D + A ) ,其特征根与无符号的拉普拉斯矩阵互为相反数。

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

L k ( λ ) = [ λ ( n 1 ) ] [ λ ( 2 n 1 ) ] n 1 λ 1 = n 1 , λ 2 = λ 3 = = λ n = 2 n 1

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

定理2:设 G = ( U V , E ) 是具有n个顶点的二部图,其中(U,V)是G的一个二分类, | U | = n 1 | V | = n 2 ,则其推广的拉普拉斯矩阵Lk的特征多项式为:

L k ( λ ) = ( λ k n 1 ) n 2 1 ( λ k n 2 ) n 1 1 [ λ 2 ( k n 1 + k n 2 ) λ + ( k 2 1 ) n 1 n 2 ]

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

L k ( λ ) = | λ I n L k | = | λ k n 2 0 1 1 0 ... λ k n 2 1 1 1 1 λ k n 1 0 1 1 0 λ k n 1 | (4)

计算 L k ( λ ) ,首先需将(4)式根据行列式的特征将其分成四块,可得:

L k ( λ ) = | A B C D |

那么子行列式A,B,C,D分别如下:

A = | λ k n 2 0 0 λ k n 2 | B = | 1 1 1 1 | C = | 1 1 1 1 | D = | λ k n 1 0 0 λ k n 1 |

根据分块矩阵的行列式计算式 L k ( λ ) = | A | | D C A 1 B | ,并且此时的行列式 | A | 必须可逆,所以得:

L k ( λ ) = ( λ k n 2 ) n 1 | [ λ k n 1 0 0 λ k n 1 ] [ 1 1 1 1 ] [ 1 λ k n 2 0 0 1 λ k n 2 ] [ 1 ... 1 ... ... ... 1 ... 1 ] | (5)

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

L k ( λ ) = ( λ k n 2 ) n 1 | λ k n 1 n 1 λ k n 2 n 1 λ k n 2 n 1 λ k n 2 n 1 λ k n 2 λ k n 1 n 1 λ k n 2 n 1 λ k n 2 n 1 λ k n 2 n 1 λ k n 2 λ k n 1 n 1 λ k n 2 | (6)

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

L ( λ ) k = ( λ k n 1 ) n 2 1 ( λ k n 2 ) n 1 1 [ λ 2 ( k n 1 + k n 2 ) λ + ( k 2 1 ) n 1 n 2 ]

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

λ 1 = k ( n 1 + n 2 ) k 2 ( n 1 n 2 ) 2 + 4 n 1 n 2 2 , λ 2 = λ 3 = = λ n 2 = k n 1

λ n 2 + 1 = = λ n 1 + n 2 1 = k n 2 , λ n = k ( n 1 + n 2 ) + k 2 ( n 1 n 2 ) 2 + 4 n 1 n 2 2

在二部图中 L k = k D A k 取值不同,会有以下性质:

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

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

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

(4) 当 k = 2 时, L 2 = 2 D A ,得到的是推广的拉普拉斯矩阵。

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

推论1:在二部图 G = ( U V , E ) 中, | U | = n 1 = 1 | V | = n 2 = n 1 时,此时的图为星图,其推广的拉普拉斯矩阵的特征多项式为: L k ( λ ) = ( λ k ) n 2 ( λ 2 k n λ + k 2 n k 2 n + 1 )

易得其特征根如下:

λ 1 = k n 2 k 2 n 2 4 k 2 n + k 2 + n 1 λ 2 = λ 3 = = λ n 1 = k λ n = k n 2 + k 2 n 2 4 k 2 n + k 2 + n 1

推论2:在二部图 G = ( U V , E ) 中, | U | = n 1 = n / 2 | V | = n 2 = n / 2 时,此时是均匀分布的二部图,其推广的拉普拉斯矩阵矩阵的特征多项式为: L k ( λ ) = 1 4 [ ( λ k n 2 ) n 2 ] [ 4 ( λ k n 2 ) 2 n 2 ]

易得其特征根如下:

λ 1 = n 2 k n 2 λ 2 = λ 3 = = λ n 1 = k n 2 λ n = n 2 + k n 2

3. 总结

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

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

基金项目

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

文章引用

梁静,赵海兴,张科,刘远超. 几类图的推广的拉普拉斯矩阵的特征多项式
The Characteristic Polynomial of Generalized Laplace Matrix of Several Kinds of Graphs[J]. 应用数学进展, 2017, 06(06): 763-767. http://dx.doi.org/10.12677/AAM.2017.66092

参考文献 (References)

  1. 1. Bondy, J.A. and Murty, U.S.R. (1976) Graph Theory with Application. The Macmilian Press Ltd., 115-120. https://doi.org/10.1007/978-1-349-03521-2

  2. 2. Brouwer, A.E. and Haemers, W.H. (2011) Spectra of Graphs. Springer, 81-82.

  3. 3. Cvetkovicid, Doob, M. and Scachs, H. (1980) Spectra of Graphs—Theory and Application. Academic Press, New York.

  4. 4. Brualdi, R.A. and Hoffman, A.J. (1985) On the Spectral Radius of (0,1)-Mantrices. Linear Algebra and Its Applications, 69, 133-146. https://doi.org/10.1016/0024-3795(85)90092-8

  5. 5. Cvetkovic, D., Rowlinson, P. and Simio, S. (2007) Singless Lap-lacian of Finite Graphs. Linear Algebra and Its Applications, 423, 155-171.

  6. 6. Mohar, B. The Laplacian Spectrum of Graphs. Department of Mathematics, University of Ljubljana, Ljubljana.

  7. 7. 赵国鹏. 完全多部图的拉普拉斯特征多项式[J]. 纺织高校基础科学学报, 2011, 24(2): 243-245.

  8. 8. 卢世芳, 卫良, 赵海兴. 完全3-部图的无符号Laplace谱[J]. 山东大学学报(理学版), 2012, 47(12): 41-46.

  9. 9. 李映辉, 王守峰. 完全图的谱[J]. 长春师范大学学报, 2015, 34(6): 6-9.

  10. 10. 李炯生, 查建国, 王新茂. 线性代数[M]. 合肥: 中国科学技术大学出版社, 2010.

期刊菜单