次数行列

グラフ理論および計算機科学において、次数行列（じすうぎょうれつ、英: Degree matrix）は、それぞれの頂点の次数（すなわち、それぞれの頂点に接続した辺の数）に関する情報を含む対角行列である^[1]。次数行列はグラフのラプラシアン行列を構築するために隣接行列と一緒に使われる^[2]。

定義

グラフ${\displaystyle G=(V,E)}$ with ${\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ずつ増加させることを意味する。有向グラフでは、「次数」という用語は入次数（それぞれの頂点に入ってくる辺の数）または出次数（それぞれの頂点から出ていく辺の数）のどちらをも指す。

例

頂点がラベル付けされたグラフ	次数行列
	${\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}}}$

性質

k-正則グラフの次数行列は、一定な対角成分${\displaystyle k}$を持つ。

出典

1. Chung, Fan; Lu, Linyuan; Vu, Van (2003), “Spectra of random graphs with given expected degrees”, Proceedings of the National Academy of Sciences of the United States of America 100 (11): 6313–6318, doi:10.1073/pnas.0937490100, MR1982145, PMC 164443, PMID 12743375, http://www.pubmedcentral.nih.gov/articlerender.fcgi?tool=pmcentrez&artid=164443.
2. Mohar, Bojan (2004), “Graph Laplacians”, in Beineke, Lowell W.; Wilson, Robin J., Topics in algebraic graph theory, Encyclopedia of Mathematics and its Applications, 102, Cambridge University Press, Cambridge, pp. 113–136, ISBN 0-521-80197-4, MR2125091, https://books.google.com/books?id=z2K26gZLC1MC&pg=PA113.