次数行列

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

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

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

例
頂点がラベル付けされたグラフ次数行列175px

性質
k-正則グラフの次数行列は、一定な対角成分を持つ。

出典

Category:行列
Category:グラフ理論
Category:代数的グラフ理論