度数矩阵

在数学领域图论中，无向图的度数矩阵（英语：degree matrix）是一个对角矩阵 ，其中包含的信息为的每一个顶点的度数，也就是每个顶点相邻的边数。^[1] 它可以和邻接矩阵一起使用以构造图的拉普拉斯算子矩阵（拉普拉斯矩阵是度数矩阵和邻接矩阵的差值）。^[2]

定义

给定一个图 ${\displaystyle G=(V,E)}$ 与 ${\displaystyle |V|=n}$， ${\displaystyle G}$的度数矩阵 ${\displaystyle D}$是一个 ${\displaystyle n\times n}$的对角线矩阵，其定义为^[1]

${\displaystyle d_{i,j}:=\left\{{\begin{matrix}\deg(v_{i})&{\mbox{if}}\ i=j\\0&{\mbox{otherwise}}\end{matrix}}\right.}$

其中度数 ${\displaystyle \deg(v_{i})}$为这个顶点上的边的条数。 在无向图中，这意味着每个环会使得度数增加2。 在有向图中，术语“度”可以指“入度”（indegree，终点在这个顶点的边的条数）或“出度”（ outdegree，起点在这个顶点的边的条数）。

例子

下面的无向图有一个6x6的度数矩阵，其数值为。

Vertex labeled graph	度数矩阵
	${\displaystyle {\begin{pmatrix}4&0&0&0&0&0\\0&3&0&0&0&0\\0&0&2&0&0&0\\0&0&0&3&0&0\\0&0&0&0&3&0\\0&0&0&0&0&1\\\end{pmatrix}}}$

注意，对于无向图而言，开始和结束于同一节点的边（即环，如上图中的节点1）会使相应的度增加2（即被计算两次）。

性质

一个k-正则图的度数矩阵是恒为${\displaystyle k}$的对角线矩阵。

根据度的总和公式，度数矩阵的迹是对应图的边数的两倍。

参考文献

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
2. 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.