度行列

代数グラフ理論の数学の分野において、無向グラフの次数行列は、各頂点の次数、つまり各頂点に接続されている辺の数に関する情報を含む対角行列です。 ^[1]これは、隣接行列とともにグラフのラプラシアン行列を構成するために使用されます。ラプラシアン行列は、次数行列と隣接行列の差です。^[2]

のグラフが与えられたとき、の次数行列は次のように定義される対角行列である^[1]${\displaystyle G=(V,E)}$${\displaystyle |V|=n}$ ${\displaystyle D}$${\displaystyle G}$${\displaystyle n\times n}$

${\displaystyle D_{i,j}:=\left\{{\begin{matrix}\deg(v_{i})&{\mbox{if}}\ i=j\\0&{\mbox{otherwise}}\end{matrix}}\right.}$

ここで、頂点の次数は、辺がその頂点で終了する回数を数えます。無向グラフでは、これは各ループが頂点の次数を 2 ずつ増やすことを意味します。有向グラフでは、次数という用語は入次数(各頂点の入力辺の数) または出次数(各頂点の出力辺の数)のいずれかを指します。 ${\displaystyle \deg(v_{i})}$

次の無向グラフには、値を持つ 6x6 次行列があります。

無向グラフの場合、同じノードで開始および終了するエッジは、対応する次数の値を 2 増加させます (つまり、2 回カウントされます)。

k 正則グラフの次数行列には、定数対角線があります。 ${\displaystyle k}$

次数和の公式によれば、次数行列の トレースは、考慮するグラフの辺の数の 2 倍になります。