次数行列

ウィキペディア

次数行列

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/12/07 04:23 UTC 版)

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

定義

グラフ${\displaystyle G=(V,E)}$ ${\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. ^ ^{a b} 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 .