查看“︁度数矩阵”︁的源代码

在[[数学]]领域[[图论]]中，无向图的'''度数矩阵'''（{{lang-en|degree matrix}}）是一个[[對角矩陣|对角矩阵]] ，其中包含的信息为的每一个[[顶点 (图论)|顶点]]的度数，也就是每个顶点相邻的边数。<ref name="clv">{{Citation|last=Chung|first=Fan|author-link=Fan Chung|last2=Lu|first2=Linyuan|last3=Vu|first3=Van|author3-link=Van Vu|doi=10.1073/pnas.0937490100|number=11|journal=Proceedings of the National Academy of Sciences of the United States of America|mr=1982145|pages=6313–6318|title=Spectra of random graphs with given expected degrees|volume=100|year=2003|pmid=12743375|pmc=164443}}</ref> 它可以和[[邻接矩阵]]一起使用以构造图的拉普拉斯算子矩阵（拉普拉斯矩阵是度数矩阵和邻接矩阵的差值）。<ref name="mohar">{{Citation|last=Mohar|first=Bojan|author-link=Bojan Mohar|editor1-last=Beineke|editor1-first=Lowell W.|editor2-last=Wilson|editor2-first=Robin J.|contribution=Graph Laplacians|isbn=0-521-80197-4|mr=2125091|pages=113–136|publisher=Cambridge University Press, Cambridge|series=Encyclopedia of Mathematics and its Applications|title=Topics in algebraic graph theory|url=https://books.google.com/books?id=z2K26gZLC1MC&pg=PA113|volume=102|year=2004}}.</ref>

== 定义 ==
给定一个图 <math>G=(V,E)</math> 与 <math>|V|=n</math>， <math>G</math>的'''度数矩阵''' <math>D</math>是一个 <math>n \times n</math>的[[對角矩陣|对角线矩阵]]，其定义为<ref name="clv">{{Citation|last=Chung|first=Fan|author-link=Fan Chung|last2=Lu|first2=Linyuan|last3=Vu|first3=Van|author3-link=Van Vu|doi=10.1073/pnas.0937490100|number=11|journal=Proceedings of the National Academy of Sciences of the United States of America|mr=1982145|pages=6313–6318|title=Spectra of random graphs with given expected degrees|volume=100|year=2003|pmid=12743375|pmc=164443}}</ref>

: <math>d_{i,j}:=\left\{
\begin{matrix} 
\deg(v_i) & \mbox{if}\ i = j \\
0 & \mbox{otherwise}
\end{matrix}
\right.
</math>

其中度数 <math>\deg(v_i)</math>为这个顶点上的边的条数。 在[[图 (数学)|无向图]]中，这意味着每个环会使得度数增加2。 在有向图中，术语“'''度'''”可以指“入度”（indegree，终点在这个顶点的边的条数）或“出度”（ outdegree，起点在这个顶点的边的条数）。

== 例子 ==
下面的无向图有一个6x6的度数矩阵，其数值为。
{| class="wikitable"
!Vertex labeled graph
!度数矩阵
|-
|[[File:6n-graph2.svg|191x191像素]]
|<math>\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}</math>
|}
注意，对于无向图而言，开始和结束于同一节点的边（即环，如上图中的节点1）会使相应的度增加2（即被计算两次）。

== 性质 ==
一个[[正則圖|k-正则图]]的度数矩阵是恒为<math>k</math>的对角线矩阵。

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

== 参考文献 ==
<references group="" responsive=""></references>
[[Category:矩陣]]
[[Category:有未审阅翻译的页面]]
[[Category:代数图论]]