次数行列

グラフ理論および計算機科学において、次数行列（じすうぎょうれつ、）は、それぞれの頂点の次数（すなわち、それぞれの頂点に接続した辺の数）に関する情報を含む対角行列である。次数行列はグラフのラプラシアン行列を構築するために隣接行列と一緒に使われる。
定義.
グラフformula_1 with formula_2を考えると、formula_3についての次数行列formula_4は以下のように定義されるformula_5対角行列である。
上式において、頂点の次数formula_7は辺がその頂点で終結する回数を合計する。無向グラフでは、これは各ループが頂点の次数を2ずつ増加させることを意味する。有向グラフでは、「次数」という用語は入次数（それぞれの頂点に入ってくる辺の数）または出次数（それぞれの頂点から出ていく辺の数）のどちらをも指す。
性質.
k-正則グラフの次数行列は、一定な対角成分formula_8を持つ。