度数矩阵

给定一个图 ${\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的度数矩阵，其数值为。

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

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

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