Matrika stopenj

Matrika stopenj je diagonalna matrika, ki vsebuje stopnje za vsako točko. Uporablja se skupaj z matriko sosednosti za tvorjenje Laplaceove matrike.

Definicija

Za dani graf $G = (V, E)$ je matrika stopenj kvadratna matrika z razsežnostjo $n \times n$ , ki ima elemente enake:

d_{i, j} = {\begin{matrix} \deg (v_{i}) & kadar je i = j \\ 0 & v ostalih primerih \end{matrix}

,

kjer je:

graf z označenimi točkami	matrika stopenj
	$[\begin{matrix} 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{matrix}]$

V neusmerjenem grafu je stopnja enaka številu povezav, ki so vezane na točko. To pomeni, da se zanke štejejo dvakrat (glej točko 1).

Matrika stopenj za k-regularni graf ima glavno diagonalo iz samih enakih vrednosti, ki so enake k.