度数矩阵

给定一个图 ${\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。 在一个 有向图中，术语度可能指 入度 (终点在这个顶点的边的条数)或 出度 (起点在这个顶点的边的条数)。