次数行列

出典: フリー百科事典『ウィキペディア(Wikipedia)』

出典: フリー百科事典『ウィキペディア(Wikipedia)』

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

定義[編集]

グラフ with を考えると、についての次数行列は以下のように定義される対角行列である[1]

上式において、頂点の次数は辺がその頂点で終結する回数を合計する。無向グラフでは、これは各ループが頂点の次数を2ずつ増加させることを意味する。有向グラフであ、「次数」という用語は入次数(それぞれの頂点に入ってくる辺の数)または出次数(それぞれの頂点から出ていく辺の数)のどちらをも指す。

[編集]

頂点がラベル付けされたグラフ 次数行列
6n-graph2.svg

性質[編集]

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 .