度数矩阵
在数学领域图论中,无向图的度数矩阵(英语:degree matrix)是一个对角矩阵 ,其中包含的信息为的每一个顶点的度数,也就是每个顶点相邻的边数。[1] 它可以和邻接矩阵一起使用以构造图的拉普拉斯算子矩阵(拉普拉斯矩阵是度数矩阵和邻接矩阵的差值)。[2]
定义
编辑给定一个图 与 , 的度数矩阵 是一个 的对角线矩阵,其定义为[1]
其中度数 为这个顶点上的边的条数。 在无向图中,这意味着每个环会使得度数增加2。 在有向图中,术语“度”可以指“入度”(indegree,终点在这个顶点的边的条数)或“出度”( outdegree,起点在这个顶点的边的条数)。
例子
编辑下面的无向图有一个6x6的度数矩阵,其数值为。
Vertex labeled graph | 度数矩阵 |
---|---|
注意,对于无向图而言,开始和结束于同一节点的边(即环,如上图中的节点1)会使相应的度增加2(即被计算两次)。
性质
编辑一个k-正则图的度数矩阵是恒为 的对角线矩阵。
根据度的总和公式,度数矩阵的迹是对应图的边数的两倍。
参考文献
编辑- ^ 1.0 1.1 Chung, Fan; Lu, Linyuan; Vu, Van, Spectra of random graphs with given expected degrees, Proceedings of the National Academy of Sciences of the United States of America, 2003, 100 (11): 6313–6318, MR 1982145, PMC 164443 , PMID 12743375, doi:10.1073/pnas.0937490100
- ^ Mohar, Bojan, Graph Laplacians, Beineke, Lowell W.; Wilson, Robin J. (编), Topics in algebraic graph theory, Encyclopedia of Mathematics and its Applications 102, Cambridge University Press, Cambridge: 113–136, 2004, ISBN 0-521-80197-4, MR 2125091.