Matrika stopenj

Matrika stopenj je diagonalna matrika, ki vsebuje stopnje za vsako vozlišče. 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} =\left\{ \begin{matrix} \deg(v_i) & \mbox{kadar je}\ i = j \\ 0 & \mbox{v ostalih primerih} \end{matrix} \right.$.

kjer je

• $\deg(v_i) \,$ stopnja vozlišča $i \,$

Zgled

graf z označenimi vozlišči	matrika stopenj
	$\begin{bmatrix} 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{bmatrix}$

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

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

Glej tudi

• seznam vrst matrik

Zunanje povezave

• Uvod v uporabo graf-teoretičnih matrik v kemiji (v slovenščini)
• Matrika stopenj na MathWorld (v angleščini)