次数行列のソースを表示

[[グラフ理論]]および[[計算機科学]]において、'''次数行列'''（じすうぎょうれつ、{{lang-en-short|Degree matrix}}）は、それぞれの[[頂点 (グラフ理論)|頂点]]の[[次数 (グラフ理論)|次数]]（すなわち、それぞれの頂点に接続した辺の数）に関する情報を含む[[対角行列]]である<ref name="clv">{{citation
 | last1 = Chung | first1 = Fan | author1-link = 金芳蓉
 | last2 = Lu | first2 = Linyuan
 | last3 = Vu | first3 = Van | author3-link = Van Vu
 | doi = 10.1073/pnas.0937490100
 | issue = 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 | authorlink = 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> with <math>|V|=n</math>を考えると、<math>G</math>についての'''次数行列'''<math>D</math>は以下のように定義される<math>n \times n</math>[[対角行列]]である<ref name="clv"/>。
:<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ずつ増加させることを意味する。[[有向グラフ]]では、「次数」という用語は[[入次数]]（それぞれの頂点に入ってくる辺の数）または[[出次数]]（それぞれの頂点から出ていく辺の数）のどちらをも指す。

==例==
{|class="wikitable"
!頂点がラベル付けされたグラフ
!次数行列
|-
|[[Image:6n-graph2.svg|175px]]
|<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>
|}

==性質==
[[正則グラフ|k-正則グラフ]]の次数行列は、一定な対角成分<math>k</math>を持つ。

==出典==
{{reflist}}

{{DEFAULTSORT:しすうきようれつ }}
[[Category:行列]]
[[Category:グラフ理論]]
[[Category:代数的グラフ理論]]